Self-checkedTier 1 30 min readpds.heap-applications

Priority queues and building a heap

The priority queue as an abstract data type and why a heap implements it best; building a heap from an arbitrary array in linear time (and why repeated insertion costs n log n and gives a different array); heapsort with its cost and its instability; and the standard uses (the k largest keys, merging k sorted lists).

Why it exists

The binary heap is a structure; this page is about what it is for. A priority queue is the abstract data type that serves items in order of priority instead of order of arrival: an operating system picks the highest-priority job, an event simulation picks the earliest event, a shortest-path search picks the closest unvisited vertex. The heap implements all of that in $O(\log n)$ per operation. Two further questions follow and both are GATE favourites: how fast can a heap be built from $n$ keys that are already in an array (answer: $\Theta(n)$ , not $n \log n$ ), and what happens if you keep removing the maximum (you get heapsort).

Prerequisites

Binary heaps and heap operations

Precise definitions

Priority queue (abstract data type). A collection of items, each with a key (the priority), supporting insert, find-max (or find-min), and extract-max (or extract-min). Often also increase-key or decrease-key and delete. It says nothing about how the items are stored. In a max priority queue the largest key is served first; in a min priority queue the smallest.
A priority queue is not a queue. A queue serves by arrival order. A priority queue serves by key, and gives no promise about items with equal keys (they need not come out in arrival order).
Implementations of a priority queue with $n$ items.

Implementation	Insert	Find-max	Extract-max
Unsorted array or list	$O(1)$	$O(n)$	$O(n)$
Sorted array (max at the end)	$O(n)$	$O(1)$	$O(1)$
Sorted linked list (max at the head)	$O(n)$	$O(1)$	$O(1)$
Binary search tree	$O(h)$	$O(h)$	$O(h)$ ( $h$ up to $n - 1$ )
Balanced search tree (such as AVL)	$O(\log n)$	$O(\log n)$	$O(\log n)$
Binary heap	$O(\log n)$	$O(1)$	$O(\log n)$

Increase-key or decrease-key in a binary heap: change the key at a known position and sift up or down, $O(\log n)$ . Finding the item first by its key takes $\Theta(n)$ unless a separate table records where each item sits (this is how a decrease-key based Dijkstra's algorithm is implemented; many programs instead push a duplicate entry and ignore the stale one).
Building a heap (heapify), bottom-up (Floyd). Given $a[1..n]$ in any order, run sift_down(a, n, i) for $i = \lfloor n/2 \rfloor, \lfloor n/2 \rfloor - 1, \ldots, 1$ . The positions $\lfloor n/2 \rfloor + 1$ to $n$ are leaves, which are already heaps of one node. When position $i$ is handled, both its subtrees are heaps, so one sift down makes the tree rooted at $i$ a heap.
Cost of bottom-up building. A sift down from a node of height $h$ does at most $h$ swaps (and at most $2h$ comparisons). There are at most $\lceil n / 2^{h+1} \rceil$ nodes of height $h$ . The heights of all nodes add up to $n - (\text{number of 1 bits of } n) \le n - 1$ . So the whole build performs at most $n - 1$ swaps and $2(n - 1)$ comparisons: $\Theta(n)$ . (Equivalent analytic form: for $h \le \log_2 n$ we have $\lceil n/2^{h+1} \rceil \le n/2^h$ , so the total is at most $\sum_{h=0}^{\lfloor \log_2 n \rfloor} h \cdot n/2^h \le n \sum_{h \ge 0} h/2^h = 2n = O(n)$ .)
Building by repeated insertion. Insert $a[1], a[2], \ldots, a[n]$ one at a time with sift up. The $i$ -th insertion costs up to the depth $\lfloor \log_2 i \rfloor$ , so the worst case is $\sum_{i=1}^{n} \lfloor \log_2 i \rfloor = (n + 1)\lfloor \log_2 n \rfloor - 2^{\lfloor \log_2 n \rfloor + 1} + 2 = \Theta(n \log n)$ swaps (reached when the keys arrive in increasing order). The two methods can produce different heaps from the same array.
Heapsort. Build a max-heap; then for $last = n, n - 1, \ldots, 2$ : swap $a[1]$ with $a[last]$ (the maximum is now in its final place), shrink the heap by one, and sift down the new root. The array ends sorted in increasing order. A min-heap sorts in decreasing order the same way.
Heapsort properties. Time: the build is $\Theta(n)$ and the $n - 1$ sift downs cost $O(\log n)$ each, so $O(n \log n)$ ; since every comparison sort needs $\Omega(n \log n)$ comparisons in the worst case, the worst case is $\Theta(n \log n)$ . Space: $O(1)$ extra (in place). Not stable. Not adaptive: a sorted input costs as much as a random one. Exam answer: best, average and worst case are all $\Theta(n \log n)$ .
The $k$ largest of $n$ keys. Keep a min-heap of size $k$ . For each key, if it is larger than the root, replace the root and sift down. Time $O(n \log k)$ , space $O(k)$ . The $k$ keys come out unsorted (sorting them costs another $O(k \log k)$ ). (Alternative: build a max-heap of all $n$ keys in $\Theta(n)$ and extract $k$ times: $O(n + k \log n)$ , but that needs all the keys at once and $\Theta(n)$ space, so it does not work on a stream.)
Merging $k$ sorted lists of $N$ keys in total: keep a min-heap with one entry per list (its current head). Repeatedly output the root and replace it by the next key of the same list. Time $O(N \log k)$ (assuming every list is non-empty, so $N \ge k$ ), space $O(k)$ besides the output.

How it works

Building a heap bottom-up

The animation runs build_heap on an array of 10 keys. Watch which positions are fixed (5, 4, 3, 2, 1, in that order, always from the last internal node up to the root), and how few swaps are needed: nodes near the bottom have little room to sink. The picture uses the same sift_down as the animations on the binary-heap page.

Building a heap in place: sift down from n / 2 to 1

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}

