hi,
Stabilizing a priority deque is not as simple as stabilizing a priority queue. The priority queue can be stabilized by appending to each element of the heap an integer "tie breaker" such that each new element's tie breaker is greater than that of any previous element. Problems with overflow can be dealt with (in O(n) time) by adjusting all tie breakers simultaneously and reconstructing the heap. The same method will work for priority deques, but with one important difference: if the maximum element is stable (FIFO), the minimum element would have the reverse order (LIFO).
having fifo/max lifo/min would be quite reasonable. a fifo of both min and max sides could probably be achieved by using use stability counters, no?
I think it is worth to consider to make it part of Boost.Heap library ( http://www.boost.org/doc/libs/1_55_0/doc/html/heap.html ).
I had considered this possibility previously, but I thought the interfaces of the private functions were too complicated to expose to an average user. There are also some concerns over whether an average user would find my internal design choices to be intuitive. For example, I realized early on that either the minimum or maximum would have a slight performance advantage over the other, depending on how I constructed my intervals. Because the priority deque is so similar to the priority queue, I decided to give the advantage to the maximum; this has resulted in intervals of the form [max, min], rather than the intuitive [min, max]. It would not be difficult to change this, but it is still something to consider.
boost.heap allows the user to configure the data structures via template arguments. these design decisions could be exposed to the user.
* mutability
I would appreciate a clarification of what was meant. I included functions for traversing the deque, editing individual elements, and editing large numbers of elements, so I must assume that my intuitive definition of the meaning of "mutability" differs from yours.
if you change the key (priority) of an element, the heap order may be violated, so you may have to update the heap structure. http://www.boost.org/doc/libs/1_55_0/doc/html/heap/concepts.html#heap.concep... cheers, tim