Heaps

Binary and d-ary heap invariants, array layout, sifting, heapify, priority contracts, stable ties, handles, batch construction, and testing.

A binary heap stores a complete binary tree in an array while maintaining a local priority rule between every parent and its children. That combination gives constant-time access to the most extreme priority and logarithmic updates without node pointers.

A heap is deliberately less ordered than a search tree. In a min-heap, the root is the smallest value, but the second-smallest value could be either child and an arbitrary target may appear almost anywhere. This partial order is exactly enough for priority queues and avoids the cost of maintaining a full sorted sequence.

Heap Model

A binary heap has two independent invariants.

Shape invariant

The tree is complete: every level is full except possibly the last, which fills left to right.

valid complete shape             invalid shape

        3                              3
      /   \                          /   \
     7     5                        7     5
    / \   /                          \   /
   9  12 8                           9  8

The invalid tree leaves a gap before later positions. A heap operation must preserve completeness as well as priority order.

Order invariant

For a min-heap:

parent priority <= each child priority

For a max-heap:

parent priority >= each child priority

The relation is local but implies a global extreme at the root. In a min-heap, repeatedly following parents never increases priority, so no descendant can be smaller than the root.

Complete Shape

A complete tree has minimum possible height for its node count. With n > 0 nodes, height is floor(log2 n) when height counts edges.

Insertion that preserves shape has only one legal position: the next open position at the last level. Removal that preserves shape takes the final position. An array provides both locations directly, so no explicit tree navigation or links are required.

before insertion:            shape position for next node:

        4                            4
      /   \                        /   \
     8     7                      8     7
    / \                          / \   /
   12 15                        12 15 [next]

Array Layout

Store level order in a zero-based array:

tree:                         array:
          3                   [3, 7, 5, 9, 12, 8]
        /   \
       7     5
      / \   /
     9  12 8

For index i:

left(i)   = 2i + 1
right(i)  = 2i + 2
parent(i) = floor((i - 1) / 2), when i > 0

Leaf boundary

In a zero-based heap of size n, every index from floor(n/2) through n - 1 is a leaf. The final internal node is floor(n/2) - 1.

This boundary matters for bottom-up construction: leaves already satisfy heap order because they have no children.

Heap-array invariant

For an array-backed min-heap:

0 <= size <= capacity
indices [0, size) contain the complete tree in level order
for each child index i > 0:
    data[parent(i)] <= data[i]

Array position is structural, not stable identity. Sifting swaps elements, so a client should not retain an index as a permanent handle unless the implementation updates a separate handle-to-index map.

Heap Types

Min-heaps

The minimum appears at index 0. Min-heaps support “process the least priority next,” such as earliest deadline or shortest tentative distance when smaller numbers mean greater urgency.

Max-heaps

The maximum appears at index 0. Max-heaps support “process the greatest priority next,” such as the largest score or highest numeric priority.

The algorithms are symmetric. A generic implementation can accept a comparison function, but this chapter uses an integer min-heap to keep each structural step visible.

D-ary heaps

A d-ary heap gives each node up to d children. It reduces height to Theta(log_d n) but makes sift-down compare up to d children per level. Larger branching can benefit workloads with many priority decreases and cache-friendly arrays. Binary heaps are the simplest common case.

Heap Operations

Peek

The extreme value is at index 0, so peek is Theta(1). Empty peek must report failure.

Heap insertion

Insert at the final array position to preserve complete shape, then sift up while the new value outranks its parent.

Insert 2 into:

before: [3, 7, 5, 9, 12, 8]
append: [3, 7, 5, 9, 12, 8, 2]

The new value is at index 6; its parent is index 2:

swap 2 with 5: [3, 7, 2, 9, 12, 8, 5]
swap 2 with 3: [2, 7, 3, 9, 12, 8, 5]

Only the ancestor path can violate order. Unrelated subtrees remain valid.

Extraction

To remove the root while preserving complete shape:

save the root value;
move the final value to index 0;
reduce size;
sift down the replacement through the smaller child until order holds.

Extract minimum from:

[2, 7, 3, 9, 12, 8, 5]

Move final 5 to root:

[5, 7, 3, 9, 12, 8]       active size = 6

Children are 7 and 3. Swap with the smaller child:

