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
- removal possible
- custom orders possible
- works with Python2 and Python3
- no drawbacks discovered so far ;-)
- needs fix/work:
- item wrapper which allows duplicate items
- decrease-key+increase-key: another missing use-case of heapq
- merge heaps
- ideas are welcome :-)
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
|Filename, Size & Hash SHA256 Hash Help||File Type||Python Version||Upload Date|
(3.7 kB) Copy SHA256 Hash SHA256
|Wheel||py2.py3||Mar 9, 2016|
(4.5 kB) Copy SHA256 Hash SHA256
|Source||None||Mar 9, 2016|