Heap Sort Visualization

Comparison-based sorting algorithm that uses a binary heap data structure.

Step: 0 / -1

Speed

1function heapSort(arr)

2 buildMaxHeap(arr)

3 for i from n-1 down to 1

4 swap(arr[0], arr[i])

5 heapify(arr, i, 0)

7function heapify(arr, n, i)

8 largest = i

9 l = 2*i + 1, r = 2*i + 2

10 if l < n and arr[l] > arr[largest]

11 largest = l

12 if r < n and arr[r] > arr[largest]

13 largest = r

14 if largest != i

15 swap(arr[i], arr[largest])

16 heapify(arr, n, largest)

Best CaseO(n log n)

Average CaseO(n log n)

Worst CaseO(n log n)