Heap Sort

Heaps

A binary heap is a complete binary tree. In a max-heap, every parent is at least as large as its children. In a min-heap, every parent is at most as large as its children.

The root is the heap's top. It is the maximum of a max-heap and the minimum of a min-heap.

Insertion, deletion and heap construction all rely on restoring heap order.

Although a heap is a tree, its storage is sequential rather than linked. For array index parent, child indices are 2 * parent + 1 and 2 * parent + 2.

Inserting a node

Insertion is a sift-up operation. Append the node at the next available position to preserve completeness. In a max-heap, if it exceeds its parent, exchange them.

The time depends on the tree height and is $O(\log n)$.

For example, insert 21 into the max-heap $\{20,15,2,14,10\}$:

Since 21 > 2, exchange the new node with its parent 2.

Since 21 > 20, exchange it with 20.

Deleting the root

Heap deletion removes the root. Move the last node into the root position to preserve completeness, then sift it down. In a max-heap, exchange it with the larger child while that child is greater.

Deletion takes $O(\log n)$ time, bounded by tree height.

For example, delete root 20:

Move the last node into the root position to restore completeness.

Since 15 > 2, exchange the new root 1 with child 15.

Continue: since 14 > 10, exchange 1 with child 14.

Building a binary heap

Turn an unordered complete binary tree into a heap by sifting down all non-leaf nodes.

For example, build a min-heap:

Start with the last non-leaf node, 10, and sift it down.

Then handle the previous non-leaf node, 3.

The next node, 1, needs no movement.

Finally sift down node 7.

The unordered complete tree is now a min-heap.

Heap sort

After construction and deletion have been introduced, heap sort follows naturally. Removing a max-heap's root actually moves it to the end of the array. Restoring heap order brings the next-largest value to the root.

First construct a max-heap:

Move the root out of the heap by swapping it with the last element.

Sift down the new root to restore the max-heap.

Repeating root removal and repair leaves a sorted sequence.

Heap sort

All four versions come from the supplied heap-sort examples. Each heapify call excludes the already sorted suffix.

#include <stdio.h>

typedef int T;

#define swap(x, y)  \
    {               \
        T temp = x; \
        x = y;      \
        y = temp;   \
    }

static void heapify(T *arr, int index, int n) {
    int child_index = 2 * index + 1;
    while (child_index < n) {
        if (child_index + 1 < n && arr[child_index + 1] > arr[child_index]) {
            child_index++;
        }
        if (arr[index] >= arr[child_index]) {
            break;
        }
        swap(arr[index], arr[child_index]);
        index = child_index;
        child_index = 2 * index + 1;
    }
}

/**
 * Heap Sort (original v1.0)
 */
T *heap_sort(T *arr, int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, i, n);
    }

    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, 0, i);
    }

    return arr;
}

int main() {
    int arr[] = {5, 8, 6, 3, 9, 2, 7, 4, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    heap_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Auxiliary space is $O(1)$ because the algorithm does not allocate another collection.

A sift-down operation takes at most the heap height, $O(\log n)$.

Heap sort has two phases:

1. Build the heap: sift down from the last non-leaf node toward the root. Most nodes are close to leaves and move only a short distance; the total work is $O(n)$.

2. Move roots to the array's end and repair: repeat $n-1$ times, with up to $O(\log n)$ repair work each time, for $O(n\log n)$ total.

Combining both phases gives $O(n\log n)$ overall time.