[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