21void build_heap(int a[], int n) {

22 for (int i = n / 2; i >= 1; i--) {

23 sift_down(a, n, i);

24 }

25}

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

State

n = 10, 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

An arbitrary array of 10 keys, viewed as a complete binary tree. Positions 6 to 10 are leaves and are already heaps of size 1.

1 / 26

The array 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 (positions 1 to 10) is set up by hidden driver code. build_heap(), sift_down() 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

Sorting with the heap

After the build, the largest key is at position 1. Swapping it with the last live position puts it in its final place and shrinks the heap; the key that arrived at the root is probably small and sinks. Green cells are in their final place (the root is outlined in blue after the build because it holds the maximum, but it is not final until it is swapped).

Heapsort: build a max-heap, then move the maximum to the end again and again

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}

21void heap_sort(int a[], int n) {

22 for (int i = n / 2; i >= 1; i--) {

23 sift_down(a, n, i);

24 }

25 for (int last = n; last >= 2; last--) {

26 swap(&a[1], &a[last]);

27 sift_down(a, last - 1, 1);

28 }

29}

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

State

n = 7, swaps so far = 0

Step 1

An arbitrary array of 7 keys. First it is turned into a max-heap.

1 / 30

The array 5, 3, 8, 1, 9, 2, 7 (positions 1 to 7) is set up by hidden driver code. heap_sort(), sift_down() and swap() are the exact code that runs. Green cells are in their final sorted place. 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 1The same workload on three implementations

Easy

#include <stdio.h>
 
#define N 1000
 
static long cmp_count;
static int next_key(void) {
    static unsigned s = 12345;
    s = s * 1103515245u + 12345u;
    return (int)((s >> 8) % 100000);
}
 
/* 1. unsorted array: insert at the end, extract by scanning for the maximum */
static int ua[N], un;
static void u_insert(int x) { ua[un++] = x; }
static int u_extract(void) {
    int best = 0;
    for (int i = 1; i < un; i++) {
        cmp_count++;
        if (ua[i] > ua[best]) best = i;
    }
    int top = ua[best];
    ua[best] = ua[--un];
    return top;
}
 
/* 2. array kept sorted in increasing order: insert by shifting, extract the last element */
static int sa[N], sn;
static void s_insert(int x) {
    int i = sn++;
    while (i > 0) {
        cmp_count++;
        if (sa[i - 1] <= x) break;
        sa[i] = sa[i - 1];
        i--;
    }
    sa[i] = x;
}
static int s_extract(void) { return sa[--sn]; }
 
