Heap Implementation for Python
It’s like heapq (blazingly fast) but object-oriented + more features.
What are heaps good for anyway?
When you need the smallest item of a large list—fast and with no overhead.
Let’s suppose you have a heap, you can use pop to get its smallest item.
from xheap import Heap heap = Heap(['H', 'D', 'B', 'A', 'E', 'C', 'L', 'J', 'I']) heap.pop() # returns A heap.pop() # returns B heap.pop() # returns C heap.pop() # returns D
Heapsort works this way.
Can I insert an item?
Indeed and it’s as fast as pop. Use push for insertion.
heap = Heap(['A', 'D', 'B', 'H', 'E', 'C', 'L', 'J', 'I']) heap.push('Z')
Can I remove an item from the middle of a heap?
Yes, that’s what RemovalHeap.remove is supposed to do.
from xheap import RemovalHeap heap = RemovalHeap(['A', 'D', 'B', 'H', 'E', 'C', 'L', 'J', 'I']) heap.remove('L')
Can I specify the order of the heap?
Just imagine two heaps of the very same set of items but you need different sorting for each heap. Or you need a max-heap instead of a min-heap. That is what OrderHeap is designed for:
from xheap import OrderHeap items = [date(2016, 1, 1), date(2016, 1, 2), date(2016, 1, 3), date(2016, 1, 4)] day_heap = OrderHeap(items, key=lambda date: date.day) day_heap.peek() # returns date(2016, 1, 1) weekday_heap = OrderHeap(items, key=lambda date: date.weekday()) weekday_heap.peek() # returns date(2016, 1, 4)
What about both remove+order?
No problem. Use XHeap.
If you wonder why there are 4 distinct heap implementations, it’s a matter of speed. Each additional feature slows a heap down. Thus, you could always use XHeap but beware of the slowdown.
Checking Heap Invariant
A heap is just a list. So, if you tinker with it, you can check whether its invariant still holds:
heap = Heap([4, 3, 7, 6, 1, 2, 9, 8, 5]) heap = 10 # I know what I am doing here heap.check_invariant() # but better check... ooops
uses C implementation if available (i.e. fast)
no slowdown if you don’t need more than a simple heap
custom orders possible
works with Python2 and Python3
no drawbacks discovered so far ;-)
item wrapper which allows duplicate items
decrease-key+increase-key: another missing use-case of heapq
ideas are welcome :-)
Release history Release notifications | RSS feed
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.