Also, in case nobody has said so, worst-case performance for insertion into a large heap (log N) is much better than for insertion into a sorted list (N). Of course, in practice, it takes a really large heap to notice these effects. -Dave From: "Martin v. Loewis" <martin@v.loewis.de> > Oren Tirosh <oren-py-d@hishome.net> writes: > > > 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! > > I think that heaps don't allocate additional memory is a valuable > property, more valuable than the asymptotic complexity (which is also > quite good). If you don't want to build priority queues, you can still > use heaps to sort a list. > > IMO, heaps are so standard as an algorithm that they belong into the > Python library, in some form. It is then the user's choice to use that > algorithm or not. > > Regards, > Martin
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