Heap Sort

Sorting

avgO(n log n)worstO(n log n)spaceO(1)

Treat the 15 values as a complete binary tree

1 / 129

Code

function heapSort(a: number[]) {  const n = a.length;  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n);  for (let end = n - 1; end > 0; end--) {    [a[0], a[end]] = [a[end], a[0]];    siftDown(a, 0, end);  }  return a;}function siftDown(a: number[], i: number, size: number) {  while (true) {    const l = 2 * i + 1, r = l + 1;    let largest = i;    if (l < size && a[l] > a[largest]) largest = l;    if (r < size && a[r] > a[largest]) largest = r;    if (largest === i) return;    [a[i], a[largest]] = [a[largest], a[i]];    i = largest;  }}

procedure heapSort(A)  n ← length(A)  for i ← ⌊n/2⌋ − 1 down to 0 do siftDown(A, i, n)    ▷ build max-heap  for end ← n − 1 down to 1 do    swap A[0] and A[end]    ▷ max goes to the back    siftDown(A, 0, end)  end for  return Aend procedureprocedure siftDown(A, i, size)  loop    l ← 2i + 1; r ← l + 1    largest ← i    if l < size and A[l] > A[largest] then largest ← l    if r < size and A[r] > A[largest] then largest ← r    if largest = i then return    swap A[i] and A[largest]    i ← largest  end loopend procedure

Variables

n=15

Counters

comparisons: 0
swaps: 0

Size15

Distribution

Custom values2 to 150 whole numbers, each 1 to 999

seed 17

How it works

Arranges the array as a binary max-heap, then repeatedly swaps the root (the maximum) to the end and sifts the new root down to restore the heap. It sorts in place in O(n log n) every time, but it isn't stable.

Complexity

Best: O(n log n)
Average: O(n log n)
Worst: O(n log n)
Space: O(1)
Stable: No
In place: Yes

Heap Sort

How it works

Complexity

Search algorithms