Re: [boost] [Container] Priority Deque - Refinement

Subject: Re: [boost] [Container] Priority Deque - Refinement
From: tim (tim_at_[hidden])
Date: 2013-11-25 04:05:24

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.concepts.mutability

cheers,
tim