/* 3. binary max-heap in h[1..hn] */
static int h[N + 1], hn;
static void h_insert(int x) {
    int i = ++hn;
    h[i] = x;
    while (i > 1) {
        cmp_count++;
        if (h[i / 2] >= h[i]) break;
        int t = h[i / 2]; h[i / 2] = h[i]; h[i] = t;
        i /= 2;
    }
}
static int h_extract(void) {
    int top = h[1];
    h[1] = h[hn--];
    int i = 1;
    for (;;) {
        int l = 2 * i, r = 2 * i + 1, big = i;
        if (l <= hn) { cmp_count++; if (h[l] > h[big]) big = l; }
        if (r <= hn) { cmp_count++; if (h[r] > h[big]) big = r; }
        if (big == i) break;
        int t = h[i]; h[i] = h[big]; h[big] = t;
        i = big;
    }
    return top;
}
 
int main(void) {
    int keys[N];
    for (int i = 0; i < N; i++) keys[i] = next_key();
    long total[3] = {0, 0, 0}, ins[3] = {0, 0, 0};
    unsigned long check[3] = {0, 0, 0};
 
    cmp_count = 0;
    for (int i = 0; i < N; i++) u_insert(keys[i]);
    ins[0] = cmp_count;
    for (int i = 0; i < N; i++) check[0] = check[0] * 31 + (unsigned long)u_extract();
    total[0] = cmp_count;
 
    cmp_count = 0;
    for (int i = 0; i < N; i++) s_insert(keys[i]);
    ins[1] = cmp_count;
    for (int i = 0; i < N; i++) check[1] = check[1] * 31 + (unsigned long)s_extract();
    total[1] = cmp_count;
 
    cmp_count = 0;
    for (int i = 0; i < N; i++) h_insert(keys[i]);
    ins[2] = cmp_count;
    for (int i = 0; i < N; i++) check[2] = check[2] * 31 + (unsigned long)h_extract();
    total[2] = cmp_count;
 
    printf("n = %d inserts, then n extract-max, key comparisons\n", N);
    printf("unsorted array : inserts %6ld, total %7ld\n", ins[0], total[0]);
    printf("sorted array   : inserts %6ld, total %7ld\n", ins[1], total[1]);
    printf("binary heap    : inserts %6ld, total %7ld\n", ins[2], total[2]);
    printf("all three give the same sequence: %s\n", check[0] == check[1] && check[1] == check[2] ? "yes" : "no");
    return 0;
}

Output:

n = 1000 inserts, then n extract-max, key comparisons
unsorted array : inserts      0, total  499500
sorted array   : inserts 240907, total  240907
binary heap    : inserts   2271, total   17224
all three give the same sequence: yes

Reading it. One thousand pseudo-random keys are inserted and then removed largest first, using each implementation and counting key comparisons. All three produce the same output order (the last line checks that). The unsorted array does no work on insertion but scans all remaining keys on every extraction: $999 + 998 + \cdots + 1 = 499500$ comparisons, which is $\Theta(n^2)$ . The sorted array pays on insertion instead (it shifts larger keys one place to the right) and extracts for free, about $n^2/4$ comparisons in total for random keys. The heap does both in $O(\log n)$ and needs about $17{,}000$ comparisons in all, roughly 17 per key against about 500 per key for the unsorted array. The exact figures belong to this run; the growth rates are what a question asks about. (Insertion into the heap is cheap here, about 2.3 comparisons per key, because random keys rarely climb far; the worst case for one insertion is $\lfloor \log_2 n \rfloor$ .)

EX 2Two ways to build a heap give two different heaps

Medium

#include <stdio.h>
 
static int swaps;
 
static void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
    swaps++;
}
 
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;
    }
}
 
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 show(const char *name, const int a[], int n) {
    printf("%-22s", name);
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    printf(" (swaps: %d)\n", swaps);
}
 