[3, 7, 5, 9, 12, 8]

Order now holds. Comparing with only the left child would be wrong when the right child has higher priority.

Heap deletion

Deleting an arbitrary index i follows the same shape repair:

save data[i];
move the final active value into i;
reduce size;
choose sift-up if the replacement outranks its parent; otherwise sift-down.

The structural update is O(log n), but finding a value to delete by equality is O(n) because a heap is not a search tree. Efficient arbitrary deletion needs an external handle-to-index map.

Key updates

After changing priority at index i:

a decrease in a min-heap may require sift-up;
an increase in a min-heap may require sift-down.

A representation-independent implementation can compare with the parent: if violated upward, sift up; otherwise sift down.

If payload and priority are separate fields, swaps must move the complete item, not just its priority.

Heap Restoration

Sift-up invariant

Before each sift-up iteration:

both child subtrees are valid heaps;
every edge is ordered except possibly the edge between i and its parent;
swapping along that edge moves the only possible violation upward.

At most the tree height, O(log n), edges are crossed.

static void sift_up(MinHeap *heap, size_t i) {
    while (i > 0) {
        size_t parent = (i - 1) / 2;
        if (heap->data[parent] <= heap->data[i]) {
            break;
        }
        swap(&heap->data[parent], &heap->data[i]);
        i = parent;
    }
}

Sift-down invariant

Before each sift-down iteration:

the left and right subtrees are valid heaps;
the value at i may violate order with a child;
swapping with the smallest child restores the old root position without creating a sibling violation.

static void sift_down(MinHeap *heap, size_t i) {
    for (;;) {
        size_t left = 2 * i + 1;
        if (left >= heap->size) {
            break;
        }
        size_t right = left + 1;
        size_t smallest = left;
        if (right < heap->size &&
            heap->data[right] < heap->data[left]) {
            smallest = right;
        }
        if (heap->data[i] <= heap->data[smallest]) {
            break;
        }
        swap(&heap->data[i], &heap->data[smallest]);
        i = smallest;
    }
}

Calculating 2 * i + 1 can overflow for an arbitrary untrusted i. Here i < size and a successfully allocated array bounds practical size, but a hardened helper may use i <= (size - 2) / 2 to test whether a child exists before multiplication.

Heap Construction

Incremental construction

Starting empty and inserting n values performs up to one O(log n) sift-up per value, for O(n log n) total time.

Bottom-up heapify

If all values already occupy an array, treat leaves as one-node heaps and sift down internal nodes from right to left:

Change the input below, step through the comparisons and swaps, and keep both the tree and its array representation in view.

Enable JavaScript to use the heap-construction experiment.

for (size_t i = size / 2; i > 0; --i) {
    sift_down(heap, i - 1);
}

The reverse loop avoids unsigned underflow. When i == 1, it processes index 0, then stops.

Why heapify is linear

A loose bound says n nodes times O(log n) each, but most nodes are near the leaves and move only a few levels:

about n/2 nodes move 0 levels
about n/4 nodes move at most 1 level
about n/8 nodes move at most 2 levels
...

The work is bounded by:

n/4 * 1 + n/8 * 2 + n/16 * 3 + ... = O(n)

Bottom-up heap construction is therefore Theta(n).

Heap Program

This complete C17 dynamic min-heap implements construction, insertion, peek, extraction, deletion by index, and priority update.

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} MinHeap;

static void swap_int(int *a, int *b) {
    int temporary = *a;
    *a = *b;
    *b = temporary;
}

static bool heap_valid(const MinHeap *heap) {
    if (heap == NULL || heap->size > heap->capacity) {
        return false;
    }
    if ((heap->capacity == 0) != (heap->data == NULL)) {
        return false;
    }
    for (size_t child = 1; child < heap->size; ++child) {
        size_t parent = (child - 1) / 2;
        if (heap->data[parent] > heap->data[child]) {
            return false;
        }
    }
    return true;
}

void heap_init(MinHeap *heap) {
    heap->data = NULL;
    heap->size = 0;
    heap->capacity = 0;
}

void heap_destroy(MinHeap *heap) {
    free(heap->data);
    heap_init(heap);
}

