Heaps & Priority Queues

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

Imagine a to-do pile where the most urgent task always floats to the top on its own. You never sort the whole pile. You just reach up and grab the top, and it is always the right one to do next. That is a heap.
The trick is that a heap is lazy in a smart way. It does not keep everything in order, that would be slow. It only ever guarantees one thing: the smallest (or the most urgent) is sitting on top, ready to grab. Play with one below and watch the top stay correct while the bottom stays messy.

Because the heap only fixes the top, adding or removing is quick: O(log n), it only touches one path up or down, not the whole pile. And peeking at the smallest is instant, O(1), since it is always right there on top.
This is why heaps run priority queues: things that must always serve the most important item next. A hospital treating the most urgent patient first, your computer picking which task to run, a maps app choosing which road to explore next. In Python you get one for free with the `heapq` module (it is a min-heap, so the smallest is on top; for the largest on top, store the numbers as negatives).

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