int main(void) {
    int input[11] = {0, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    int n = 10;
 
    int f[11];
    for (int i = 0; i <= n; i++) f[i] = input[i];
    swaps = 0;
    for (int i = n / 2; i >= 1; i--) sift_down(f, n, i);
    show("bottom-up (Floyd):", f, n);
 
    int g[11];
    swaps = 0;
    for (int k = 1; k <= n; k++) {
        g[k] = input[k];
        sift_up(g, k);
    }
    show("repeated insertion:", g, n);
    return 0;
}

Output:

bottom-up (Floyd):    16 14 10 8 7 9 3 2 4 1  (swaps: 7)
repeated insertion:   16 14 10 8 7 3 9 1 4 2  (swaps: 9)

Reading it. The input is 4 1 3 2 16 9 10 14 8 7. Bottom-up building (the animation above) gives 16 14 10 8 7 9 3 2 4 1 with 7 swaps. Repeated insertion gives 16 14 10 8 7 3 9 1 4 2 with 9 swaps. Both are valid max-heaps, and both have the same root and the same set of keys, but positions 6, 7, 8 and 10 differ. So a heap is not unique, and a question that asks for the array "after building the heap" usually says which method. If it only says "build a heap" or "using the standard build-heap procedure", read it as bottom-up.

EX 3Why bottom-up building is linear and insertion is not

GATE level

#include <stdio.h>
 
#define N 7
 
static int swaps;
 
static void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
    swaps++;
}
 
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;
    }
}
 
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 int a[N + 1], used[N + 1];
static int worst_floyd, worst_insert, arrangements;
 
static void gen(int k) {
    if (k > N) {
        int f[N + 1], g[N + 1];
        arrangements++;
        for (int i = 1; i <= N; i++) f[i] = a[i];
        swaps = 0;
        for (int i = N / 2; i >= 1; i--) sift_down(f, N, i);
        if (swaps > worst_floyd) worst_floyd = swaps;
        swaps = 0;
        for (int i = 1; i <= N; i++) {
            g[i] = a[i];
            sift_up(g, i);
        }
        if (swaps > worst_insert) worst_insert = swaps;
        return;
    }
    for (int v = 1; v <= N; v++) {
        if (used[v]) continue;
        used[v] = 1;
        a[k] = v;
        gen(k + 1);
        used[v] = 0;
    }
}
 
static int log2_floor(int x) {
    int r = 0;
    while (x > 1) {
        x /= 2;
        r++;
    }
    return r;
}
 
int main(void) {
    gen(1);
    printf("n = %d, all %d arrangements: most swaps bottom-up %d, repeated insertion %d\n", N, arrangements, worst_floyd, worst_insert);
    printf("       n  sum of heights  sum of depths\n");
    int sizes[5] = {7, 15, 255, 1023, 1000000};
    for (int s = 0; s < 5; s++) {
        int n = sizes[s];
        long heights = 0, depths = 0;
        for (int i = 1; i <= n; i++) {
            int h = 0;
            for (int j = i; 2 * j <= n; j *= 2) h++;
            heights += h;
            depths += log2_floor(i);
        }
        printf("%8d %15ld %14ld\n", n, heights, depths);
    }
    return 0;
}

Output:

n = 7, all 5040 arrangements: most swaps bottom-up 4, repeated insertion 10
       n  sum of heights  sum of depths
       7               4             10
      15              11             34
     255             247           1538
    1023            1013           8194
 1000000          999993       17951445

Reading it. For $n = 7$ the program tries all $7! = 5040$ input arrangements and records the largest number of swaps each method ever needs: 4 for bottom-up and 10 for repeated insertion. For $n = 7$ those equal the sums in the second table (the sums are upper bounds, and here they are attained): the sum of the heights of all nodes ( $0 \cdot 4 + 1 \cdot 2 + 2 \cdot 1 = 4$ for $n = 7$ ) bounds the swaps of bottom-up building, and the sum of the depths ( $1 \cdot 2 + 2 \cdot 4 = 10$ ) bounds the swaps of repeated insertion. Most nodes are near the bottom, so a node's height is small on average while its depth is large on average: for $n = 1023$ the first sum is 1013 (about $n$ ) and the second is 8194 (about $n(\log_2 n - 1)$ ). For $n = 10^6$ it is 999,993 against 17,951,445. That is the whole argument for $\Theta(n)$ against $\Theta(n \log n)$ : the sums are worst-case bounds, and they are attained (the exhaustive check for $n = 7$ shows it).

EX 4Heapsort costs the same on every input (almost)

Medium

#include <stdio.h>
 
#define N 1024
 
static long cmp_count, swap_count;
 
static void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
    swap_count++;
}
 