static bool heap_reserve(MinHeap *heap, size_t capacity) {
    if (capacity <= heap->capacity) {
        return true;
    }
    if (capacity > SIZE_MAX / sizeof *heap->data) {
        return false;
    }
    int *new_data = realloc(heap->data,
                            capacity * sizeof *heap->data);
    if (new_data == NULL) {
        return false;
    }
    heap->data = new_data;
    heap->capacity = capacity;
    return true;
}

static void sift_up(MinHeap *heap, size_t index) {
    while (index > 0) {
        size_t parent = (index - 1) / 2;
        if (heap->data[parent] <= heap->data[index]) {
            break;
        }
        swap_int(&heap->data[parent], &heap->data[index]);
        index = parent;
    }
}

static void sift_down(MinHeap *heap, size_t index) {
    for (;;) {
        size_t left = index * 2 + 1;
        if (left >= heap->size) {
            return;
        }
        size_t right = left + 1;
        size_t smallest = left;

        if (right < heap->size &&
            heap->data[right] < heap->data[left]) {
            smallest = right;
        }
        if (heap->data[index] <= heap->data[smallest]) {
            return;
        }
        swap_int(&heap->data[index], &heap->data[smallest]);
        index = smallest;
    }
}

bool heap_build(MinHeap *heap, const int values[], size_t count) {
    assert(heap_valid(heap));
    if (count > 0 && values == NULL) {
        return false;
    }
    if (!heap_reserve(heap, count)) {
        return false;
    }
    if (count > 0) {
        memcpy(heap->data, values, count * sizeof *values);
    }
    heap->size = count;

    for (size_t i = heap->size / 2; i > 0; --i) {
        sift_down(heap, i - 1);
    }
    assert(heap_valid(heap));
    return true;
}

bool heap_insert(MinHeap *heap, int value) {
    assert(heap_valid(heap));
    if (heap->size == heap->capacity) {
        size_t next = heap->capacity == 0 ? 8 : heap->capacity * 2;
        if (next < heap->capacity || !heap_reserve(heap, next)) {
            return false;
        }
    }
    size_t index = heap->size++;
    heap->data[index] = value;
    sift_up(heap, index);
    assert(heap_valid(heap));
    return true;
}

bool heap_peek(const MinHeap *heap, int *out) {
    assert(heap_valid(heap));
    if (heap->size == 0 || out == NULL) {
        return false;
    }
    *out = heap->data[0];
    return true;
}

bool heap_extract(MinHeap *heap, int *out) {
    assert(heap_valid(heap));
    if (heap->size == 0 || out == NULL) {
        return false;
    }
    *out = heap->data[0];
    --heap->size;
    if (heap->size > 0) {
        heap->data[0] = heap->data[heap->size];
        sift_down(heap, 0);
    }
    assert(heap_valid(heap));
    return true;
}

bool heap_update(MinHeap *heap, size_t index, int value) {
    assert(heap_valid(heap));
    if (index >= heap->size) {
        return false;
    }
    int old = heap->data[index];
    heap->data[index] = value;
    if (value < old) {
        sift_up(heap, index);
    } else if (value > old) {
        sift_down(heap, index);
    }
    assert(heap_valid(heap));
    return true;
}

bool heap_remove_at(MinHeap *heap, size_t index, int *out) {
    assert(heap_valid(heap));
    if (index >= heap->size || out == NULL) {
        return false;
    }
    *out = heap->data[index];
    --heap->size;
    if (index < heap->size) {
        heap->data[index] = heap->data[heap->size];
        if (index > 0 &&
            heap->data[index] < heap->data[(index - 1) / 2]) {
            sift_up(heap, index);
        } else {
            sift_down(heap, index);
        }
    }
    assert(heap_valid(heap));
    return true;
}

int main(void) {
    MinHeap heap;
    heap_init(&heap);
    int values[] = {12, 3, 17, 8, 4, 11, 20, 6};

    if (!heap_build(&heap, values,
                    sizeof values / sizeof values[0]) ||
        !heap_insert(&heap, 2)) {
        heap_destroy(&heap);
        return EXIT_FAILURE;
    }

    int value;
    while (heap_extract(&heap, &value)) {
        printf("%d ", value);
    }
    putchar('\n'); /* 2 3 4 6 8 11 12 17 20 */
    heap_destroy(&heap);
    return EXIT_SUCCESS;
}

