Binary min-heaps: complete shape and safe operations

What you will learn

A binary min-heap keeps a smallest key at its root while preserving a complete binary-tree shape. This introductory lesson explains how that shape gives zero-based array positions and how insertion and extract-min repair the order. By the end, you should be able to draw the shape from an array, check heap order, and trace safe sift-up and sift-down operations.

Prerequisite: the companion lesson on binary-tree structure and traversals, plus integer arrays, initialized storage, conditions, loops, functions and return values. A key is the integer value used for comparisons. A min-heap is useful when the next item needed is a smallest key, as in a priority queue. This is a data-structure heap, unrelated to the dynamically allocated memory region also called a heap. No dynamic allocation is used here.

Two rules that must hold together

Shape rule: every level is full except possibly the last, and the last level fills from left to right without gaps. This is a complete binary tree. A complete tree need not be perfect (all levels full) or full (every internal node has exactly two children). For example, six nodes give a complete tree whose node at index 2 has only a left child.

Order rule: each parent's key is less than or equal to each existing child's key. Following the parent chain shows that the root is no greater than any stored key. Equal keys are allowed. For example, [2, 5, 4, 9, 7] is a min-heap even though 5 comes before 4 in the array. Siblings need not be ordered. The array is not generally sorted.

A binary search tree uses comparisons against a node to constrain whole left and right subtrees. A min-heap does not impose that left/right partition: both children may be greater than the root, and left-subtree keys may be larger or smaller than right-subtree keys. The heap property alone cannot tell you which one of the two subtrees contains an arbitrary requested key. Equal-priority items have no promised first-in-first-out order. This lesson stores keys only, so no identity or insertion time exists to enforce stability.

Complete shape gives implicit array positions

Store nodes in level order: root first, then its children left to right, then the next level left to right. Capacity is 7; count is the number of active elements, between 0 and 7. Exactly indices 0 through count - 1 are active. Any initialized values beyond them are unused storage, not nodes. Unlike arbitrary node-index links used for general trees, this representation stores no child-link fields and permits no gaps among active positions.

For an active index i:

• If i > 0, parent index is (i - 1) / 2, using integer division. Index 0 is the root and has no parent; never apply the parent formula as a root-parent lookup.
• Candidate left child is 2 * i + 1; candidate right child is 2 * i + 2. Read either only if its index is less than count.
• A computed position is not automatically an existing child. Capacity alone is not the active-child test.

For five keys [2, 5, 4, 9, 7], level 0 has index 0 containing 2; level 1 has indices 1 and 2 containing 5 and 4; level 2 has indices 3 and 4 containing 9 and 7. Positions 5 and 6 are absent, so the last level is partial but left-packed. Index 2's candidate children 5 and 6 are not active. Index 4's parent is (4 - 1) / 2 = 1, since integer division of 3 by 2 gives 1. This is a shape calculation, not a comparison of stored keys.

Worked trace 1: insertion and sift-up

Start with those five keys. To insert 1, first append at index count = 5, then set count to 6. Appending preserves complete shape. Only the chain from the new leaf toward the root can now violate heap order.

Each swap moves the new small key one level upward. Stop when its parent is already no greater, or when the key reaches the root. Do not swap on equality in this implementation. With a full heap, reject insertion before appending; index 7 does not exist. With an empty heap, insertion writes index 0 and needs no sift-up.

Worked trace 2: extract-min and sift-down

Extract-min returns and removes the root key, 1. Save that key before changing storage. Remove the last active position, place its key 4 at the root, and reduce count from 6 to 5. Removing the last node preserves shape; removing the root without this replacement would leave a gap.

Choosing the smaller existing child matters: swapping 4 with left child 5 would leave root 5 above child 2, which violates heap order. If child keys tie, this program chooses the left child. That local tie choice does not promise stable extraction of equal-key items. When the heap initially has one node, decrementing count makes it zero; return the saved key without reading a replacement or any child. Empty extraction fails before reading index 0.

Worked trace 3: a node with only a left child

