[Oren Tirosh] > A sorted list is a much more general-purpose data structure than a priority > queue and can be used to implement a priority queue. [...] The only > advantage of a heap is O(1) peek which doesn't seem so critical. [...] > the internal order of a heap-based priority queue is very non-intuitive and > quite useless for other purposes while a sorted list is, umm..., sorted! It surely occurred to many of us to sort a file (or any set of data) from the most interesting entry to the least interesting entry, look at the first 5% to 10%, and drop all the rest. A heap is a good way to retain the first few percents of items, without going through the lengths of fully sorting all the rest. By comparison, it would not be efficient to use `.sort()' then truncate. Within a simulation, future events are scheduled while current events are being processed, so we do not have all the events to `.sort()' first. It is likely that heaps would beat insertion after binary search, given of course that both are implemented with the same care, speed-wise. -- François Pinard http://www.iro.umontreal.ca/~pinard
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