Binary Heaps

A binary heap is a complete binary tree stored in an array that keeps the smallest or largest element at the root for O(log n) updates.

The heap property

A binary heap is a complete binary tree obeying the heap property: in a min-heap every parent is less than or equal to its children, so the minimum sits at the root; a max-heap is the mirror image. The heap does not fully sort its elements, it only guarantees the extreme value is on top, which is exactly what a priority queue needs.

Array layout without pointers

Because the tree is complete it packs perfectly into an array with no gaps. For a node at index i, its children are at 2i+1 and 2i+2 and its parent is at (i-1)/2. This arithmetic replaces pointers, giving compact storage and good cache behaviour.

• Find min or max: O(1)
• Insert: O(log n)
• Extract min or max: O(log n)
• Build heap from n items: O(n)

Sift up and sift down

Insertion appends the new element at the end, then sifts it up, swapping with its parent while it violates the heap property. Extraction removes the root, moves the last element to the top, then sifts it down, swapping with the smaller child until order is restored. Each traverses at most the height, so both are O(log n).

def sift_down(h, i, n):
    while True:
        smallest, l, r = i, 2*i+1, 2*i+2
        if l < n and h[l] < h[smallest]: smallest = l
        if r < n and h[r] < h[smallest]: smallest = r
        if smallest == i: return
        h[i], h[smallest] = h[smallest], h[i]
        i = smallest

Linear-time build

Building a heap by sifting down from the last internal node up to the root takes O(n), not O(n log n), because most nodes are near the bottom and sift down only a short distance. This linear build is the first phase of heapsort.