Binary Heaps

The Priority Queue Interface

A priority queue stores items with keys and is optimised for one thing: finding and removing the item with the highest (or lowest) priority. The interface is a deliberate subset of the full Set interface:

Three Priority Queues, Three Sorting Algorithms

Any priority queue translates directly into a sorting algorithm: build the queue, then repeatedly call delete_max to extract items in decreasing order. The choice of underlying data structure determines the sort:

(a) amortised

The binary heap achieves AVL-tree-level sort performance while being in-place — using only $O(1)$ extra space beyond the input array. This is the key advantage over AVL trees for sorting.

Array as a Complete Binary Tree

A binary heap is stored in a plain array — no pointers needed. The trick is reading the array as a complete binary tree: fill levels top-to-bottom, left-to-right.

The parent-child relationships are encoded entirely in index arithmetic — no pointers stored anywhere:

A complete binary tree on $n$ nodes has height $\lfloor \log_2 n \rfloor$ — always balanced, always $O(\log n)$ tall. This is the source of the heap's performance guarantee.

The Max-Heap Property

Insert — Heapify Up

Append the new item to the end of the array (next leaf in reading order). The heap property holds everywhere except possibly at this new node — it might be larger than its parent. Fix it by swapping with the parent and repeating upward until the property is restored.

def parent(i):
    return (i - 1) // 2 if i > 0 else i

def max_heapify_up(A, n, i):
    """Restore max-heap property from node i upward. O(log n)."""
    p = parent(i)
    if A[p].key < A[i].key:          # parent is smaller — swap
        A[i], A[p] = A[p], A[i]
        max_heapify_up(A, n, p)       # recurse on parent

class MaxHeap:
    def __init__(self):
        self.A = []

    def insert(self, x):              # O(log n) amortised
        self.A.append(x)              # place at end (next leaf)
        max_heapify_up(self.A, len(self.A), len(self.A) - 1)

    def find_max(self):               # O(1)
        return self.A[0] if self.A else None

#include <vector>
using namespace std;

int parent(int i) { return i > 0 ? (i - 1) / 2 : i; }
int left(int i)   { return 2 * i + 1; }
int right(int i)  { return 2 * i + 2; }

template<typename T>
void heapify_up(vector<T>& A, int i) {
    int p = parent(i);
    if (i > 0 && A[p] < A[i]) {     // parent is smaller — swap
        swap(A[i], A[p]);
        heapify_up(A, p);              // recurse on parent
    }
}

template<typename T>
struct MaxHeap {
    vector<T> A;

    void insert(T x) {                 // O(log n) amortised
        A.push_back(x);
        heapify_up(A, A.size() - 1);
    }

    T find_max() { return A[0]; }      // O(1)
};

Correctness: appending creates one potential violation at node $i$. If $Q[i] > Q[\text{parent}(i)]$, we swap — now the parent satisfies the heap property with all its descendants (the old subtree is unchanged), and the same potential violation may have moved one level up. We recurse. When we reach the root or a node where the property holds, we are done. Each step moves strictly upward, so termination is guaranteed.

Runtime: at most $h = \lfloor \log_2 n \rfloor$ swaps — one per level of the tree. $\Theta(\log n)$.

Delete Max — Heapify Down

The maximum is always at $Q[0]$. We cannot simply remove it and leave a gap. Instead: swap the root with the last element, remove the last element (now holding the old max), then fix the heap property downward from the new root.

The new root may be smaller than one or both children. Fix it by swapping with the larger child (to preserve the heap property for the non-swapped child), then recurse downward.

def left(i, n):  return 2*i+1 if 2*i+1 < n else i
def right(i, n): return 2*i+2 if 2*i+2 < n else i

def max_heapify_down(A, n, i):
    """Restore max-heap property from node i downward. O(log n)."""
    l, r = left(i, n), right(i, n)
    # find index of the largest among node i and its children
    c = l if A[r].key < A[l].key else r   # larger child
    if A[i].key < A[c].key:               # i is smaller than a child
        A[i], A[c] = A[c], A[i]
        max_heapify_down(A, n, c)          # recurse on the child we swapped

    def delete_max(self):                  # O(log n)
        n = len(self.A)
        self.A[0], self.A[n-1] = self.A[n-1], self.A[0]  # swap root with last
        max_val = self.A.pop()             # remove last (old root = max)
        max_heapify_down(self.A, len(self.A), 0)           # fix heap from root
        return max_val

