Heap Data Structure and Priority Queue in Python

Heap and Priority Queue

A heap is a complete binary tree that satisfies the heap property. Python's heapq module implements a min-heap — the smallest element is always at the top. Heaps enable O(log n) insertion and O(1) minimum access.

import heapq

# Min-heap operations
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)

print(heap[0])              # 1 — minimum always at index 0
print(heapq.heappop(heap))  # 1 — removes minimum
print(heapq.heappop(heap))  # 1 — next minimum

# heapify — convert list to heap in O(n)
nums = [5, 3, 8, 1, 2, 9, 4]
heapq.heapify(nums)
print(nums[0])  # 1

# Max-heap: negate values (heapq only does min-heap)
max_heap = []
for n in [5, 3, 8, 1]:
    heapq.heappush(max_heap, -n)  # negate to simulate max-heap
print(-heapq.heappop(max_heap))   # 8 (largest)

Top K Pattern — Most Asked Interview

def top_k_frequent(nums, k):
    # Count frequencies
    freq = {}
    for n in nums:
        freq[n] = freq.get(n, 0) + 1

    # Min-heap of size k: O(n log k) — better than sort O(n log n)
    heap = []
    for num, count in freq.items():
        heapq.heappush(heap, (count, num))
        if len(heap) > k:
            heapq.heappop(heap)  # remove smallest frequency

    return [num for count, num in heap]

print(top_k_frequent([1,1,1,2,2,3], 2))  # [1, 2]

# K closest points to origin
def k_closest(points, k):
    heap = []
    for x, y in points:
        dist = x*x + y*y
        heapq.heappush(heap, (-dist, x, y))  # max-heap
        if len(heap) > k:
            heapq.heappop(heap)
    return [(x, y) for _, x, y in heap]

# Merge K sorted arrays
def merge_k_sorted(arrays):
    result = []
    heap   = [(arr[0], i, 0) for i, arr in enumerate(arrays) if arr]
    heapq.heapify(heap)
    while heap:
        val, arr_i, idx = heapq.heappop(heap)
        result.append(val)
        if idx + 1 < len(arrays[arr_i]):
            heapq.heappush(heap, (arrays[arr_i][idx+1], arr_i, idx+1))
    return result