Begin with the valid seven-key heap [1, 4, 2, 7, 8, 3, 9]. Extract 1 and move last key 9 to index 0, leaving six active keys [9, 4, 2, 7, 8, 3]. Compare children 4 and 2; swap with index 2 to obtain [2, 4, 9, 7, 8, 3]. Now the moving index is 2: left index 5 exists and contains 3, but right index 6 equals count and is absent. Swap with the left child to obtain [2, 4, 3, 7, 8, 9], then stop at leaf index 5. Never read a[6] as a child after the removal, even though it remains within physical capacity and may still hold an old value.

C syntax and storage contract

The complete C11 program below uses enum { CAP = 7 }; for an integer constant. struct groups fields; typedef supplies the type names Heap and Result. A Heap contains an array a and integer count. A Result contains separate ok and value fields. ok = 1 means success; ok = 0 means ignore the initialized value field. Therefore 0, -1, INT_MIN and INT_MAX can all be real keys without being mistaken for failure. The last two names, from <limits.h> in the author tests, mean the smallest and largest representable int.

Heap h = {{2, 5, 4, 9, 7, 0, 0}, 5}; initializes the inner array and then count in field order. h.count selects a field of a record. &h is the address of the live record. A parameter Heap *h receives a pointer to that record, so its updates change the caller's heap. h->count selects a field through the pointer; it means (*h).count, where unary * accesses the pointed-to record. Binary * in 2 * i instead means multiplication. const Heap *h allows the validator to inspect, but not change, the record through that pointer. NULL is the null-pointer constant provided here by <stdio.h>; it points to no record.

Callers must provide NULL or a pointer to one live Heap whose entire array and count are initialized. The validator handles NULL, invalid counts and broken order; it cannot detect dangling pointers, uninitialized objects or forged addresses. The int a[] function parameter adjusts to a pointer to the caller's array, without copying it. swap_values is an internal helper: its callers must supply two active indices. It exchanges values through a temporary instead of arithmetic on keys, preventing overflow at int limits.

= assigns; == compares for equality. <, >, <= are integer comparisons. ! negates a truth condition. || is short-circuit OR, so a true left condition skips the right one. && is short-circuit AND, so a false left condition skips the right one. These rules protect NULL field access and the missing right-child read. Division / on nonnegative integers discards the fractional part. if selects a guarded block; while repeats while its condition is nonzero; while (1) repeats until a break exits that loop. return leaves the function, optionally returning an int or Result record by value. A function declared void returns no value; (void) in main declares no parameters. Braces group statements or initialize records, square brackets index arrays, and semicolons end simple statements. Local variables such as i and p hold positions, not keys.

#include <stdio.h> declares the standard output function and supplies NULL. printf prints the string in quotes; %d formats an int, and \n ends the line. main returns 0 on a successful run or 1 on a demonstration failure. This program uses initialized fixed storage and performs no input, allocation or recursion.

Complete bounded C11 program

#include <stdio.h>

enum { CAP = 7 };

typedef struct {
    int a[CAP];
    int count;
} Heap;

typedef struct {
    int ok;
    int value;
} Result;

int valid_heap(const Heap *h) {
    if (h == NULL || h->count < 0 || h->count > CAP) {
        return 0;
    }
    int i = 1;
    while (i < h->count) {
        int p = (i - 1) / 2;
        if (h->a[p] > h->a[i]) {
            return 0;
        }
        i = i + 1;
    }
    return 1;
}

void swap_values(int a[], int x, int y) {
    int saved = a[x];
    a[x] = a[y];
    a[y] = saved;
}

int insert(Heap *h, int value) {
    if (!valid_heap(h) || h->count == CAP) {
        return 0;
    }
    int i = h->count;
    h->a[i] = value;
    h->count = h->count + 1;
    while (i > 0) {
        int p = (i - 1) / 2;
        if (h->a[p] <= h->a[i]) {
            break;
        }
        swap_values(h->a, p, i);
        i = p;
    }
    return 1;
}

Result extract_min(Heap *h) {
    Result result = {0, 0};
    if (!valid_heap(h) || h->count == 0) {
        return result;
    }
    result.ok = 1;
    result.value = h->a[0];
    h->count = h->count - 1;
    if (h->count == 0) {
        return result;
    }
    h->a[0] = h->a[h->count];
    int i = 0;
    while (1) {
        int left = 2 * i + 1;
        if (left >= h->count) {
            break;
        }
        int right = left + 1;
        int smaller = left;
        if (right < h->count && h->a[right] < h->a[left]) {
            smaller = right;
        }
        if (h->a[i] <= h->a[smaller]) {
            break;
        }
        swap_values(h->a, i, smaller);
        i = smaller;
    }
    return result;
}