The final output is sorted because repeated extraction successively removes minima. That procedure leads to heap-based sorting, whose algorithmic analysis belongs in Sorting.

Priority Queues

A priority queue is the ADT; a heap is one implementation. Queue order uses arrival time alone, while priority-queue order uses a comparison key.

typedef struct {
    int priority;
    unsigned long sequence;
    Task payload;
} QueueItem;

For a stable priority policy, compare priority first and insertion sequence second. Among equal priorities, a lower sequence number leaves first.

Min-priority queues

Smaller keys leave first. Common interpretations include earliest deadline, smallest tentative cost, or next event time.

Max-priority queues

Larger keys leave first. Common interpretations include highest severity, largest bid, or greatest score.

Handles

Applications may need to change the priority of an existing item. Searching the heap by payload is linear. A handle table maps stable item IDs to current heap indices:

A handle is a stable external ID that lets a caller refer to an item even after heap swaps move that item to a different array index.

id -> heap index

Every swap must update both affected handle entries. The cross-structure invariant is:

position[heap[i].id] == i

This adds memory and mutation work but makes priority updates O(log n) after O(1) expected handle lookup.

Priority Contract

“Minimum” is obvious for plain integers, but a real priority queue stores records. The heap needs one comparison relation that answers which complete item should leave first.

typedef struct {
    int priority;
    unsigned long long sequence;
    int task_id;
} TaskItem;

static bool task_before(TaskItem a, TaskItem b) {
    if (a.priority != b.priority) {
        return a.priority < b.priority;
    }
    return a.sequence < b.sequence;
}

Here a lower number is more urgent. For equal priority, the earlier sequence is more urgent. task_before(a, b) is false when the records tie on both fields, and a parent is valid when its child does not come before it.

Do not spread assumptions such as a.priority < b.priority throughout heap code. Centralize comparison so sift-up, sift-down, validation, and tests all use the same rule. A max-priority queue then changes one relation rather than reversing several loops independently.

Comparison must be stable while an item is stored. If client code changes a priority field directly, the heap is immediately invalid. Expose an update operation that changes the field and restores order, or hide item storage behind the queue interface.

Payload ownership is separate from priority order. For payload pointers, define whether insertion transfers ownership, whether extraction transfers it back, and whether destruction releases items still queued. If a growing insertion fails, the queue should still own exactly the items it owned before the call, while the caller retains the rejected item.

Stable Ties

A heap is not naturally stable. Consider these arrivals:

(priority 2, task A)
(priority 1, task B)
(priority 2, task C)
(priority 2, task D)

Heap swaps may place C or D before A even though their numeric priorities are equal. If equal-priority tasks must retain arrival order, give every successful insertion a monotonically increasing sequence:

A -> (2, 0)
B -> (1, 1)
C -> (2, 2)
D -> (2, 3)

Lexicographic comparison produces extraction order:

B, A, C, D

The sequence should be assigned only when insertion is going to succeed. Consuming a sequence during failed allocation does not usually break correctness, but it makes histories harder to explain and can waste a bounded counter. If the counter can wrap, the contract needs an answer: reject further insertion before wrap, rebuild sequence numbers while preserving order, or use a sufficiently wide counter under a proven queue lifetime bound. Silently wrapping makes a new item appear older than existing ones.

Stable priority does not automatically imply fairness. A continuous stream of priority-0 tasks can starve priority-10 tasks forever. Aging, quotas, and deadline policy belong to the scheduler built above the priority queue; the heap faithfully implements only the comparator it is given.

Handle Invariant

An array index is a location, not an identity. If item 42 starts at index 6 and sifts to index 2, a remembered 6 points to some other item. A handle layer separates stable identity from changing position.

For dense IDs, an array can store positions. Use a sentinel such as SIZE_MAX for an item not currently present:

heap[0] = {id 8, priority 2}    position[8] = 0
heap[1] = {id 3, priority 5}    position[3] = 1
heap[2] = {id 5, priority 4}    position[5] = 2

Every swap is now one atomic logical update with three parts:

static void swap_items(HandleHeap *heap, size_t a, size_t b) {
    HeapItem temporary = heap->items[a];
    heap->items[a] = heap->items[b];
    heap->items[b] = temporary;
    heap->position[heap->items[a].id] = a;
    heap->position[heap->items[b].id] = b;
}

Updating only one position entry creates a table that sometimes locates the wrong item. A full validator checks both directions:

for every heap index i:
    position[heap[i].id] == i

for every present ID x:
    position[x] < size
    heap[position[x]].id == x

Deletion should mark the removed ID absent before returning. If numeric IDs may be reused, a stale caller handle can accidentally refer to a new item with the same ID. A generation handle stores both slot and generation, such as (slot 12, generation 4). Reusing slot 12 increments its generation, so a handle from generation 3 is rejected rather than silently targeting the replacement.

For sparse or string IDs, the position table may itself be a hash table. The complete operation cost then combines expected handle lookup with worst-case heap repair. The cross-structure invariant remains the same even though lookup storage changes.

Trace a priority decrease to see why every swap matters:

items:     [(id 8,p2), (id 3,p5), (id 5,p4), (id 9,p8)]
positions: 8->0, 3->1, 5->2, 9->3

decrease id 9 to p1
swap indices 3 and 1: positions 9->1, 3->3
swap indices 1 and 0: positions 9->0, 8->1

items:     [(id 9,p1), (id 8,p2), (id 5,p4), (id 3,p5)]
positions: 9->0, 8->1, 5->2, 3->3

The heap order and the position map must become valid together before the public operation returns.

Replacement Trace

Arbitrary removal is easy to describe but worth tracing because the final item can need either direction. Begin with:

index: 0  1  2  3  4  5  6
value: 2  6  3  9  8  7  4

Removing index 3 moves final value 4 into its place:

[2, 6, 3, 4, 8, 7]

4 is smaller than parent 6, so it must sift upward:

[2, 4, 3, 6, 8, 7]

By contrast, remove index 1 from the original heap. Final value 4 replaces 6:

[2, 4, 3, 9, 8, 7]

No repair is needed. If the replacement had been 10, it would not outrank the parent but could violate a child edge, so sift-down would be required.

A compact decision is:

if i > 0 and item[i] comes before item[parent(i)]: sift up
else:                                                   sift down

Only one direction is necessary. Before replacement, both the ancestor side and child subtrees were valid. The moved item can violate the edge above it or the edges below it, but not both under a consistent heap order.

D-ary Layout

For a zero-based d-ary heap with d >= 2:

parent(i)       = floor((i - 1) / d), for i > 0
child(i, k)     = d * i + k, for k in 1..d
first_child(i)  = d * i + 1

A node may have fewer than d children only at the final occupied portion of the array. Sift-down scans the existing child range and chooses the best one.

Increasing d shortens the height from about log2 n to log_d n. Sift-up performs roughly one parent comparison per level, so a larger d can help workloads dominated by upward priority changes. Sift-down compares as many as d children per level, giving roughly d log_d n child comparisons. That expression does not improve forever as d grows.

For example, with about one million elements:

binary height:  about 20 levels, at most 2 children checked per down level
4-ary height:   about 10 levels, at most 4 children checked per down level
16-ary height:  about 5 levels,  at most 16 children checked per down level

Actual performance also depends on item size, comparison cost, branch behavior, and cache lines. A four-ary heap is often a useful experiment, not a universal replacement for binary heaps.

Harden child arithmetic against overflow. Instead of forming d * i + 1 blindly, first establish that i <= (size - 2) / d when size >= 2. Then cap the final child’s index at size - 1.

Heapify Work

The earlier geometric argument establishes linear time. A more concrete accounting groups nodes by height above the leaves. In a binary heap:

fewer than n/2 nodes can move one or more levels;
fewer than n/4 nodes can move two or more levels;
fewer than n/8 nodes can move three or more levels;
and so on.

Count one unit each time a node descends one level. Fewer than n/2 nodes can cross a first edge, fewer than n/4 can cross a second edge, and so on. The total is bounded by:

n/2 + n/4 + n/8 + ... < n

This view avoids pretending that every internal node travels the full root height. Half of all positions are leaves and do no work. A quarter are parents of leaves and can move only one level. Only a tiny number near the root can move far.

