Heaps & Priority Queues

Always-sorted access to the minimum or maximum, O(log n) insert, O(1) peek

A heap is a complete binary tree where each parent is smaller (min-heap) or larger (max-heap) than its children. This guarantees O(1) access to the min/max and O(log n) insert/remove.
Python's heapq module is a min-heap. For max-heap: negate values.
Key operations:

heapq.heappush(h, x), O(log n)

heapq.heappop(h), O(log n)

h[0], peek min, O(1)

K largest elements using a min-heappython

import heapq

def k_largest(nums, k):
    """Return k largest elements using a size-k min-heap."""
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)  # Remove smallest, keep k largest
    return sorted(heap, reverse=True)

print(k_largest([3, 1, 5, 12, 2, 11], 3))  # → [12, 11, 5]

⏰In the Real World...

Task schedulers use priority queues, the task with the highest priority (or earliest deadline) is always at the top. OS process scheduling, Dijkstra's algorithm, and A* pathfinding all use heaps.

🤔Quick Check

What is the time complexity of finding the k-th largest element using a heap?

🎯

Phase Complete!

Greedy & Heaps

Greedy algorithms and heaps complete your toolkit. One final phase: the top interview patterns that appear in 80% of coding interviews.

0/500

Practice Exercises

0/1 solved

Exercise 1 of 1hard

⏱ 00:00

Merge K Sorted Lists

Merge k sorted arrays into one sorted array using a heap.
Expected output: [1, 1, 2, 3, 4, 4, 5, 6]

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next