static void sift_down(int a[], int n, int i) {
    for (;;) {
        int l = 2 * i, r = 2 * i + 1, big = i;
        if (l <= n) { cmp_count++; if (a[l] > a[big]) big = l; }
        if (r <= n) { cmp_count++; if (a[r] > a[big]) big = r; }
        if (big == i) break;
        swap(&a[i], &a[big]);
        i = big;
    }
}
 
static void heap_sort(int a[], int n) {
    for (int i = n / 2; i >= 1; i--) sift_down(a, n, i);
    for (int last = n; last >= 2; last--) {
        swap(&a[1], &a[last]);
        sift_down(a, last - 1, 1);
    }
}
 
static void run(const char *name, int a[]) {
    cmp_count = swap_count = 0;
    heap_sort(a, N);
    int sorted = 1;
    for (int i = 2; i <= N; i++)
        if (a[i - 1] > a[i]) sorted = 0;
    printf("%-18s comparisons %6ld, swaps %6ld, sorted: %s\n", name, cmp_count, swap_count, sorted ? "yes" : "no");
}
 
int main(void) {
    static int a[N + 1];
    unsigned s = 7;
    for (int i = 1; i <= N; i++) { s = s * 1103515245u + 12345u; a[i] = (int)((s >> 8) % 100000); }
    run("random keys", a);
    for (int i = 1; i <= N; i++) a[i] = i;
    run("already sorted", a);
    for (int i = 1; i <= N; i++) a[i] = N + 1 - i;
    run("reverse sorted", a);
    for (int i = 1; i <= N; i++) a[i] = 5;
    run("all keys equal", a);
    return 0;
}

Output:

random keys        comparisons  17307, swaps   9318, sorted: yes
already sorted     comparisons  18060, swaps   9968, sorted: yes
reverse sorted     comparisons  16407, swaps   8542, sorted: yes
all keys equal     comparisons   3066, swaps   1023, sorted: yes

Reading it. $n = 1024$ in each case. Random, already sorted and reverse sorted inputs cost about the same, around $17{,}000$ comparisons: heapsort does not get faster on sorted input. That is the sense in which it is not adaptive, and it is why the usual table gives $\Theta(n \log n)$ for the best, average and worst case alike. That is the answer to give in an exam. The one input here that is much cheaper is all keys equal: 3066 comparisons, about $3n$ , because this code's sift down uses a strict >, never swaps equal keys, and stops after one level (the 1023 swaps are the root swaps of the sort loop). This is a property of the code, not a case to quote: with >= in the two child tests the same input costs 16,398 comparisons (a separate run of the modified code, not shown).

EX 5Heapsort is not stable

GATE level

#include <stdio.h>
 
struct rec {
    int key;
    char tag;
};
 
static void swap(struct rec *x, struct rec *y) {
    struct rec t = *x;
    *x = *y;
    *y = t;
}
 
static void sift_down(struct rec a[], int n, int i) {
    for (;;) {
        int l = 2 * i, r = 2 * i + 1, big = i;
        if (l <= n && a[l].key > a[big].key) big = l;
        if (r <= n && a[r].key > a[big].key) big = r;
        if (big == i) break;
        swap(&a[i], &a[big]);
        i = big;
    }
}
 
static void heap_sort(struct rec a[], int n) {
    for (int i = n / 2; i >= 1; i--) sift_down(a, n, i);
    for (int last = n; last >= 2; last--) {
        swap(&a[1], &a[last]);
        sift_down(a, last - 1, 1);
    }
}
 
int main(void) {
    struct rec a[4] = {{0, ' '}, {1, 'a'}, {1, 'b'}, {2, 'c'}};
    printf("before: ");
    for (int i = 1; i <= 3; i++) printf("%d%c ", a[i].key, a[i].tag);
    heap_sort(a, 3);
    printf("\nafter:  ");
    for (int i = 1; i <= 3; i++) printf("%d%c ", a[i].key, a[i].tag);
    printf("\n");
    return 0;
}

Output:

before: 1a 1b 2c
after:  1b 1a 2c

Reading it. The two records with key 1 come in as a then b, and leave as b then a. The reason: equal keys are moved by long-distance swaps (root with the last position, parent with child) that ignore their original order, and the sift down does not swap on a tie. A stable sort keeps equal keys in their input order, so heapsort is not stable (unlike merge sort and insertion sort). It is, however, in place: it uses $O(1)$ extra space.

EX 6The k largest keys with a min-heap of size k

Medium

#include <stdio.h>
 
