Push values into a min-heap by hand

Heaps and priority queues Mid-level Python 3.13+ Kotlin 2.4+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

import heapq
heap: list[int] = []
for v in [5, 3, 8, 1]:
    heapq.heappush(heap, v)
before = list(heap)
print(before, heapq.heappop(heap), heap)

Options[1, 3, 8, 5] 1 [3, 5, 8][1, 3, 5, 8] 1 [3, 5, 8][1, 3, 8, 5] 1 [5, 3, 8]

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [1, 3, 8, 5] 1 [3, 5, 8]

Right: 1 climbs to the root; after the pop, 5 moves to the top and sinks below 3.

Only the root is guaranteed smallest; the rest of the list is in heap order, not sorted order.

Why not the others?

B [1, 3, 5, 8] 1 [3, 5, 8]. A heap is not fully sorted; 5 sits below 3 at the end.
C [1, 3, 8, 5] 1 [5, 3, 8]. After the pop, the new root sinks below the smaller child.

A min-heap drawn as a tree and as its backing list while values are pushed one at a time, showing how far each value swaps upward, for two push orders.

Steps come from running the Python solution.

Text version

Push 5, 3, 8, 1:

Push 5: 0 swaps up, list [5].
Push 3: 1 swap up, list [3, 5] (slots 1 → 0).
Push 8: 0 swaps up, list [3, 5, 8].
Push 1: 2 swaps up, list [1, 3, 8, 5] (slots 3 → 1 → 0).

Result: [1, 3, 8, 5]

Push 9, 7, 5, 3, 1:

Push 9: 0 swaps up, list [9].
Push 7: 1 swap up, list [7, 9] (slots 1 → 0).
Push 5: 1 swap up, list [5, 9, 7] (slots 2 → 0).
Push 3: 2 swaps up, list [3, 5, 7, 9] (slots 3 → 1 → 0).
Push 1: 2 swaps up, list [1, 3, 7, 9, 5] (slots 4 → 1 → 0).

Result: [1, 3, 7, 9, 5]

30-second answer

A heap stored in a list keeps each parent at index (i - 1) // 2 no larger than its children. A push appends at the end and swaps upward until the parent is not larger. Each push climbs at most the height of the tree, O(log n), so n pushes cost O(n log n), and the heap takes O(n) space. The result matches what heapq.heappush produces.

Practise saying it · 45 s. No recording, just a timer

Explain a heap push.

Say your answer out loud, then check which of these points you covered:

List layout, parent (i - 1) // 2
Swap upward
O(log n) per push

Deep dive

The list layout is the template for all heap work: children of i sit at 2i + 1 and 2i + 2.

A pop moves the last item to the root and swaps it downward with the smaller child.

Building from a full list with heapify is O(n), cheaper than n pushes.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

def push_all(values: list[int]) -> list[int]:
    heap: list[int] = []
    for v in values:
        heap.append(v)
        i = len(heap) - 1
        while i > 0:
            up = (i - 1) // 2  # parent slot
            if heap[up] <= heap[i]:
                break
            heap[up], heap[i] = heap[i], heap[up]
            i = up
    return heap

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1

Kotlin 2.4

fun pushAll(values: List<Int>): List<Int> {
    val heap = mutableListOf<Int>()
    for (v in values) {
        heap.add(v)
        var i = heap.size - 1
        while (i > 0) {
            val up = (i - 1) / 2 // parent slot
            if (heap[up] <= heap[i]) break
            heap[up] = heap[i].also { heap[i] = heap[up] }
            i = up
        }
    }
    return heap
}

Common mistakes

Comparing with the wrong parent index, such as i // 2 with zero-based indexes.
Swapping when the parent equals the child, which is harmless but wasted work.

Senior take & follow-ups

Draw the list and the tree side by side; showing both views explains the index maths.

Follow-up questions

Think of your answer first, then open the hint.

How does a pop work?
Show hint
Swap the root with the last item, remove it, then sift the new root down past the smaller child.
Why is heapify O(n)?
Show hint
Most nodes are near the bottom and move only a little; the total work sums to a constant times n.

What each operation costs: Min Heap · Max Heap · Heap Operations · Priority Queue

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.