Heap sort

Challenge

Sort an array in place using heap sort with a binary max-heap.

Task

Implement void heap_sort(int *a, size_t n) that sorts the n elements of a into non-decreasing order, using an in-place binary max-heap (no extra array).

Input

• a: writable array of n ints.
• n: the number of elements.

Output

Nothing returned; a[0..n-1] is sorted in place.

Example

{5,3,8,1,9,2,4,7,6,0}   ->   {0,1,2,3,4,5,6,7,8,9}
{-3,-1,-5,-2,0,4}       ->   {-5,-3,-2,-1,0,4}

Edge cases

• n == 0 and n == 1 return immediately.
• All-equal arrays sort correctly.

Rules

• Sort in place with O(1) auxiliary memory. Do not call malloc. Build a max-heap, then repeatedly swap the root to the back and sift down.

Why this matters

Heap sort sorts in place with O(n log n) guaranteed and no recursion. Heaps also underpin priority queues, event schedulers, and OS process scheduling.

Input format

a: writable array of n ints; n: element count.

Output format

Nothing returned; a is sorted non-decreasing in place.

Constraints

O(1) auxiliary memory. No malloc.

Starter code

#include <stddef.h>
void heap_sort(int *a, size_t n) { /* TODO */ }

Common mistakes

Off-by-one on parent/child index math; using i/2 when 0-indexed needs (i-1)/2; sifting up instead of down.

Edge cases to handle

n==0, n==1, all-equal arrays, already-heap arrays.

Complexity

O(n) build-heap, O(n log n) sort. O(1) memory.

Background lessons

• Binary trees
• Hashing — turning keys into table indices

Up next

• Min-heap priority queue
• Merge sort