int main(void) {
    Heap h = {{2, 5, 4, 9, 7, 0, 0}, 5};
    if (!insert(&h, 1)) {
        return 1;
    }
    Result first = extract_min(&h);
    if (!first.ok) {
        return 1;
    }
    printf("minimum: %d\n", first.value);
    printf("heap:");
    int i = 0;
    while (i < h.count) {
        printf(" %d", h.a[i]);
        i = i + 1;
    }
    printf("\n");
    return 0;
}

Exact output:

minimum: 1
heap: 2 5 4 9 7

Why the guarded operations are safe

valid_heap first establishes 0 <= count <= CAP. It then starts at index 1, so every parent calculation has i > 0, and checks every active parent-child edge. A packed prefix already fixes complete shape; the validator need not traverse links. Short-circuit checks reject a null pointer before reading its fields. Invalid input makes both operations fail without changing any field.

Insertion writes only when count is below capacity. At most index 6 is appended, and sift-up moves strictly toward index 0. Extraction reads the root only from a nonempty valid heap. After decrement, a positive count is the old last index, so that replacement read is inside the array. In sift-down the moving index always remains active. It checks left existence before reading a child, and tests right existence before comparing that child. Each swap moves strictly down, eventually reaching a leaf. With capacity 7, even computing the candidate left index at leaf 6 gives only 13, safely representable as int; the program does not index there. These bounded arithmetic arguments are not a promise that unbounded index formulas cannot overflow.

The count determines membership. After extract-min, the unused old last slot need not be cleared, and this implementation leaves stale data there. No operation treats it as active. It also neither subtracts keys for comparisons nor adds them for swapping, so extreme int keys are safe.

Here O(n) describes an upper growth bound proportional to the number of active keys (linear growth). O(log n) describes a bound proportional to the number of levels in a complete tree: roughly one extra level when the node count doubles. These are growth categories, not exact instruction counts.

The usual heap algorithms use at most one root-to-leaf path, giving O(log n) sift work in a variable-size complete tree. Our teaching functions additionally run a full O(n) validator before each operation, making their overall variable-n cost O(n). With the literal fixed bound 7 every run is bounded by a constant; quoting standard O(log n) for the whole defensive function would hide the validation work. Formal complexity proofs, bottom-up heap construction and heapsort are outside this introduction.

A bounded analogy

Imagine seven labelled seats arranged in tree-shaped rows. People fill seats in level order without gaps. Each person holds a number; a parent seat must hold no larger a number than either occupied child seat. An arrival takes the next available seat, then numbers exchange upward if needed. For a departure from the root, the last occupied seat supplies its number and comparisons repair the order downward.

This analogy models occupied shape and number swaps only. People are not pointers, free seats are not nodes, and swapping equal-priority records is not a promise about which person leaves first. In the code the keys move, while the index relationships remain fixed.

Key box

• A binary min-heap requires both complete shape and parent <= child order.
• Root index 0 holds a minimum when count is positive.
• Use (i - 1) / 2 only for i > 0; guard child indices against count.
• Append then sift up; save root, replace from last, then sift down with the smaller existing child.
• Duplicate keys are valid; neither sorted array order nor stable tie order is promised.
• Status is separate from key data. Full insertion and empty extraction must be handled before access.

Two additional exercises

1. Insert 3 into [2, 5, 4, 9, 7]. Try the trace before reading the answer. Append at index 5: [2, 5, 4, 9, 7, 3]. Parent 2 holds 4, so swap: [2, 5, 3, 9, 7, 4]. Parent 0 holds 2 <= 3, so stop; count is 6.
2. Start with an initialized empty heap, insert 0 twice, and extract three times. Both insertions succeed; the second equal key stays at index 1. Results are {1, 0}, {1, 0}, then {0, 0}. Only the first two values are valid payloads. Final count is 0; no stability claim can be inferred from two indistinguishable keys.

Scope and next step

