Thanks @tim.one !
I wonder… What do you think it would be better? Having something like Heap(variant="min") (and also "max" can be passed), or two MinHeap and MaxHeap classes?
We expect for usage of these two variants to be somewhat equivalent? (better two classes) Or “min” is enough for almost everybody? (better one Heap in this case)
Thanks!
Two classes is my preference. Ironically, the one “compelling” use case (good worst-case sorting) needs a max heap. It’s counterintuitive because a max heap moves the largest elements to the front at first. Which is the most convenient way to swap them to the end as the sort goes on and the “still a heap” part shrinks.,
Min queues are best for priority queues that want “the smallest current element” first, like shortest-path problems. But other priority-queue algorithms want the largest first instead.
This is so application-specific that there’s really no benefit to be gained, but potential for needless confusion, by smashing them all into a single class.
A SortedList in contrast can do “smallest first” or “largest first” at each step, depending on whether you do .pop(0) or .pop(-1),. Which I’ve done at times, alternating on each step. This is surprisingly hard to get working right with a min-heap + max-heap pair.
It might be an option to consider Min-Max heap.
Here it says it is already faster than binary heap: On Modern Hardware the Min-Max Heap beats a Binary Heap | Probably Dance
And here it is optimized further: https://arxiv.org/pdf/cs/0007043
Of course, more work than just abstracting existing heapq, but it might be good to get something a bit faster (and more functional) - from my experience, priority queue is often a bottleneck in Python implementations of quite a few algorithms like Dijkstra’s or A* sequence alignment.
Yes, that’s interesting. If an implementation is needed to explore this direction, I’d be happy to contribute or prototype it.
I’ll work on this abstraction…
Exactly, I added Title: Add Optional Comparator Support to heapq for Enhanced Flexibility · Issue #127328 · python/cpython · GitHub once.
Yeah, key would be a good flexibility. However, function calls are expensive. Alternative key object on which comparison happens might be better.
I am not too fussed about a wrapper - flyweight functions are quite elegant IMO and Python wrapper does impact relative performance a fair bit.
On the other hand, if someone is doing C work, why not add extra alt_key argument? 
It would definitely make Dijkstra faster and more importantly avoid issues when 2nd element of tuple (which is the current fastest workaround) is non-comparable!
And minmax heap is a long shot here… Would be quite fancy improvement ofc, especially if it is faster than heapq. But I imagine new heap is very far down the priority list.
I think SortedList is much more realistic to expect as far as new data structures go. I am just not convinced copy+pasting sortedcontainers without a bit of research is a good idea.
I don’t think there is a “priority list” here 
.Only very trendy things get added now in the absence of very compelling real-life use cases.
In the general area of priority queues, the most frequent annoyance I’ve encountered is the lack of a pleasant approach to the “decrease key” primitive. For example. you’ re using A* to find an optimal (“lowest cost”) path between two sets of points in a state space, implemented as some form of weighted graph.
Ai it it goes on, a particular node can be encountered more than once, via different paths from the start set. Then some successor of the current-lowest state may already be on the queue. What to do? If a lower bound on a completion is smaller than the lower bound computed for the completion of the path found before. we don’t want to add the state redundantly - we want to decrease the lower bound for this state saved before. “Decrease key”.
Now an underlying priority queue implementation may well support this functionality very efficiently. For example, for a plain list arranged as a heap, simply swap the old heap node with its parent so long as the new lower bound is smaller than the parent’s. At the worst at most \log_2{n} swaps.
BUT! We don’t know where the earlier instance of the node lived in the heap, and there’s no efficient way to find it.
A fancier implementation can store the heap index in each heap entry, and keep it updated as heap nodes change position. Then we need also to add a way to find a heap node (if any) given a state’s value (not just some path _to_the state).
It can get quite involved, and there appears to be plausible way for a generic “priority queue class” to supply everything that’s needed. Some other approaches (all of which I’ve tiried, none of which I liked):
.
Write a custom prioirihy queue that supplies exactly what its client really needs.
Rewrite the simple heap-as-plain-list code to keep track of elements’ indices, storing them in element instances. A client using this code needs to define an element class that inherits from a specific mixin class (which supplies an instance attribute to store the element’s index).
Punt! Store duplicate states redundantly,. This is a more-general meta approach that can also apply to other priority queue headaches. Rather than try to avoid adding useless entries, instead craft a way to identify than as redundant if/when they’re popped. So start the search loop like so:
while heap:
state = heap.pop()
if state.is_useless():
continue
if state.is_goal():
return state
for each successor state:
compute lower bound on completion and push
There typically aren’t oodles of useless states added, and heap operations are log time, so speed can actually be better than with “look before you leap” (which requires slowing every mutating operation to keep indices updated). And no changes to the priority code in use are needed - no “decrease minimum” function is asked for.,
Which is all a long-winded say of saying the real world is more complicated than our clean abstractions hope for .
It’s worth noting that the observations here may not hold for python. Implement both and check. Some real-world use cases with fixed-size values and simpler, “but seemingly wrong time complexity” datastructures get huge boosts from things like cache locality, cpu predictions, and sometimes even some clever compiler outputs involving simd instructions, that may not get the same gains with pythons objects.
I think this is a very reasonable option.
Especially as it seems that the most performant heaps are faster to sufficient degree to compensate for it. Unless memory is an issue…
My current take on performance.
Top 3:
Next goes binary heap / quickheap / minmax heap.
That makes sense. Do you think it would be worth to benchmark these ds to get a clearer picture of the trade-offs? It could be interesting to compare execution time and memory usage
I think it depends on the goal here. If there is strong consensus that we want new heap/SortedList in Python and someone is willing to take it on, then, at least from my POV, it would be essential.
Otherwise - a lot of work.
However, a lot of things can be inferred without doing it:
all heaps are in-place by definition. Few exceptions: tournament tree (not a heap) is 2n memory, quickheap is O(logn) extra memory.
There are others with extra memory for double structures or extra structures for optimal “decrease key”, but these are quite explicit in definitions.
Regarding memory importance in Python. int is of size 28. pointer is of size 8. so at worst, it means that with 2n memory, your queue will be 25% more memory heavy than in-place heapq.
Quite a lot of work to implement and make sure implementations are optimized and measures optimally across HW. However, again a lot can be inferred.
Tournament Tree is the raw representation of what mergesort does, just instead of going layer by layer, it bubbles up elements one-by-one individually from POV of the tree. This results in exactly the same comparison count (but worse cache locality). Any heap which is derived from this, in terms of performace, is a downgrade - they sacrifice stability & comparisons / data moves for in-place-ness.
Then there are QuickHeaps / RadixHeaps and other, which are in a different class. I don’t know much about these, apart from the fact that QuickHeap by definition has good cache locality and performance of quicksort, except that it is online, meaning, it all boils down to memory management strategies, laziness, etc - it is not hard to see why good variants of it will be at the top of the list in terms of performance.
Then there are full SortedList options:
sortedcontainers approach with a fair bit of wiggle room.LazySortedList is possible via partitioning. Also using bins in a similar manner as sortedcontainers does. @tim.one has prototyped offline version of this in another thread.It looks like a “OO interface for heapq” idea won’t fly: see comments in this issue I opened
Regarding the heapq interface, my library (amongst many other things) provide min and max heap classes in the dev branch, they will be available in the next release. That release will also provides everything from sorted containers, but with modern, type safe code. All those classes will subsequently be compiled in Rust to be even faster.
I’m sharing this because I highly doubt that a sortedcontainer should be in the stdlib. First of all the code of sortedcontainers is very messy.
From all the python classes I had to convert for my lib it was by far the most challenging, so in any case I highly doubt that the same API is desirable. Furthermore, the differents implementation choices all make performance trade-offs, so which one would be the best and most general purpose? Hard question to answer in itself.
Do you think is there anything else that can be done?
Don’t think so, the proposal was downvoted several times in different places…
of course an integral part of the idea of having a higher level implementation is to be able to specify other ways to sort, via a `key` argument, just like sort. Creating a class with methods, and having the user still have to think about wrapping their objects in 2 or 3 tuples for proper sorting, is not even getting to half the way.
oops. That is sad to see.
IMO, at this day and age, it would be one of the last possible steps we could still do to 'make Python more Pythonic". Because from here on, it is generated code downhill - one won’t care for the 3X longer code for dealing with a function api for heaps if it is the LLM dealing with it.
Agreed.
But I don’t think it is worth building upon heapq, which is pleasantly simple with flyweight methods.
And the code is not that much of added cost, it’s a simple layer: gh-137200: Add object-oriented MinHeap and MaxHeap classes to heapq by facundobatista · Pull Request #153821 · python/cpython · GitHub