Heaps

Foundation drill for this topic

Drill #57 — Min-heap push and pop

Easy Heap Operations

In plain English: Show how to add and remove elements from a min-heap, which always gives you the smallest element first.

A heap is a complete binary tree stored in an array where each parent is smaller than its children — push and pop maintain this property in O(log n).

Prompt

Demonstrate pushing and popping elements from a min-heap using Python's heapq module.

Try to write it from scratch before scrolling down.

Solution

import heapq

def heap_demo():
    h = []
    for val in [5, 3, 8, 1, 2]:
        heapq.heappush(h, val)  # O(log n) insert
    # h is now a valid min-heap

    result = []
    while h:
        result.append(heapq.heappop(h))  # O(log n) extract-min
    return result

# Test: heap_demo() == [1, 2, 3, 5, 8]

O(n log n) time · O(n) space

Related Micro Drills

Quick recall drills to reinforce this pattern.

34 Push and pop Stack Discipline 5s

Stack push/pop is the foundation for all LIFO operations: DFS, undo, and expression parsing.

stack = []
stack.append(x)
stack.pop()

36 Min stack push Stack Discipline 10s

Maintaining a parallel min stack gives O(1) getMin. Classic design problem.

self.stack.append(val)
self.min_stack.append(
    min(val, self.min_stack[-1] if self.min_stack else val)
)

68 Heappush Search 5s

heappush maintains the min-heap invariant. Used in merge-k-lists and streaming median.

import heapq
heapq.heappush(h, val)

See all drills in Heaps →