Self-checkedTier 1 25 min readpds.binary-heap

Binary heaps and heap operations

A complete binary tree stored in an array so that every parent is at least as large as its children (max-heap) or at most as large (min-heap). Learn the index arithmetic, insertion by sifting up, deleting the root by sifting down, deleting any position, the height and leaf facts, where the minimum of a max-heap can hide, and how many different heaps exist.

Why it exists

Many programs keep a changing collection and keep asking for its largest (or smallest) item: the next job to run, the closest unvisited city, the two smallest weights to merge. An unsorted array finds the maximum in $\Theta(n)$ . A sorted array finds it at once but needs $\Theta(n)$ to insert. A balanced search tree does both in $O(\log n)$ but is heavy (pointers, rotations) and orders far more than is needed. A binary heap orders only as much as is needed: the best item is always at the root, and inserting or removing it costs $O(\log n)$ . It needs no pointers at all, because a complete binary tree can be stored in a plain array with simple index arithmetic.

Prerequisites

Trees and binary trees Arrays and indexing

Precise definitions

Complete binary tree. Every level is full except possibly the last, and the last level is filled from the left (see the trees page). For a given number of nodes $n$ there is exactly one such shape.
Max-heap. A complete binary tree in which the key of every node is greater than or equal to the keys of its children. Equivalent: every node is at least as large as all of its descendants. A min-heap is the mirror image (every node $\le$ its children). With equal keys the rule uses $\ge$ or $\le$ , so ties are allowed. Statements below about the smallest key, the $k$ -th largest key and the number of heaps assume distinct keys.
A heap is not a search tree. Nothing is said about the left child versus the right child, so a heap is not sorted: neither the keys within a level nor the levels relative to each other need be in order, and its inorder traversal means nothing.
Array form (1-based, the usual form in textbooks and GATE). Store the tree level by level in $a[1..n]$ . The root is $a[1]$ . The children of position $i$ are at $2i$ (left) and $2i + 1$ (right), and the parent of position $i$ is at $\lfloor i/2 \rfloor$ . Position $i$ has a left child iff $2i \le n$ , and a right child iff $2i + 1 \le n$ . Position $i$ is on depth $\lfloor \log_2 i \rfloor$ .
Array form (0-based). Children of $i$ are $2i + 1$ and $2i + 2$ ; the parent is $\lfloor (i - 1)/2 \rfloor$ . Always check which one a question uses.
Height and leaves (height counted in edges, as everywhere on this site). A heap with $n$ nodes has height $\lfloor \log_2 n \rfloor$ . The leaves are exactly the positions $\lfloor n/2 \rfloor + 1, \ldots, n$ , so there are $\lceil n/2 \rceil$ leaves and $\lfloor n/2 \rfloor$ internal nodes. At most $\lceil n / 2^{h+1} \rceil$ nodes have height $h$ . The heights of all the nodes add up to $n - (\text{number of 1 bits of } n) \le n - 1$ .
Operations and costs.

Operation	How	Cost
Find the maximum (max-heap)	read $a[1]$	$O(1)$
Insert	put the key at position $n + 1$ , then sift up (swap with the parent while it is larger)	$O(\log n)$
Extract the maximum	save $a[1]$ , move $a[n]$ to $a[1]$ , set $n \leftarrow n - 1$ , then sift down (swap with the larger child while that child is larger)	$O(\log n)$
Delete the key at position $i$	move $a[n]$ to position $i$ , shrink, then sift up or down (at most one of the two moves anything)	$O(\log n)$
Increase or decrease a key at position $i$	change it, then sift up or down	$O(\log n)$
Search for an arbitrary key	scan the array (siblings are not ordered)	$\Theta(n)$
Find the minimum of a max-heap	it is in one of the $\lceil n/2 \rceil$ leaves, so check them all	$\Theta(n)$
Build a heap from $n$ arbitrary keys	sift down from position $\lfloor n/2 \rfloor$ to 1 (next page)	$\Theta(n)$

Exact counts for the code on this page (counting one key comparison per child test, so two per level when a node has two children). Inserting into a heap that then has $n$ nodes takes at most $\lfloor \log_2 n \rfloor$ comparisons and swaps. Extracting from a heap of $n \ge 2$ nodes takes at most $\lfloor \log_2 (n - 1) \rfloor$ swaps and at most $2 \lfloor \log_2 (n - 1) \rfloor$ comparisons (the comparison bound is reached for most $n$ but not when $n - 1$ is a power of 2; checked for $n \le 14$ , where it is missed for $n = 3, 5, 9$ , and for $n = 9$ the worst case is 5 comparisons, not 6). Questions normally only ask for $O(\log n)$ .
How many heaps. The number of different max-heaps on $n$ distinct keys is $h(n) = \binom{n - 1}{L}\, h(L)\, h(n - 1 - L)$ with $h(0) = h(1) = 1$ , where $L$ is the size of the left subtree of the complete tree with $n$ nodes (the largest key is the root; choose which of the remaining $n - 1$ keys go left). The values are $1, 1, 2, 3, 8, 20, 80, 210, 896, 3360$ for $n = 1, \ldots, 10$ .
Rank and depth. The $k$ -th largest key of a max-heap is on depth at most $k - 1$ , because all of its ancestors are larger. So the second largest key is at position 2 or 3, and the third largest within positions 2 to 7.