/* min-heap of the k largest keys seen so far, in m[1..size] */
static int m[16], size;
 
static void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}
 
static void sift_down(int i) {
    for (;;) {
        int l = 2 * i, r = 2 * i + 1, s = i;
        if (l <= size && m[l] < m[s]) s = l;
        if (r <= size && m[r] < m[s]) s = r;
        if (s == i) break;
        swap(&m[i], &m[s]);
        i = s;
    }
}
 
static void push(int x) {
    int i = ++size;
    m[i] = x;
    while (i > 1 && m[i / 2] > m[i]) {
        swap(&m[i / 2], &m[i]);
        i /= 2;
    }
}
 
int main(void) {
    int data[12] = {23, 5, 91, 14, 60, 8, 77, 31, 99, 2, 45, 68};
    int k = 4;
    for (int i = 0; i < 12; i++) {
        if (size < k) {
            push(data[i]);
        } else if (data[i] > m[1]) {
            m[1] = data[i];
            sift_down(1);
        }
        printf("after %2d: the %d largest so far, smallest of them at the root: %d\n", data[i], size, m[1]);
    }
    printf("heap array:");
    for (int i = 1; i <= size; i++) printf(" %d", m[i]);
    printf("\n");
    return 0;
}

Output:

after 23: the 1 largest so far, smallest of them at the root: 23
after  5: the 2 largest so far, smallest of them at the root: 5
after 91: the 3 largest so far, smallest of them at the root: 5
after 14: the 4 largest so far, smallest of them at the root: 5
after 60: the 4 largest so far, smallest of them at the root: 14
after  8: the 4 largest so far, smallest of them at the root: 14
after 77: the 4 largest so far, smallest of them at the root: 23
after 31: the 4 largest so far, smallest of them at the root: 31
after 99: the 4 largest so far, smallest of them at the root: 60
after  2: the 4 largest so far, smallest of them at the root: 60
after 45: the 4 largest so far, smallest of them at the root: 60
after 68: the 4 largest so far, smallest of them at the root: 68
heap array: 68 77 91 99

Reading it. With $k = 4$ the heap keeps the four largest keys seen so far, and its root is the smallest of those four (a min-heap). A new key is useful only if it beats that smallest one; then it replaces the root and sinks. After 60 the root is 14: the heap holds 91, 14, 23, 60 (the four largest of the first five keys 23, 5, 91, 14, 60). The final heap array is 68 77 91 99, which are exactly the four largest of the twelve keys. Each key costs at most one sift down in a heap of size $k$ , so the time is $O(n \log k)$ and the space $O(k)$ . It also never needs all the keys at once, so it works on a stream. (A max-heap of size $k$ would be the wrong tool for the $k$ largest: its root is the largest of the kept keys, which tells you nothing about whether to evict.)

EX 7Merging k sorted lists

Medium

#include <stdio.h>
 
#define K 3
 
/* one list is sorted increasingly; the heap holds one entry per list: the list's current head */
struct entry {
    int value;
    int list;
};
 
static struct entry heap[K + 1];
static int hn;
 
static void swap(struct entry *x, struct entry *y) {
    struct entry t = *x;
    *x = *y;
    *y = t;
}
 
static void sift_down(int i) {
    for (;;) {
        int l = 2 * i, r = 2 * i + 1, s = i;
        if (l <= hn && heap[l].value < heap[s].value) s = l;
        if (r <= hn && heap[r].value < heap[s].value) s = r;
        if (s == i) break;
        swap(&heap[i], &heap[s]);
        i = s;
    }
}
 
static void push(struct entry e) {
    int i = ++hn;
    heap[i] = e;
    while (i > 1 && heap[i / 2].value > heap[i].value) {
        swap(&heap[i / 2], &heap[i]);
        i /= 2;
    }
}
 
