Heaps & Priority Queues

Concept

A heap is a complete binary tree stored in an array where each parent is ≤ its children (min-heap).

Push and pop are O(log n); peeking the minimum is O(1). Python's heapq is a min-heap; negate values for a max-heap.

For top-K largest, keep a min-heap of size K: O(n log K).

Complexity

Code (Python)

import heapq

def k_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return sorted(heap, reverse=True)

Remember

• “K largest / smallest / closest” → heap.
• Merge K sorted lists → heap of heads.
• Median of a stream → two heaps.