How it works

Insertion: place at the end, sift up

The new key goes to the first free position, so the shape stays complete. That can break the rule only between the new node and its parent. Swap them while the parent is smaller. Each swap moves the new key one level up, and the rule stays true everywhere except, possibly, between the moving key and its new parent. So the loop only has to look one level higher each time, and it stops at the root at the latest: at most $\lfloor \log_2 n \rfloor$ steps, where $n$ is the size after the insertion.

Inserting into a max-heap: place at the end, sift up

Real run

C source

1#include <stdio.h>

3static void swap(int *x, int *y) {

4 int t = *x;

5 *x = *y;

6 *y = t;

9/* a[1..n] holds a max-heap; position 0 is unused */

10void insert(int a[], int *n, int x) {

11 int i = ++*n;

12 a[i] = x;

13 while (i > 1 && a[i / 2] < a[i]) {

14 swap(&a[i / 2], &a[i]);

15 i /= 2;

16 }

17}

Array a (the heap is positions 1 to n; each node's children are at 2i and 2i + 1)

State

n = 6, swaps so far = 0

Blue = the position this step is working on, amber = a position being compared, red = positions just swapped, green = finished or in its final place, a filled blue cell = a value just placed, faded = not part of the structure at this step.

Step 1

A max-heap of 6 keys. Insert 60 and then 15.

1 / 13

The starting heap 50, 30, 40, 10, 20, 35 (positions 1 to 6) and the two inserts, 60 and then 15, are set up by hidden driver code. insert() and swap() are the exact code that runs. Produced by: real execution: every array, stack, matrix and list in the picture is read from the running program's memory at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog

Extracting the maximum: move the last key to the root, sift down

The maximum is the root. To keep the tree complete, the last key is moved to the root and the size drops by one. Now only the root can be wrong. Compare it with both children, swap with the larger one if that one is bigger (the larger child is the only safe one to lift above its sibling), and repeat one level lower. Sifting down needs up to two comparisons per level, so at most about $2\lfloor \log_2 n \rfloor$ in all (the exact bound is given under Operations and costs).

Extracting the maximum: move the last key to the root, sift down

Real run

C source

1#include <stdio.h>

3static void swap(int *x, int *y) {

4 int t = *x;

5 *x = *y;

6 *y = t;

9/* a[1..n] is a max-heap except possibly at position i */

10void sift_down(int a[], int n, int i) {

11 for (;;) {

12 int l = 2 * i, r = 2 * i + 1, big = i;

13 if (l <= n && a[l] > a[big]) big = l;

14 if (r <= n && a[r] > a[big]) big = r;

15 if (big == i) break;

16 swap(&a[i], &a[big]);

17 i = big;

18 }

19}

21int extract_max(int a[], int *n) {

22 int top = a[1];

23 a[1] = a[*n];

24 --*n;

25 sift_down(a, *n, 1);

26 return top;

27}

Array a (the heap is positions 1 to n; each node's children are at 2i and 2i + 1)

State

n = 8, swaps so far = 0

Step 1

A max-heap of 8 keys. Extract the maximum twice.

1 / 17

The heap 60, 30, 50, 15, 20, 35, 40, 10 is set up by hidden driver code, which then calls extract_max() twice. sift_down(), extract_max() and swap() are the exact code that runs. Produced by: real execution: every array, stack, matrix and list in the picture is read from the running program's memory at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog

Worked examples

EX 1Index arithmetic: parents, children and leaves

Easy

#include <stdio.h>
 
int main(void) {
    int n = 11;
    printf(" i parent  left right leaf?\n");
    for (int i = 1; i <= n; i++) {
        int l = 2 * i, r = 2 * i + 1;
        if (i == 1) printf("%2d %6s ", i, "-");
        else printf("%2d %6d ", i, i / 2);
        if (l <= n) printf("%5d ", l);
        else printf("%5s ", "-");
        if (r <= n) printf("%5d ", r);
        else printf("%5s ", "-");
        printf("%s\n", l > n ? "yes" : "no");
    }
    return 0;
}

Output:

 i parent  left right leaf?
 1      -     2     3 no
 2      1     4     5 no
 3      1     6     7 no
 4      2     8     9 no
 5      2    10    11 no
 6      3     -     - yes
 7      3     -     - yes
 8      4     -     - yes
 9      4     -     - yes
10      5     -     - yes
11      5     -     - yes

Reading it. With $n = 11$ , a position is a leaf when $2i > n$ , which first happens at $i = 6 = \lfloor 11/2 \rfloor + 1$ . So the leaves are $6, \ldots, 11$ ( $\lceil 11/2 \rceil = 6$ of them) and the internal nodes are $1, \ldots, 5$ . Position 5 has two children (10 and 11), the last position 11 is a right child, and the root has no parent. The height is $\lfloor \log_2 11 \rfloor = 3$ : position 11 is on depth 3.

EX 2Is this array a heap?

Easy

#include <stdio.h>
 
/* 0 if a[1..n] obeys the rule, otherwise the first position whose parent breaks it */
static int first_bad(const int a[], int n, int max_heap) {
    for (int i = 2; i <= n; i++) {
        int p = a[i / 2], c = a[i];
        if (max_heap ? p < c : p > c) return i;
    }
    return 0;
}
 
int main(void) {
    int A[] = {0, 90, 70, 80, 40, 60, 50, 30};
    int B[] = {0, 90, 70, 80, 40, 60, 85, 30};
    int C[] = {0, 10, 20, 15, 30, 25};
    printf("A: max-heap test %d, min-heap test %d\n", first_bad(A, 7, 1), first_bad(A, 7, 0));
    printf("B: max-heap test %d, min-heap test %d\n", first_bad(B, 7, 1), first_bad(B, 7, 0));
    printf("C: max-heap test %d, min-heap test %d\n", first_bad(C, 5, 1), first_bad(C, 5, 0));
    return 0;
}

Output:

A: max-heap test 0, min-heap test 2
B: max-heap test 6, min-heap test 2
C: max-heap test 2, min-heap test 0

Reading it. 0 means the array obeys the rule, any other number is the first position whose parent breaks it. $A = 90, 70, 80, 40, 60, 50, 30$ is a max-heap (every parent $\ge$ its children) but not a min-heap, because the parent 90 is larger than its child 70 at position 2. $B$ differs from $A$ in position 6, which now holds 85 under the parent 80 (position 3), so it is not a max-heap; position 6 is the first violation (85 is larger than its parent 80). $C = 10, 20, 15, 30, 25$ is a min-heap: $10 \le 20, 15$ and $20 \le 30, 25$ . Note that checking a heap means checking every parent against its children, not that the array is sorted.

EX 3A min-heap: six insertions, then two extractions

Medium

#include <stdio.h>
 
static void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}
 
/* min-heap in a[1..n] */
static void insert(int a[], int *n, int x) {
    int i = ++*n;
    a[i] = x;
    while (i > 1 && a[i / 2] > a[i]) {
        swap(&a[i / 2], &a[i]);
        i /= 2;
    }
}
 
static int extract_min(int a[], int *n) {
    int top = a[1];
    a[1] = a[(*n)--];
    int i = 1;
    for (;;) {
        int l = 2 * i, r = 2 * i + 1, s = i;
        if (l <= *n && a[l] < a[s]) s = l;
        if (r <= *n && a[r] < a[s]) s = r;
        if (s == i) break;
        swap(&a[i], &a[s]);
        i = s;
    }
    return top;
}
 
static void show(const int a[], int n) {
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    printf("\n");
}
 
int main(void) {
    int keys[6] = {10, 4, 15, 2, 8, 1};
    int a[16], n = 0;
    for (int k = 0; k < 6; k++) {
        insert(a, &n, keys[k]);
        printf("insert %2d: ", keys[k]);
        show(a, n);
    }
    int m = extract_min(a, &n);
    printf("extract %d: ", m);
    show(a, n);
    m = extract_min(a, &n);
    printf("extract %d: ", m);
    show(a, n);
    return 0;
}

Output:

insert 10: 10
insert  4: 4 10
insert 15: 4 10 15
insert  2: 2 4 15 10
insert  8: 2 4 15 10 8
insert  1: 1 4 2 10 8 15
extract 1: 2 4 15 10 8
extract 2: 4 8 15 10

Reading it. Every line is the whole array after one operation, read from position 1.

Inserting 2 puts it at position 4; its parent (position 2) holds 10, so they swap; then the parent at position 1 holds 4, so they swap again: the new key reaches the root.
Inserting 8 goes to position 5, its parent (position 2) holds 4, which is smaller, so nothing moves.
Inserting 1 goes to position 6, swaps with 15 (position 3) and with 2 (position 1).
extract 1: the last key 15 replaces the root, then it sinks: its children are 4 and 2, the smaller is 2, so they swap; at position 3 it has no children (the size is 5). Result 2 4 15 10 8.
extract 2: 8 replaces the root, the children are 4 and 15, it swaps with 4; at position 2 the children are position 4 (key 10) and none, and $8 \le 10$ , so it stops. Result 4 8 15 10.

The code is the max-heap code with both comparisons reversed. A question about a min-heap is solved the same way with "larger" and "smaller" exchanged.

EX 4Where can the minimum of a max-heap be?

GATE level

#include <stdio.h>
 
#define N 7
 
static int a[N + 1], used[N + 1];
static int heaps, pos_of_1[N + 1], pos_of_2[N + 1];
 
static int is_max_heap(void) {
    for (int i = 2; i <= N; i++)
        if (a[i / 2] < a[i]) return 0;
    return 1;
}
 
static void gen(int k) {
    if (k > N) {
        if (is_max_heap()) {
            heaps++;
            for (int i = 1; i <= N; i++) {
                if (a[i] == 1) pos_of_1[i]++;
                if (a[i] == 2) pos_of_2[i]++;
            }
        }
        return;
    }
    for (int v = 1; v <= N; v++) {
        if (used[v]) continue;
        used[v] = 1;
        a[k] = v;
        gen(k + 1);
        used[v] = 0;
    }
}
 
int main(void) {
    gen(1);
    printf("max-heaps of the keys 1..%d: %d\n", N, heaps);
    printf("position of key 1:");
    for (int i = 1; i <= N; i++) printf(" %d:%d", i, pos_of_1[i]);
    printf("\nposition of key 2:");
    for (int i = 1; i <= N; i++) printf(" %d:%d", i, pos_of_2[i]);
    printf("\n");
    return 0;
}

Output:

max-heaps of the keys 1..7: 80
position of key 1: 1:0 2:0 3:0 4:20 5:20 6:20 7:20
position of key 2: 1:0 2:0 3:0 4:20 5:20 6:20 7:20

Reading it. The program tries all $7! = 5040$ arrangements of the keys 1 to 7 and keeps the ones that are max-heaps: there are 80. The smallest key 1 never sits at the root or at positions 2 and 3, only at the leaves $4, 5, 6, 7$ , and equally often at each of them (20 times each). The reason (distinct keys): a node that has a child is larger than that child, so a node with a child cannot hold the smallest key. Hence the minimum of a max-heap is always in one of the $\lceil n/2 \rceil$ leaves, but nothing says which one, and finding it takes $\Theta(n)$ time (one comparison fewer than the number of leaves is enough and necessary). For $n = 7$ the key 2 also lands only on leaves, but that is special to this size and is not a rule.

EX 5Height and the number of nodes of each height

Medium

#include <stdio.h>
 
static int height(int i, int n) {
    int h = 0;
    while (2 * i <= n) {
        i *= 2;
        h++;
    }
    return h;
}
 
int main(void) {
    int n = 20, count[8] = {0};
    for (int i = 1; i <= n; i++) count[height(i, n)]++;
    printf("n = %d, height of the heap = %d\n", n, height(1, n));
    for (int h = 0; h <= height(1, n); h++) {
        int bound = (n + (1 << (h + 1)) - 1) / (1 << (h + 1)); /* ceil(n / 2^(h+1)) */
        printf("height %d: %d node%s (bound %d)\n", h, count[h], count[h] == 1 ? "" : "s", bound);
    }
    return 0;
}

Output:

n = 20, height of the heap = 4
height 0: 10 nodes (bound 10)
height 1: 5 nodes (bound 5)
height 2: 3 nodes (bound 3)
height 3: 1 node (bound 2)
height 4: 1 node (bound 1)

Reading it. A heap of $n = 20$ nodes has height $\lfloor \log_2 20 \rfloor = 4$ . The last level holds only the 5 nodes at positions 16 to 20; there are $\lceil 20/2 \rceil = 10$ leaves (positions 11 to 20, on two levels, all of height 0). The bound $\lceil n / 2^{h+1} \rceil$ is exact for heights 0, 1, 2 and 4 here and is not reached at height 3, where only one node (the left child of the root, position 2) has height 3 although the bound allows two: it is an upper bound. These counts are why building a heap is cheap: most nodes have small height, and a sift down from a node costs at most its height (next page).

EX 6How many different heaps?

GATE level

#include <stdio.h>
 
#define MAXN 12
 
static int bin(int n, int k) {
    long r = 1;
    for (int i = 1; i <= k; i++) r = r * (n - k + i) / i;
    return (int)r;
}
 
/* size of the left subtree of a complete tree with n nodes */
static int left_size(int n) {
    if (n <= 1) return 0;
    int h = 0;
    while ((2 << h) - 1 < n) h++;       /* h = depth of the last level = floor(log2 n) */
    int last = n - ((1 << h) - 1);      /* nodes on the last level */
    int half = 1 << (h - 1);            /* the last level has room for 2^h nodes, half of them on the left */
    return (half - 1) + (last < half ? last : half);
}
 
static long heaps(int n) {
    if (n <= 1) return 1;
    int l = left_size(n);
    return (long)bin(n - 1, l) * heaps(l) * heaps(n - 1 - l);
}
 
static int a[MAXN], used[MAXN];
static long brute;
 
static void gen(int k, int n) {
    if (k > n) {
        for (int i = 2; i <= n; i++)
            if (a[i / 2] < a[i]) return;
        brute++;
        return;
    }
    for (int v = 1; v <= n; v++) {
        if (used[v]) continue;
        used[v] = 1;
        a[k] = v;
        gen(k + 1, n);
        used[v] = 0;
    }
}
 
int main(void) {
    for (int n = 1; n <= 10; n++) {
        if (n <= 8) {
            brute = 0;
            gen(1, n);
            printf("n = %2d  formula %5ld  brute force %5ld\n", n, heaps(n), brute);
        } else {
            printf("n = %2d  formula %5ld\n", n, heaps(n));
        }
    }
    return 0;
}

Output:

n =  1  formula     1  brute force     1
n =  2  formula     1  brute force     1
n =  3  formula     2  brute force     2
n =  4  formula     3  brute force     3
n =  5  formula     8  brute force     8
n =  6  formula    20  brute force    20
n =  7  formula    80  brute force    80
n =  8  formula   210  brute force   210
n =  9  formula   896
n = 10  formula  3360

Reading it. The recurrence says: the largest key is the root; of the other $n - 1$ keys choose the $L$ that go into the left subtree, where $L$ is fixed by the shape (the left subtree size of a complete tree), and build a heap on each side independently. For $n = 7$ the tree is perfect with $L = 3$ : $\binom{6}{3} \cdot h(3) \cdot h(3) = 20 \cdot 2 \cdot 2 = 80$ , the number the previous example found by trying everything. For $n = 4$ : $L = 2$ , $\binom{3}{2} \cdot h(2) \cdot h(1) = 3 \cdot 1 \cdot 1 = 3$ . The program also checks the formula against a complete search for $n \le 8$ . The count of min-heaps on the keys $1..n$ is the same.

EX 7Deleting a key from the middle: up or down?

GATE level

#include <stdio.h>
 
static void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}
 
static void sift_up(int a[], int i) {
    while (i > 1 && a[i / 2] < a[i]) {
        swap(&a[i / 2], &a[i]);
        i /= 2;
    }
}
 
static void sift_down(int a[], int n, int i) {
    for (;;) {
        int l = 2 * i, r = 2 * i + 1, big = i;
        if (l <= n && a[l] > a[big]) big = l;
        if (r <= n && a[r] > a[big]) big = r;
        if (big == i) break;
        swap(&a[i], &a[big]);
        i = big;
    }
}
 
/* delete the key at position i of the max-heap a[1..*n] */
static void delete_at(int a[], int *n, int i) {
    a[i] = a[(*n)--];
    if (i <= *n) {
        sift_up(a, i);
        sift_down(a, *n, i);
    }
}
 
static void show(const int a[], int n) {
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    printf("\n");
}
 
int main(void) {
    int a[16] = {0, 100, 50, 90, 20, 30, 80, 85};
    int n = 7;
    show(a, n);
    delete_at(a, &n, 4);
    show(a, n);
    return 0;
}

Output:

100 50 90 20 30 80 85
100 85 90 50 30 80

Reading it. The heap is 100 50 90 20 30 80 85. Deleting the key at position 4 (value 20) moves the last key, 85, into position 4 and shrinks the heap to 6 keys. Position 4 has no children now (its children would be positions 8 and 9), so no sift down is possible, but 85 is larger than its new parent 50 (position 2), so it sifts up one step, and stops under 100 because $100 \ge 85$ . The result is 100 85 90 50 30 80. This is the point of the example: the replacement key comes from another branch of the tree, so it may need to move up as well as down. The code tries both, and at most one of them does anything.

Cheat box

Heap = complete binary tree + heap property (max-heap: parent $\ge$ children). Not a search tree, not sorted.
1-based array: children $2i$ , $2i + 1$ ; parent $\lfloor i/2 \rfloor$ . 0-based: $2i + 1$ , $2i + 2$ , $\lfloor (i-1)/2 \rfloor$ .
$n$ nodes: height $\lfloor \log_2 n \rfloor$ ; leaves are positions $\lfloor n/2 \rfloor + 1 \ldots n$ ( $\lceil n/2 \rceil$ of them).
Max at the root: $O(1)$ . Insert (sift up) and extract (last key to the root, sift down): $O(\log n)$ . Search: $\Theta(n)$ .
Minimum of a max-heap: in a leaf; $\Theta(n)$ to find. 2nd largest at position 2 or 3. $k$ -th largest at depth $\le k - 1$ .
Delete at position $i$ : last key goes there; sift up or down.
Distinct heaps on $n$ keys: $1, 1, 2, 3, 8, 20, 80, 210, 896, 3360$ for $n = 1..10$ .
Sift down compares with both children and swaps with the larger (max-heap) or smaller (min-heap).

Traps and GATE patterns

Connections

Builds on

Trees and binary trees Arrays and indexing

Unlocks

Heap sortuses Huffman codingPrerequisite of Huffman codinguses Kruskal and Primuses Dijkstra's algorithmPrerequisite of Dijkstra's algorithmuses Trees and binary treesuses Counting binary treesuses Binary search treescontrasts with Priority queues and building a heapPrerequisite of Priority queues and building a heapuses Graph representationsuses AVL trees and rotationscontrasts with

Across subjects

Heap sortuses Dijkstra's algorithmuses Huffman codinguses

Within this subject

Priority queues and building a heapuses Binary search treescontrasts-with Counting binary treesuses

A heap is the complete binary tree of the trees page stored in an array. It contrasts with the binary search tree: a weaker rule (parent versus children only), so it cannot search quickly ( $\Theta(n)$ , against $O(h)$ for a BST), but it is simpler and its shape is always balanced. The next page, priority queues and building a heap, builds a heap in $\Theta(n)$ and sorts with it. The number of different heaps on $n$ distinct keys (the ways to put the keys into the one complete shape) is a counting argument like those on the counting page, although there the objects counted are tree shapes. The heap is used by heapsort, by Dijkstra's algorithm and by Huffman coding.

PYQs

19 previous year questions from your book. I re-solved each one myself (12 by running or simulating, 7 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2025 · Set 2 · MCQ · 2 marksQ1 · page 146 of the book

A meld operation on two instances of a data
structure combines them into one single instance of
the same data structure. Consider the following
data structures:
P: Unsorted doubly linked list with pointers to the
head node and tail node of the list.
Q: Min-heap implemented using an array.
R: Binary Search Tree.
Which ONE of the following options gives the
worst-case time complexities for meld operation on
instances of size n of these data structures?

(a)P: θ(1), Q: θ(n), R: θ(n)
(b)P: θ(1), Q: θ(nlogn), R: θ(n)
(c)P: θ(n), Q: θ(nlogn), R: θ(n2)
(d)P: θ(1), Q: θ(n), R: θ(nlogn)

GATE 2023 · MCQ · 2 marksQ2 · page 146 of the book

Let A be a priority queue for maintaining a set
of elements. Suppose A is implemented using a
max-heap data structure. The operation Extract-
Max(A) extracts and deletes the maximum
element from A. The operation Insert(A, key)
inserts a new element key in A. The properties
of a max-heap are preserved at the end of each
of these operations. When A contains n
elements, which one of the following statements
about the worst case running time of these two
operations is TRUE?

(a)Both Extract-Max(A) and Insert(A, key) run in O(1)
(b)Both Extract-Max(A) and Insert(A, key) run in O(log n)
(c)Extract-Max(A) runs in O(1) whereas Insert(A, key) runs in O(n)
(d)Extract-Max(A) runs in O(1) whereas Insert(A, key) runs in O(log n).

GATE 2023 · MCQQ3 · page 146 of the book

Which one of the following sequences when
stored in an array at locations A[1], ..., A[10]
forms a max-heap?

(a)23, 17, 10, 6, 13, 14, 1, 5, 7, 12
(b)23, 17, 14, 7, 13, 10, 1, 5, 6, 12
(c)23, 17, 14, 6, 13, 10, 1, 5, 7, 15
(d)23, 14, 17, 1, 10, 13, 16, 12, 7, 5

GATE 2015 · Set 1 · MCQ · 2 marksQ8 · page 147 of the book

An algorithm performs (logN)1/2 find operations, N
insert operations, (logN)1/2 delete operations, and
(logN)1/2 decrease-key operations on a set of data
items with keys drawn from a linearly ordered set .
For a delete operation, a pointer is provided to the
record that must be deleted. For the decrease-key
operation, a pointer is provided to the record that
has its key decreased. Which one of the following
data structures is the most suited for the algorithm
to use, if the goal is to achieve the best total
asymptotic
complexity
considering
all
the
operations?

(a)Unsorted array
(b)Min - heap
(c)Sorted array
(d)Sorted doubly linked list ALGORITHMS Check Out Our Gate Courses & Secure Your Dream Rank !

GATE 2022Q6 · page 67 of the book

Suppose a binary search tree with 1000 distinct
elements is also a complete binary tree. The tree is
stored using the array representation of binary heap
trees. Assuming that the array indices start with 0,
the 3rd largest element of the tree is stored at index

GATE 2021 · Set 2Q7 · page 67 of the book

Let H be a binary min-heap consisting of n
elements implemented as an array. What is the
worst case time complexity of an optimal algorithm
to find the maximum element in H '?

(a)Θ(n)
(b)Θ(1)
(c)Θ(logn)
(d)Θ(n log n)

GATE 2016 · MCQQ18 · page 68 of the book

An operator delete(i) for a binary heap data structure
is to be designed to delete the item in the i-th node.
Assume that the heap is implemented in an array and
i refers to the i-th index of the array. If the heap tree
has depth d (number of edges on the path from the
root to the farthest leaf), then what is the time
complexity to re-fix the heap efficiently after the
removal of the element?

(a)O(1)
(b)O(d) but not O(1)
(c)O(2d) but not O(d)
(d)O(d2d) but not O(2d)

GATE 2016 · Set 2Q19 · page 68 of the book

A complete binary min-heap is made by including
each integer in [1, 1023] exactly once. The depth of a
node in the heap is the length of the path from the root
of the heap to that node. Thus, the root is at depth 0.
The maximum depth at which integer 9 can appear is

GATE 2015 · Set 3Q22 · page 69 of the book

Consider the following array of elements. 〈89, 19,
50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉. The minimum
number of interchanges needed to convert it into a
max-heap is

(a)4
(b)5
(c)2
(d)3

GATE 2015 · Set 1Q23 · page 69 of the book

Consider a max heap, represented by the array: 40,
30, 20, 10, 15, 16, 17, 8, 4. Now consider that a
value 35 is inserted into this heap. After insertion,
the new heap is

(a)40, 30, 20, 10, 15, 16, 17, 8, 4, 35
(b)40, 35, 20, 10, 30, 16, 17, 8, 4, 15
(c)40, 30, 20, 10, 35, 16, 17, 8, 4, 15
(d)40, 35, 20, 10, 15, 16, 17, 8, 4, 30

GATE 2014 · Set 2Q28 · page 70 of the book

A priority queue is implemented as a Max-Heap.
Initially, it has 5 elements. The level-order traversal
of the heap is: 10, 8, 5, 3, 2. Two new elements 1
and 7 are inserted into the heap in that order. The
level-order traversal of the heap after the insertion
of the elements is:

(a)10, 8, 7, 3, 2, 1, 5
(b)10, 8, 7, 2, 3, 1, 5
(c)10, 8, 7, 1, 2, 3, 5
(d)10, 8, 7, 5, 3, 2, 1

GATE 2011 · MCQQ34 · page 71 of the book

A max-heap is a heap where the value of each parent
is greater than or equal to the values of its children.
Which of the following is a max-heap?

(a)DATA STRUCTURE
(b)
(c)
(d)
(a)0
(b)1
(c)(n - 1)/2
(d)n – 1

GATE 2009Q38 · page 72 of the book

Consider a binary max-heap implemented using an
array. Which one of the following array represents
a binary max-heap?

(a){25, 12, 16, 13, 10, 8, 14 }
(b){(25, 14, 13, 16, 10, 8, 12}
(c){25, 14, 16, 13, 10, 8, 12}
(d){25, 14, 12, 13, 10, 8, 16}

GATE 2009Q39 · page 72 of the book

Consider a binary max-heap implemented using an
array. What is the content of the array after two delete
operations on

(a){14, 13. 12. 10, 8}
(b){14, 12,13, 8, 10}
(c){14, 13, 8, 12, 10}
(d){14, 13, 12, 8, 10}

year not read yetQ45 · page 73 of the book

Consider the process of inserting an element into a
Max Heap, where the Max Heap is represented by an
array. Suppose we perform a binary search on the
path from the new leaf to the root to find the position
for the newly inserted element, the number of
comparisons performed is:

(a)Θ(log2 n)
(b)Θ(log2 log2 n)
(c)Θ(n)
(d)Θ(n log2 n)

GATE 2006Q46 · page 73 of the book

In a binary max heap containing n numbers, the
smallest element can be found in time

(a)O(n)
(b)O(log n)
(c)O(log log n)
(d)O(1)

GATE 2006Q47 · page 73 of the book

A 3-ary max heap is like a binary max heap, but
instead of 2 children, nodes have 3 children. A 3-ary
heap can be represented by an array as follows: The
root is stored in the first location, A[0], nodes in the
next level, from left to right, are stored from A[1] to
A[3]. The nodes from the second level of the tree
from left to right are stored from A[4] onward. An
item x can be inserted into a 3-ary heap containing n
items by placing x in the location A[n] and pushing
it up the tree to satisfy the heap property.
Which one of the following is a valid sequence of
elements in an array representing a 3-ary max heap?

(a)1, 3, 5, 6, 8, 9
(b)9, 6, 3, 1, 8, 5
(c)9, 3, 6, 8, 5, 1
(d)9, 5, 6, 8, 3, 1

GATE 2006Q48 · page 73 of the book

A 3-ary max heap is like a binary max heap, but
instead of 2 children, nodes have 3 children. A 3-ary
heap can be represented by an array as follows: The
DATA STRUCTURE

root is stored in the first location, A[0], nodes in
the next level, from left to right, are stored from
A[1] to A[3]. The nodes from the second level of
the tree from left to right are stored from A[4]
onward. An item x can be inserted into a 3-ary
heap containing n items by placing x in the
location A[n] and pushing it up the tree to satisfy
the heap property.
Suppose the elements 7, 2, 10 and 4 are inserted, in
that order, into the valid 3-ary max heap found in
the previous question . Which one of the following
is the sequence of items in the array representing
the resultant heap?

(a)10, 7, 9, 8, 3, 1, 5, 2, 6, 4
(b)10, 9, 8, 7, 6, 5, 4, 3, 2, 1
(c)10, 9, 4, 5, 7, 6, 8, 2, 1, 3
(d)10, 8, 6, 9, 7, 2, 3, 4, 1, 5

GATE 2005Q50 · page 74 of the book

A priority queue is implemented as a Max-Heap.
Initially, it has 5 elements. The level-order
traversal of the heap is:10, 8, 5, 3, 2
Two new elements 1 and 7 are inserted into the
heap in that order. The level-order traversal of the
heap after the insertion of the elements is:

(a)10, 8, 7, 5, 3, 2, 1
(b)10, 8, 7, 2, 3, 1, 5
(c)10, 8, 7, 1, 2, 3, 5
(d)10, 8, 7, 3, 2, 1, 5

Self-check

Question 1

A max-heap has 25 elements. How many leaves does it have, at which positions, and what is its height?

Show answer

$\lceil 25/2 \rceil = 13$ leaves, at positions $13, \ldots, 25$ ( $\lfloor 25/2 \rfloor + 1 = 13$ ). The height is $\lfloor \log_2 25 \rfloor = 4$ .

Question 2

Insert 65 into the max-heap stored as 70 50 60 30 40 20 10 (positions 1 to 7). Write the new array.

Show answer

65 goes to position 8; its parent is position 4 (30), swap; now at position 4, its parent is position 2 (50), swap; now at position 2, its parent is the root 70, which is larger, stop. The array is 70 65 60 50 40 20 10 30.

Question 3

Which of 1 3 2 6 5 4 7 and 1 3 2 6 1 4 7 is a min-heap?

Show answer

The first. In the second, position 5 holds 1 under the parent at position 2, which holds 3: the parent is larger, so the min-heap rule fails. In the first, $1 \le 3, 2$ ; $3 \le 6, 5$ ; $2 \le 4, 7$ .

Question 4

In a max-heap with 100 distinct keys, in which positions can the second largest key be?

Show answer

Only position 2 or position 3. A key at depth 2 or more has at least two ancestors, and all of them are larger, so it can be at best the third largest. Only the two children of the root can have just one larger key above them.

Question 5

What is the minimum number of comparisons that is enough to find the smallest key in a max-heap of $n$ keys, in the worst case, and why can it not be fewer?

Show answer

It is in one of the $\lceil n/2 \rceil$ leaves, and finding the minimum of $m$ unordered keys takes $m - 1$ comparisons, so $\lceil n/2 \rceil - 1$ , which is $\Theta(n)$ . Fewer would leave some leaf never compared, and that leaf could be the smaller one.

Revision card

One-screen revision

Max-heap: complete binary tree, parent $\ge$ children. Array, 1-based: children $2i$ , $2i + 1$ , parent $\lfloor i/2 \rfloor$ .
Height $\lfloor \log_2 n \rfloor$ ; leaves positions $\lfloor n/2 \rfloor + 1 \ldots n$ .
Insert: at the end, sift up. Extract: last key to the root, sift down with the larger child. Both $O(\log n)$ . Find-max $O(1)$ . Search $\Theta(n)$ .
Delete at $i$ : last key to $i$ , sift up or down.
Minimum of a max-heap: in a leaf, $\Theta(n)$ to find. Second largest at 2 or 3.
Heaps on $n$ keys: $1, 1, 2, 3, 8, 20, 80, 210, 896, 3360$ . A heap is not sorted.

References

·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., Chapter 6 Heapsort (6.1 Heaps, 6.2 Maintaining the heap property, 6.5 Priority queues)

Verification

The two animations replay real runs of the shown insert() and extract_max()/sift_down() functions: every array and the tree drawn from it are read from the running program, and the test suite checks that the live part is a valid max-heap whenever an operation has finished, that every swap step changes exactly two cells and that the final arrays are the expected ones. All C programs on this page are compiled with -Wall -Wextra -Werror and run by npm run verify:c. The facts below were checked exhaustively by scripts/enum-checks/heaps.py (every permutation of 1..n for n up to 9, and every n up to 399 for the counting statements): the number of heaps and the recurrence for it, that the minimum of a max-heap is always in a leaf, the number of leaves, nodes of each height, the sum of the heights, the worst-case swaps and comparisons of insertion and extraction, and that the k-th largest key lies on depth at most k - 1. The textbook section numbers were written from memory and have NOT been checked against the book. The prose and the GATE-pattern claims have NOT yet had a human textbook check (the independent second pass is described at the end of these notes). SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand (long C programs were not re-read line by line: they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Binary search trees

Priority queues and building a heap