On Mon, Jun 24, 2002 at 09:33:18PM -0400, Kevin O'Connor wrote: > I often find myself needing priority queues in python, and I've finally > broken down and written a simple implementation. Previously I've used > sorted lists (via bisect) to get the job done, but the heap code > significantly improves performance. There are C based implementations, but > the effort of compiling in an extension often isn't worth the effort. I'm > including the code here for everyone's amusement. > > Any chance something like this could make it into the standard python > library? It would save a lot of time for lazy people like myself. :-) A sorted list is a much more general-purpose data structure than a priority queue and can be used to implement a priority queue. It offers almost the same asymptotic performance: sorted list using splay tree (amortized): insert: O(log n) pop: O(log n) peek: O(log n) priority queue using binary heap: insert: O(log n) pop: O(log n) peek: O(1) The only advantage of a heap is O(1) peek which doesn't seem so critical. It may also have somewhat better performance by a constant factor because it uses an array rather than allocating node structures. But 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! Oren
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