int main(void) {
    int list0[] = {1, 4, 9, 12};
    int list1[] = {2, 3, 10};
    int list2[] = {5, 6, 7, 8, 11};
    const int *lists[K] = {list0, list1, list2};
    int len[K] = {4, 3, 5};
    int pos[K] = {0, 0, 0};
    int max_size = 0;
 
    for (int j = 0; j < K; j++) {
        struct entry e = {lists[j][0], j};
        push(e);
        if (hn > max_size) max_size = hn;
    }
    int total = 4 + 3 + 5;
    for (int out = 0; out < total; out++) {
        struct entry top = heap[1];
        printf("%d ", top.value);
        pos[top.list]++;
        if (hn > max_size) max_size = hn;
        if (pos[top.list] < len[top.list]) {
            heap[1].value = lists[top.list][pos[top.list]];
            sift_down(1);
        } else {
            heap[1] = heap[hn--];
            sift_down(1);
        }
    }
    printf("\nlargest heap size during the merge: %d (for %d output keys)\n", max_size, total);
    return 0;
}

Output:

1 2 3 4 5 6 7 8 9 10 11 12
largest heap size during the merge: 3 (for 12 output keys)

Reading it. Three sorted lists (1 4 9 12, 2 3 10, 5 6 7 8 11, twelve keys in total) are merged. The heap holds one entry per list, the current smallest unused key of that list, so it never holds more than $k = 3$ entries. Each output step looks at the root (the overall smallest), prints it, and replaces it with the next key of the same list; when a list is used up, its entry is removed and the heap shrinks. Every output key costs one sift down in a heap of size $\le k$ , so merging $N$ keys takes $O(N \log k)$ . Merging by always scanning all $k$ list heads would cost $\Theta(N k)$ .

EX 8Costing a whole workload

GATE level

A program performs $n$ inserts followed by $n$ extract-max operations on a priority queue of keys. What is the total worst-case time for each implementation?

Implementation	$n$ inserts	$n$ extract-max	Total
Unsorted array	$n \cdot O(1) = \Theta(n)$	$\sum_{i=1}^{n} \Theta(i) = \Theta(n^2)$	$\Theta(n^2)$
Sorted array	$\sum_{i=1}^{n} \Theta(i) = \Theta(n^2)$	$n \cdot O(1) = \Theta(n)$	$\Theta(n^2)$
Binary heap, insertion by sift up	$n \cdot O(\log n) = O(n \log n)$	$n \cdot O(\log n) = O(n \log n)$	$O(n \log n)$ (and $\Theta(n \log n)$ in the worst case, see below)
Binary heap, bottom-up build of the $n$ keys first	$\Theta(n)$	$O(n \log n)$	$O(n \log n)$

Reading it. The two array versions only move the work around: one is cheap on insert and expensive on extract, the other the reverse. The heap shares the work evenly. Bottom-up building makes the first phase linear but the extractions still dominate, so the total stays $\Theta(n \log n)$ . This is exactly the work of heapsort, which is why heapsort is $\Theta(n \log n)$ and not better in the worst case: a comparison-based sort cannot beat $\Omega(n \log n)$ comparisons in the worst case (see the Algorithms subject).

Cheat box

Priority queue: insert, find-max, extract-max. Not a FIFO queue; equal keys have no order guarantee.
Binary heap: insert $O(\log n)$ , extract $O(\log n)$ , find-max $O(1)$ . Unsorted array: $O(1)$ , $O(n)$ . Sorted array: $O(n)$ , $O(1)$ .
Build-heap (bottom-up): sift down for $i = \lfloor n/2 \rfloor$ down to 1. $\Theta(n)$ (at most $n - 1$ swaps). Building by $n$ inserts: $\Theta(n \log n)$ . The arrays can differ.
Heapsort: build, then swap root with the last live position and sift down. $\Theta(n \log n)$ in the best, average and worst case (exam answer), in place, not stable, not adaptive. Max-heap gives increasing order.
$k$ largest: min-heap of size $k$ , $O(n \log k)$ . Merge $k$ sorted lists: heap of $k$ heads, $O(N \log k)$ .
Decrease-key $O(\log n)$ at a known position; finding the item by key is $\Theta(n)$ without an index table.

Traps and GATE patterns

Connections

Builds on

Binary heaps and heap operations

Unlocks

Heap sortPrerequisite of Heap sortuses Huffman codinguses Binary heaps and heap operationsuses

Across subjects

Heap sortimplemented-by Stability, in-place and comparison of sortsuses Dijkstra's algorithmuses Huffman codinguses

Within this subject

Binary heaps and heap operationsuses Queue (abstract data type)contrasts-with

Everything here rests on the binary heap and its two operations. A priority queue is the opposite of a queue in the order it serves. Heapsort is one of the comparison sorts of the Algorithms subject (heap sort, with the stability comparison in sorting properties); Dijkstra's shortest paths and Huffman coding are the classic users of a priority queue.

