Heap Sort

Implement heap sort — a sorting algorithm built on top of the binary-heap data structure. The trick is to view the input array AS a heap: build a max-heap in place, then repeatedly swap the root (the current largest) to the back of the array and shrink the heap by one. After n rounds the array is fully sorted, and you never allocated a second buffer. Unlike quick sort, heap sort's worst case is still O(n log n); unlike merge sort, it uses only O(1) extra space. The price you pay is that heap sort is not stable — equal items can be re-ordered — and it doesn't exploit pre-existing runs the way Timsort does.

Signature

// Sorts `array` in place using the max-heap-then-extract algorithm and
// returns the same array reference. `compare` follows the same convention
// as Array.prototype.sort: negative if `a` should come out first.
// Default is `(a, b) => a - b` — ascending numeric order.
function heapSort<T>(
  array: T[],
  compare?: (a: T, b: T) => number
): T[];

Examples

Basic ascending sort, returning the same array reference:

const arr = [5, 3, 8, 1, 9, 2];
heapSort(arr);          // [1, 2, 3, 5, 8, 9]
heapSort(arr) === arr;  // true (sorts in place, returns the input)

Descending order via a flipped comparator:

heapSort([3, 1, 4, 1, 5, 9, 2, 6], (a, b) => b - a);
// → [9, 6, 5, 4, 3, 2, 1, 1]

Custom comparator over objects — sort by a priority field:

const tasks = [
  { id: 'a', priority: 3 },
  { id: 'b', priority: 1 },
  { id: 'c', priority: 2 },
];
heapSort(tasks, (a, b) => a.priority - b.priority);
// → [{ id: 'b', priority: 1 }, { id: 'c', priority: 2 }, { id: 'a', priority: 3 }]

Already-sorted and reverse-sorted inputs — both still O(n log n), no worst-case explosion:

heapSort([1, 2, 3, 4, 5]);  // [1, 2, 3, 4, 5]
heapSort([5, 4, 3, 2, 1]);  // [1, 2, 3, 4, 5]

Notes

• In-place — the input array is mutated and returned. There is no second buffer; extra memory is O(1) regardless of input size. Callers who want to keep the original should slice() before calling.
• Not stable — when two elements compare equal, the relative order they end up in is unspecified. If you need stability, reach for merge sort or augment the comparator with an index tiebreaker.
• O(n log n) worst case — unlike quick sort, there is no pathological input that pushes heap sort into O(n²). Already-sorted, reverse-sorted, and all-equal inputs all run in the same time class.
• The default comparator is (a, b) => a - b — ascending numeric. For strings, pass (a, b) => a.localeCompare(b) or use < / > explicitly.
• Returns the input reference — heapSort(arr) === arr must hold. Tests check this.
• Comparator errors propagate — if your comparator throws, heap sort does not swallow the exception.
• Out of scope — external (out-of-core) sorting, parallel heap sort, smoothsort. See Going further in the solution for pointers.