Binary heap (MaxPQ)

Cost and properties

insert	O(log n) — ≤ 1 + lg n compares
del-max	O(log n) — ≤ 2 lg n compares
max	O(1)
space	no links at all

Reference: Sedgewick & Wayne, §2.4; Williams 1964.

Binary heap (MaxPQ) in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class MaxPQ:
    # Heap-ordered COMPLETE binary tree kept in pq[1..n]:
    #   parent of k is k // 2,  children of k are 2k and 2k + 1.
    # Heap order: no key is larger than its parent, so pq[1] is the max.

    def __init__(self):
        self.pq = [None]                  # pq[0] unused: clean index maths
        self.n = 0

    def insert(self, key):
        self.pq.append(key)               # put it at the end (a new leaf)
        self.n += 1
        self._swim(self.n)                # then move it UP into place

    def del_max(self):
        top = self.pq[1]                  # the root is the maximum
        self._swap(1, self.n)             # swap it with the last leaf
        self.pq.pop()
        self.n -= 1
        self._sink(1)                     # then move the new root DOWN
        return top

    def _swim(self, k):
        while k > 1 and self.pq[k // 2] < self.pq[k]:
            self._swap(k, k // 2)         # bigger than the parent: exchange
            k //= 2

    def _sink(self, k):
        while 2 * k <= self.n:
            j = 2 * k
            if j < self.n and self.pq[j] < self.pq[j + 1]:
                j += 1                    # pick the LARGER child
            if not self.pq[k] < self.pq[j]:
                break                     # heap order restored
            self._swap(k, j)
            k = j

    def _swap(self, i, j):
        self.pq[i], self.pq[j] = self.pq[j], self.pq[i]

Why it works

The array is the tree

No node objects, no pointers: the tree's shape is implied by the indices. Node k's children are 2k and 2k+1, its parent is k/2 (integer division). This works only because the tree is complete — filled level by level, left to right — which also forces its height to be exactly ⌊lg n⌋. Starting at index 1 rather than 0 is what keeps the arithmetic clean.

Heap order is weaker than sorted

The only promise is parent ≥ children. Siblings are unordered, and the array is not sorted — that is precisely why insert is cheap. A priority queue that kept everything sorted would pay n per insert; the heap pays lg n because it maintains just enough order to know the maximum.

Swim and sink are the same idea, opposite directions

• Swim: the new key may be too big for its parent — exchange upward until it is not. At most lg n exchanges, 1 compare each.
• Sink: the new root may be too small for its children — exchange with the larger child until it is not. 2 compares per level (pick the larger child, then compare), so ≤ 2 lg n.

Sinking to the larger child is not an optimisation: exchanging with the smaller one leaves the other child above its parent and breaks heap order.

Practical notes

• Immutability matters: if a client mutates a key already in the queue, heap order breaks silently and the structure lies about its maximum.
• MinPQ is the same code with the comparison reversed — which is what Dijkstra and Prim use in Part II.
• An index priority queue adds decrease_key, needed by those same algorithms to update a vertex's distance.

What to try in the animation

A letter or number inserts it; - removes the maximum. Use build then drain to see the keys come out in descending order.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• course example — S O R T - E X - A M - P L E - - -
• insert in order (worst swim) — 1 2 3 4 5 6 7
• build then drain — 5 9 2 7 4 8 1 - - - - - - -
• all equal — 4 4 4 4 - - - -

Open Binary heap (MaxPQ) in the player →

The rest of Priority queues

• Heapsort Heapify the array bottom-up, then repeatedly swap the root to the end.