Heaps and Priority Queues

Build the mental model

A priority queue is an abstract data type: it hands you the highest-priority item first, regardless of insertion order. A binary heap is the standard concrete structure implementing it, built on one invariant, the heap property — in a min-heap, every parent node's value is less than or equal to both its children's. That's a weaker guarantee than full sorting (siblings can be in any order relative to each other), and that weakness is exactly the source of its efficiency: maintaining it only requires local swaps up or down the tree, not a global reorder. Insert appends a new element then 'bubbles it up' past parents it violates the property with — O(log n) swaps, bounded by tree height. Extract-min removes the root (always the minimum), moves the last element there, then 'sinks it down' past children — also O(log n). Peek-min is O(1), just reading the root. Compare this to the alternatives: a sorted list gives O(1) find-min but O(n) insert (shifting elements to keep it sorted); an unsorted list gives O(1) insert but O(n) find-min (scanning everything). A heap is the practical middle ground, trading a small log n cost on both operations for good performance on each.

Connect it to a real scenario

The Tutorial Platform's 'trending this week' feature needs to keep track of the most-viewed lessons as view counts constantly change, and efficiently pull out the top few without re-sorting the entire lesson catalog after every view. A min-heap of a fixed size k (bounded to the top k trending lessons) makes this cheap: pushing a new view-count update and popping the lowest-ranked entry when the heap exceeds size k are both O(log k) operations, far cheaper than re-sorting thousands of lessons on every page load. This is the priority-queue pattern in its most common real form — 'give me the current top few by some constantly-changing score,' without paying full-sort cost every time the score changes.

• The heap property (min-heap): every parent node is less than or equal to both its children.
• Insert and extract-min are O(log n); peek-min is O(1).
• A heap is the practical middle ground between a sorted list (O(n) insert) and an unsorted list (O(n) find-min).

Try the working example

import heapq

pq = []
heapq.heappush(pq, (3, "intro-to-loops"))
heapq.heappush(pq, (1, "critical-security-patch"))
heapq.heappush(pq, (2, "update-lesson-images"))

# heapq pops the smallest (priority, item) tuple first
while pq:
    priority, item = heapq.heappop(pq)
    print(priority, item)

Prints three lines in priority order (1, 2, 3): critical-security-patch, update-lesson-images, intro-to-loops.

Python Docs — heapq — Data Structures & Algorithms