Binary Heap: Definition, Operations, Build, Heap Sort, and Priority Queue Implementation in C

0 Overview

The binary heap is a complete binary tree stored in an array, where each node corresponds to an array element. All levels are fully filled except possibly the last one. Binary heaps are used to implement heap sort and priority queues.

1 Binary Heap Definition

In an array A, LENGTH(A) denotes the array length and HEAP_SIZE(A) the number of elements that belong to the heap, with LENGTH(A) ≤ HEAP_SIZE(A). The root of the heap is A[0]. Given a node index i, its parent and children can be computed as:

#define PARENT(i) ( i > 0 ? (i-1)/2 : 0 )
#define LEFT(i)   (2*i + 1)
#define RIGHT(i)  (2*i + 2)

The height h of a heap with n elements satisfies h = ⌊log₂ n⌋, because a complete binary tree of height h contains between 2^h and 2^{h+1}‑1 nodes.

2 Maintaining the Heap Property

For a max‑heap, the function maxHeapify(int A[], int i, int heapSize) lets the element at index i “float down” until the subtree rooted at i satisfies the max‑heap property.

void maxHeapify(int A[], int i, int heapSize) {
    int l = LEFT(i);
    int r = RIGHT(i);
    int largest = i;
    if (l <= heapSize-1 && A[l] > A[i]) {
        largest = l;
    }
    if (r <= heapSize-1 && A[r] > A[largest]) {
        largest = r;
    }
    if (largest != i) {
        // largest is not i, swap and recurse
        swapInt(A, i, largest);
        maxHeapify(A, largest, heapSize);
    }
}

The routine runs in O(log N) time because the height of the affected subtree is at most log N.

3 Building a Max Heap

To turn an arbitrary array into a max‑heap we call maxHeapify on all non‑leaf nodes in reverse order:

void buildMaxHeap(int A[], int n) {
    int i;
    for (i = n/2 - 1; i >= 0; i--) {
        maxHeapify(A, i, n);
    }
}

The correctness is proved by a loop invariant: before each iteration, all nodes with index greater than i are roots of max‑heaps. After the loop finishes, the whole array satisfies the max‑heap property. The overall construction runs in O(N) time.

4 Heap Sort

Heap sort repeatedly extracts the maximum element from the heap:

void heapSort(int A[], int n) {
    buildMaxHeap(A, n);
    int heapSize = n;
    for (int i = n-1; i >= 1; i--) {
        swapInt(A, 0, i);
        maxHeapify(A, 0, --heapSize);
    }
}

Each extraction maintains the heap property, resulting in a sorted array in ascending order.

5 Priority Queue

A max‑priority queue supports four operations: insert , maximum , extractMax , and increaseKey . The following C structure and functions implement the queue:

typedef struct PriorityQueue {
    int capacity;
    int size;
    int elems[];
} PQ;

/** Create a priority queue from an array */
PQ *newPQ(int A[], int n) {
    PQ *pq = (PQ *)malloc(sizeof(PQ) + sizeof(int) * n);
    pq->size = 0;
    pq->capacity = n;
    for (int i = 0; i < pq->capacity; i++) {
        pq->elems[i] = A[i];
        pq->size++;
    }
    buildMaxHeap(pq->elems, pq->size);
    return pq;
}
int maximum(PQ *pq) { return pq->elems[0]; }
int extractMax(PQ *pq) {
    int max = pq->elems[0];
    pq->elems[0] = pq->elems[--pq->size];
    maxHeapify(pq->elems, 0, pq->size);
    return max;
}
PQ *insert(PQ *pq, int key) {
    int newSize = ++pq->size;
    if (newSize > pq->capacity) {
        pq->capacity = newSize * 2;
        pq = (PQ *)realloc(pq, sizeof(PQ) + sizeof(int) * pq->capacity);
    }
    pq->elems[newSize-1] = INT_MIN;
    increaseKey(pq, newSize-1, key);
    return pq;
}
void increaseKey(PQ *pq, int i, int key) {
    int *elems = pq->elems;
    elems[i] = key;
    while (i > 0 && elems[PARENT(i)] < elems[i]) {
        swapInt(elems, PARENT(i), i);
        i = PARENT(i);
    }
}

References

CLRS, Chapter 6 – Heap Sort.