[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.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4