[Python-Dev] Priority queue (binary heap) python code

[Tim Peters]

[Guido]
> The only change I would make would be to make heap[0] the
> lowest value rather than the highest.

[Kevin O'Connor]
> I agree this appears more natural, but a priority queue that pops the
> lowest priority item is a bit odd.

So now the fellow who wrote the code to begin with squirms at what will
happen if it's actually put in the std library, and sounds like he would
continue using his own code.

[Delaney, Timothy]
> I'm in two minds about this. My first thought is that the *first* item
> (heap[0]) should be the highest priority.
>
> OTOH, if it were a sorted list, list[0] would return the *lowest*
> priority.

On the third hand, if you're using heaps for sorting (as in a heapsort),
it's far more natural to have a max-heap -- else the sort can't be done
in-place (with a max-heap you pop the largest value, copy it to the last
array slot, pretend the array is one shorter, and trickle what *was* in the
last array slot back into the now-one-smaller max-heap; repeat N-1 times and
you've sorted the array in-place).

On the fourth hand, if you want a *bounded* priority queue, to remember only
the N best-scoring (largest-priority) objects for some fixed N, then
(perhaps paradoxically) a min-heap is what you need.

On the fifth head, if you want to process items in priorty order (highest
first) interleaved with entering new items, then you need a max-heap.  I
suspect that's what Kevin does.

> So i think for consistency heap[0] must return the lowest priority.

On the sixth hand, anyone who has implemented a heap in another 0-based
language expects the first slot in the array to be unused, in order to
simplify the indexing (parent = child >> 1 uniformly if the root is at index
1), and to ensure that all nodes on the same level have indices with the
same leading bit (which can be helpful in advanced algorithms -- then, e.g.,
you know that i and j are on the same level of the tree if and only if i&j >
i^j; maybe that's not obvious at first glance <wink>).

Priority queues just aren't a once-size-fits-all thing.