This is a foundation bridge for GATE CS data structures. It does not teach heapsort, heap construction proofs, all priority-queue implementations or the full syllabus. The questions below are original practice, not previous-year questions. No exam-year relabelling is implied. Hindi is learning support, not a claim that GATE CS has an official Hindi question paper.

Six original single-correct questions

1. A packed zero-based heap has count = 6 and capacity 7. Which children of index 2 are active?

A. Both indices 5 and 6 B. Only left child index 5 C. Only right child index 6 D. No children

2. Which statement about the active array [2, 9, 3] is correct?

A. It is invalid because the left child is larger than the right child. B. It is a min-heap, so searching for 9 must use a BST left/right partition. C. It is a min-heap, so its array is sorted in nondecreasing order. D. It is a min-heap: both children are at least 2, with no sibling-order requirement.

3. Using the lesson algorithm, insert 1 into [3, 6, 5, 9]. What is the final active array?

A. [1, 3, 5, 9, 6] B. [1, 3, 5, 6, 9] C. [3, 1, 5, 9, 6] D. [3, 6, 5, 9, 1]

4. Extract the minimum once from [1, 4, 2, 7, 8, 3, 9] using the lesson algorithm. Which final active array results?

A. [4, 7, 2, 9, 8, 3] B. [2, 4, 9, 7, 8, 3] C. [2, 4, 3, 7, 8, 9] D. [1, 4, 2, 7, 8, 3]

5. A valid Heap has count = CAP = 7. What does insert(&h, -1) do in the provided code?

A. Overwrites the root because -1 has high priority. B. Returns 0 and changes neither count nor any array slot. C. Writes -1 at index 7 and then sifts upward. D. Returns 1 but silently removes a largest key.

6. A valid one-element heap contains INT_MIN. What does extract_min return, and what is the new count?

A. {0, 0}, count 1, because INT_MIN is an error sentinel. B. {1, 0}, count 0, because removing the last key clears its value. C. {1, INT_MIN}, count 1, because extraction reads without removing. D. {1, INT_MIN}, count 0, with no replacement-child access.

Worked option feedback

1. B

A is incorrect: 6 equals count, so it is unused even though within capacity.

B is correct: left = 2 * 2 + 1 = 5 < 6; right = 6 is not < 6.

C is incorrect: index 6 is absent; the left-packed shape cannot skip existing index 5.

D is incorrect: index 5 is active and is the left child of index 2.

2. D

A is incorrect: 9 > 3 is permitted; heap order compares a parent with each child.

B is incorrect: a heap gives no BST subtree partition; here the left child 9 is greater than root 2.

C is incorrect: 9 followed by 3 is a decrease, so this valid heap is not a sorted array.

D is correct: positions 0, 1, 2 give complete shape and the two required comparisons are 2 <= 9 and 2 <= 3.

3. A

A is correct: append at 4, swap with parent 1 (key 6), then parent 0 (key 3), giving [1, 3, 5, 9, 6].

B is incorrect for this algorithm: it is a valid heap, but it additionally swaps siblings 9 and 6, which sift-up never does.

C is incorrect: this is the intermediate state after one swap; parent 3 is still greater than child 1.

D is incorrect: this only appends; key 1 remains below parent 6, violating heap order.

4. C

A is incorrect: always choosing the left child leaves root 4 above child 2; the smaller existing child must be selected.

B is incorrect: the first swap is done, but index 2 still has key 9 above its only child 3 at index 5.

C is correct: save 1, move 9 to root, swap with 2 at index 2, then with its left child 3 at index 5.

D is incorrect: this just discards the last position; minimum 1 remains and was not removed.

5. B

A is incorrect: the capacity guard returns before any assignment, regardless of the proposed key.

B is correct: valid_heap reads only; count == CAP triggers return 0 before append or swaps.

C is incorrect: the seven-element array has indices 0 through 6; the guard prevents an out-of-bounds write.

D is incorrect: this insertion has no replacement policy; a full heap rejects the operation.

6. D

A is incorrect: no int key is reserved as an error sentinel; failure is represented by ok = 0.

B is incorrect: the root is saved before count changes, so the returned payload remains INT_MIN, not zero.

C is incorrect: extract_min decrements count, removing the single active element.

D is correct: ok becomes 1, the root key is copied, count becomes 0, and the early return avoids a replacement read.