Heaps

Heaps / Priority Queues

import heapq

# Min-heap (Python default)
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
print(heap[0])              # 1 -- peek O(1)
print(heapq.heappop(heap))  # 1 -- extract O(log n)

# Max-heap: negate values
max_heap = []
for v in [5,1,3]: heapq.heappush(max_heap, -v)
print(-heapq.heappop(max_heap))  # 5

# Heapify existing list -- O(n)
nums = [3,1,4,1,5]
heapq.heapify(nums)

# Top-K problems
def k_largest(nums, k):  # O(n log k)
    return heapq.nlargest(k, nums)

def k_smallest(nums, k): # O(n log k)
    return heapq.nsmallest(k, nums)

# Top-K frequent elements
from collections import Counter
def top_k_frequent(nums, k):
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)

# Merge K sorted lists -- O(n log k)
from heapq import merge
result = list(merge([1,3,5],[2,4,6],[0,7,8]))