Bottom-up heapify rearranges the input array. An API named heapify_in_place(values, n) should say that plainly. A constructor that promises to preserve caller input must first copy the values into owned storage and heapify the copy.

Batch Construction

Construction combines ownership and failure semantics. Three useful contracts are:

borrow-and-copy: caller keeps source; heap allocates and copies it
take-buffer:     heap takes a compatible allocation on success
in-place view:   caller owns storage; heap may reorder it but cannot grow

For borrow-and-copy, perform all fallible work before replacing an existing heap:

validate count * sizeof(item) for overflow;
allocate a temporary buffer;
copy source items into it;
heapify the temporary buffer;
swap the completed representation into the heap;
release the former backing buffer.

If allocation fails at step 2, both source and old heap remain unchanged. Heapify itself performs no allocation, so after the copy succeeds the remainder cannot fail for an ordinary fixed comparator.

Building handles adds another temporary structure. Initialize every position entry from the copied array, reject duplicate IDs, then heapify only through the handle-aware swap routine. Publish neither array until both invariants hold. This is a small transaction: prepare a complete new state, validate it, then commit it in constant time.

Reserve can be valuable before a known burst of insertions. It prevents array relocation during the burst but does not change sift costs. A fixed-capacity heap can reject insertion when full and gives a strict bound on memory use; an automatically growing heap offers convenience with an occasional linear allocation/copy pause.

Heap Oracles

A simple unsorted array makes a trustworthy test oracle. Insertion appends. Oracle extraction scans for the best item, removes it, and therefore costs linear time—but simplicity matters more than speed in a test.

After every random operation:

compare returned status and item with the oracle;
compare logical sizes;
verify every parent-child heap edge;
verify both directions of the handle map;
confirm that every active ID occurs exactly once;
for stable queues, compare equal-priority extraction order by sequence.

Generate insert, peek, extract, priority increase, priority decrease, and arbitrary deletion. Bias IDs toward existing and absent values, and sizes toward 0, 1, capacity boundaries, and the final internal node. Include many equal priorities because equality exercises tie policy rather than numeric heap order alone.

Repeated extraction from a min-heap must be nondecreasing under the complete comparator. That is a strong end-to-end check, but it is not enough by itself: a corrupted handle map can coexist with perfectly sorted extraction. Validate each invariant separately.

With a controlled allocator, force growth failure and batch-construction failure. The queue must retain its old size, items, positions, next sequence, and ownership state. Sanitizers then catch out-of-bounds child calculations and stale handle access that value comparisons may miss.

Heap Costs

Operation	Binary heap
Peek extreme	`Theta(1)`
Insert	`O(log n)` sifting; `Theta(n)` if growth relocates storage
Extract extreme	`Theta(log n)`
Update known index	`O(log n)`
Delete known index	`O(log n)`
Find arbitrary value	`Theta(n)`
Build incrementally	`O(n log n)`
Build bottom-up	`Theta(n)`
Storage	`Theta(n)`

The heap repair performed by insertion crosses at most one ancestor path and costs O(log n). A dynamic backing array adds a separate capacity cost: when it is full, a growing insertion may allocate a larger block and copy all n existing items, making that individual insertion Theta(n). With geometric growth, copying is amortized O(1) per insertion across a long sequence, so the overall amortized insertion bound remains O(log n). A fixed-capacity heap avoids relocation and retains the strict O(log n) worst-case update bound once constructed.

Insertion may perform no swaps when the appended item already obeys its parent relation, but the worst case crosses the full height.

Heap Applications

Scheduling

A heap repeatedly selects the next task by priority while allowing new tasks to arrive. Define tie-breaking so behavior is deterministic and fair where required.

Event simulation

Future events are keyed by timestamp. Extraction advances to the earliest event, whose processing may insert more future events.

Streaming selection

To retain the largest k values from a stream, maintain a min-heap of size k. The root is the smallest retained value and can be replaced when a larger candidate arrives.

Algorithm support

Priority queues support shortest-path, spanning-tree, compression, and best-first procedures. Their correctness and problem-specific use belong to Algorithms; this chapter supplies the heap representation and update contracts.

Choosing Priorities

Sorted priorities