PYQs

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

GATE 2005 · MCQQ53 · page 74 of the book

Suppose there are ⌈log n⌉ sorted lists of ⌊n/log n⌋
elements each. The time complexity of producing a
sorted list of all these elements is: (Hint: Use a heap
data structure)

(a)O(nlog log n)
(b)θ(nlog n)
(c)Ω(nlog n) 3
(d)Ω (n2) DATA STRUCTURE

Self-check

Question 1

Build a max-heap from the array 1 2 3 4 5 6 using the standard bottom-up procedure. Give the final array and the number of swaps. Then give the array produced by inserting 1, 2, 3, 4, 5, 6 one at a time.

Show answer

Bottom-up: position 3 (key 3) has the child 6 at position 6, swap (1 swap); position 2 (key 2) has children 4 and 5, swap with 5 (1 swap); position 1 (key 1) has children 5 and 6 (after the changes), swap with 6, then at position 3 its child at position 6 holds 3, swap (2 swaps). Total 4 swaps, array 6 5 3 4 2 1. Repeated insertion gives 6 4 5 1 3 2 (8 swaps). Both are heaps and they differ.

Question 2

State the time to (a) build a heap from $n$ keys, (b) heapsort $n$ keys, (c) find the 5 largest of $n$ keys with a heap.

Show answer

(a) $\Theta(n)$ . (b) $\Theta(n \log n)$ . (c) $O(n)$ : for example a min-heap of size 5 costs $O(n \log 5) = O(n)$ , or build a max-heap in $\Theta(n)$ and extract 5 times for $O(n + 5 \log n) = O(n)$ .

Question 3

A priority queue is a sorted array. What is the total time for $n$ inserts followed by $n$ extract-max operations?

Show answer

Each insertion shifts $O(i)$ keys, so the inserts cost $\Theta(n^2)$ in total; each extraction is $O(1)$ . Total $\Theta(n^2)$ .

Question 4

Give input records of which heapsort changes the order of two equal keys.

Show answer

Three records with keys 1, 1, 2 labelled a, b, c come out as b, a, c (the example above). So heapsort is not stable.

Question 5

For a heap of $n = 15$ keys (a perfect tree), how many swaps can bottom-up building need at most, and how many can building by repeated insertion need at most?

Show answer

Bottom-up: the sum of the node heights, $4 \cdot 1 + 2 \cdot 2 + 1 \cdot 3 = 11$ ( $= 15 - 4$ , as $15$ has four 1 bits). Repeated insertion: the sum of the depths, $2 \cdot 1 + 4 \cdot 2 + 8 \cdot 3 = 34$ .

Revision card

One-screen revision

Priority queue ADT: insert, find-max, extract-max; heap gives $O(\log n)$ , $O(1)$ , $O(\log n)$ .
Bottom-up build: sift down from $\lfloor n/2 \rfloor$ to 1; $\Theta(n)$ (swaps $\le$ sum of heights $\le n - 1$ ). By inserts: $\Theta(n \log n)$ . Results can differ.
Heapsort: build; swap root with last; sift down. $\Theta(n \log n)$ best, average and worst; in place; not stable.
$k$ largest: min-heap of size $k$ , $O(n \log k)$ . Merge $k$ lists: $O(N \log k)$ .
Equal keys: no order guarantee in a priority queue.

References

·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., Chapter 6 Heapsort (6.3 Building a heap, 6.4 The heapsort algorithm, 6.5 Priority queues)

Verification

The two animations on this page (heap-build and heap-sort) are real runs of the shown code. All C programs on this page are compiled with -Wall -Wextra -Werror and run by npm run verify:c. The following were checked by scripts/enum-checks/heaps.py: that bottom-up building and repeated insertion both always give valid heaps for every permutation of 1..n (n up to 9), their exact worst-case swap counts (4 and 10 for n = 7), and that the sum of the heights of the nodes of an n-node heap is n minus the number of 1 bits of n. The brute-force counts for n = 7 are also run by one of the programs on this page. The textbook section numbers were written from memory and have NOT been checked against the book. The statement about heapsort on all-equal keys is a measured run, not a proof. 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 heaps and heap operations

Stack applications: expression evaluation and matching