visualization

Heap Operations

A tree in disguise: it's just an array with parent = (i-1)//2.

min-heap = [2, 5, 8, 9, 7] · push(3), push(1), then pop()step 1/17

implicit tree (parent = (i-1)//2)

i=0 → 2 (root)i=1 → 5, parent i=0i=2 → 8, parent i=0i=3 → 9, parent i=1i=4 → 7, parent i=1

A min-heap is just this array: [2, 5, 8, 9, 7]. Index i's parent lives at (i-1)//2 — no pointers, the shape is implied.

pseudocode

def push(x): heap.append(x); i = len(heap)-1
    while i > 0 and heap[i] < heap[(i-1)//2]:
        swap(i, (i-1)//2); i = (i-1)//2
def pop(): top = heap[0]
    heap[0] = heap.pop()   # last leaf to root
    while a child is smaller than heap[i]:
        swap(i, smaller_child); i = smaller_child
    return top