template<typename T>
void heapify_down(vector<T>& A, int n, int i) {
    int l = left(i), r = right(i);
    // find larger child (stay in bounds)
    int c = (r < n && A[l] < A[r]) ? r : (l < n ? l : i);
    if (c != i && A[i] < A[c]) {      // i is smaller than its child
        swap(A[i], A[c]);
        heapify_down(A, n, c);          // recurse on the swapped child
    }
}

template<typename T>
T MaxHeap<T>::delete_max() {          // O(log n)
    T mx = A[0];
    swap(A[0], A.back());              // move last element to root
    A.pop_back();                      // remove old max
    if (!A.empty())
        heapify_down(A, A.size(), 0);  // restore heap property
    return mx;
}

$O(n)$ Build Heap — The Surprising Result

Inserting $n$ items one by one (heapify_up) costs $\sum_{i=0}^{n-1} \log i = \log(n!) = \Omega(n \log n)$. But if we have all $n$ items available at once, we can do better.

Key observation: the bottom half of the array are all leaves — they trivially satisfy the heap property (no children to violate it). Only the top half needs fixing.

Run max_heapify_down from index $\lfloor n/2 \rfloor - 1$ down to $0$. Each call costs $O(\text{height of node } i)$. Nodes near the leaves have small height; the total cost telescopes to $O(n)$:

def build_max_heap(A):
    """Convert arbitrary array A into a max-heap in O(n) time."""
    n = len(A)
    # Start from last non-leaf (index n//2 - 1) and go up to root
    for i in range(n // 2 - 1, -1, -1):   # O(n) — see proof above
        max_heapify_down(A, n, i)           # O(height(i)) per call


def heap_sort(A):
    """Sort A in-place in O(n log n). Uses O(1) extra space."""
    n = len(A)
    build_max_heap(A)                       # O(n)  — build phase
    for i in range(n - 1, 0, -1):          # O(n log n) — extract phase
        A[0], A[i] = A[i], A[0]            # move current max to sorted end
        max_heapify_down(A, i, 0)           # heap shrinks by 1 each iteration

# Trace on [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]:
# After build_max_heap: [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]  ← valid max-heap
# After extract phase:  [1, 2, 3, 4, 7, 8, 9, 10, 14, 16]  ← sorted

#include <vector>
#include <algorithm>
using namespace std;

template<typename T>
void build_max_heap(vector<T>& A) {   // O(n)
    int n = A.size();
    for (int i = n/2 - 1; i >= 0; --i)
        heapify_down(A, n, i);
}

template<typename T>
void heap_sort(vector<T>& A) {        // O(n log n), in-place
    build_max_heap(A);                 // O(n) — arrange as max-heap
    for (int i = A.size()-1; i > 0; --i) {
        swap(A[0], A[i]);              // move max to sorted end
        heapify_down(A, i, 0);         // shrink heap and restore
    }
    // A is now sorted in ascending order
}
// Note: std::sort_heap does exactly this after std::make_heap

import heapq

orders = []  # min-heap on negative priority = max-heap on priority

# Insert 5 orders (priority, order_id, side, strike)
heapq.heappush(orders, (-85, 1, 'buy',  24000))
heapq.heappush(orders, (-92, 2, 'sell', 24500))
heapq.heappush(orders, (-71, 3, 'buy',  23500))
heapq.heappush(orders, (-98, 4, 'sell', 24000))  # highest priority
heapq.heappush(orders, (-88, 5, 'buy',  24200))

# Extract top 3 — each O(log n)
for _ in range(3):
    neg_p, oid, side, strike = heapq.heappop(orders)
    print(f"Fill order {oid}: {side} {strike} (priority {-neg_p})")
# Output:
# Fill order 4: sell 24000 (priority 98)
# Fill order 2: sell 24500 (priority 92)
# Fill order 5: buy  24200 (priority 88)