A sorted array offers constant-time extreme access but linear insertion. A heap sacrifices full order to make insertion and extraction logarithmic.

Unsorted arrays

An unsorted array appends in constant time but needs a linear scan for the extreme. It can outperform a heap when insertion dominates and extraction is rare.

Balanced search trees

A balanced search tree supports extremes, arbitrary lookup, ordered traversal, and ranges in logarithmic time. A heap is more compact and often faster when only one extreme matters.

Buckets

If priorities lie in a small integer range, an array of queues can provide faster bounded-priority operations. Heap comparisons are more general.

Heap Hazards

Assuming sorted order

Only parent-child order is guaranteed. The array [2,7,3,9,12,8,5] is a valid min-heap even though 7 > 3.

Wrong child choice

Sift-down must swap with the higher-priority child. Choosing the left child merely because it exists can leave the right child above a larger parent.

Wrong repair direction

After arbitrary replacement, always sifting down misses a value that should move upward. Compare with its parent or use the known direction of the priority change.

Stale indices

Every sift swap changes item positions. External indices become stale unless maintained as explicit handles.

Unsigned reverse loops

for (size_t i = n/2 - 1; i >= 0; --i) never terminates because an unsigned value is always nonnegative. Count from n/2 while testing i > 0, then process i - 1.

Partial item swaps

Swapping only priorities separates them from payloads. Swap the complete record and update any external position map.

Ambiguous equality

Equal priorities satisfy heap order but do not imply FIFO extraction. Add a sequence tie-breaker if stable behavior is required.

Heap Validation

Test structural boundaries and repair directions:

empty peek and extraction;
singleton extraction;
insert new minimum and a non-moving maximum;
extract when the replacement needs several downward swaps;
sift-down where the right child is smaller;
update requiring sift-up and update requiring sift-down;
delete root, final item, and an interior item;
build from sorted, reverse-sorted, equal, and random arrays;
repeated extraction produces nondecreasing values;
allocation failure during growth leaves content unchanged.

Validate the parent relation after every randomized update rather than checking only the root.

Heap Essentials

A binary heap combines complete-tree shape with local parent-child priority order.
Complete shape permits a gap-free array representation and logarithmic height.
Peek is constant time; insertion and extraction repair one root-to-leaf path.
Sift-up moves one possible violation toward the root; sift-down moves it toward leaves.
Arbitrary deletion and key update choose repair direction from the replacement relation.
Bottom-up heapify is linear because most nodes are close to leaves.
A priority queue is an interface; a heap is a compact general-purpose implementation.
Stable handles and stable tie-breaking require additional metadata and invariants.

Heap Problems

Heap Invariants

State the shape and order invariants of a min-heap.
Derive parent and child formulas for zero-based storage.
Why is arbitrary search linear in a heap?
Distinguish a heap from a priority queue.

Heap Repairs

Insert 4,9,7,2,8,1,6 into an empty min-heap and record every swap.
Extract three minima from the resulting heap and record every replacement and child comparison.
Bottom-up heapify [14,3,12,9,7,1,8,2], processing internal nodes in the actual order.
Delete an interior element whose replacement must sift upward.

Restoration Failures

Construct a heap where always choosing the left child breaks sift-down.
Diagnose a heapify loop written with unsigned i >= 0.
Explain how swapping priority without payload corrupts a task queue.
Create an operation sequence that invalidates a client-stored heap index.

Heap Variants

Convert the reference implementation into a max-heap.
Add a comparator so one implementation stores arbitrary item records.
Add stable ID handles and maintain an ID-to-index table through every swap.
Implement a fixed-capacity heap with strict worst-case allocation behavior.
Implement a d-ary heap and make d a construction parameter.

Priority Choices

Choose between a heap, sorted vector, and unsorted vector for a workload with one million inserts followed by one extraction.
Define tie-breaking for a hospital task queue without claiming that priority alone ensures fairness.
Design ownership rules for heap items containing dynamically allocated payloads.
Compare binary and four-ary heaps for frequent decrease-priority operations.

Construction and Meld

Prove bottom-up heap construction is Theta(n) using a summation by node height.
Maintain the median of a stream using one max-heap and one min-heap.
Implement a meldable priority queue and compare why a binary heap cannot generally meld in logarithmic time.