Heap (Priority Queue)
Some handful snippets for using heap in Python.
Create a heap
Empty heap
heap = []
From a list
Complexity:
heapq.heapify(the_list) # Inplace
tip
For max heap, use negative numbers.
Push an item
heapq.heappush(heap, item)
Read the top (smallest) item
item = heapq.heappop(heap)
without removing it (peek):
item = heap[0]
Remove an arbitary item from a heap
Removing the item at index i1:
Complexity:
h[i] = h[-1]
h.pop()
heapq.heapify(h)
Complexity:
h[i] = h[-1]
h.pop()
if i < len(h):
heapq._siftup(h, i)
heapq._siftdown(h, 0, i)
Keep top K largest items
for item in items:
if len(heap) == k:
heappushpop(heap, item)
else:
heappush(heap, item)