Build a heap and pop it

Lesson 8.2 · Easy · Heap basics · 6 min · by Vinay C

We'll cover the following

Push numbers into a min-heap one by one, then pop them all. See how the smallest value always sits at the root.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

Push 9 at the end. Bubble it up while it is smaller than its parent.

inserted 1 of 10

1 / 48

Time	Space	Why
`O(n log n)`	`O(n)`	n pushes and n pops, each O(log n).

import heapq
h = []
for x in nums:
    heapq.heappush(h, x)        # O(log n)
out = [heapq.heappop(h) for _ in range(len(h))]   # sorted

A heap is a tree stored in an array. A parent is never bigger than its children, so the smallest is at index 0. Pushing bubbles a value up, and popping sinks a value down. Both take about log n swaps.
Time O(n log n), space O(n). n pushes and n pops, each O(log n).