Skip to content

Big O Visualizer

Heap Sort

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. Unlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure to more quickly find the largest element in each step.

Complexity

Heap Sort has a linearithmic time complexity for most common cases.

Heap Sort performs (close to) linear, which is better than linearithmic, in one specific case: when the input list contains (large series of) identical numbers.

Algorithm

Below the implementation of Heap Sort as used on this page.

src/algorithms/heap-sort.ts
1export default class HeapSort extends Algorithm {
2 name = "Heap Sort"
3 timeComplexityBest = Complexities.linearithmic
4 timeComplexityAverage = Complexities.linearithmic
5 timeComplexityWorst = Complexities.linearithmic
6
7 execute(array: number[]): void {
8 this.buildHeap(array)
9 for (let i = array.length - 1; i > 0; i--) {
10 this.swap(array, 0, i)
11 this.heapify(array, 0, i)
12 }
13 }
14
15 buildHeap(array: number[]) {
16 for (let i = Math.floor(array.length / 2); i >= 0; i--) {
17 this.incrementOpCounter()
18 this.heapify(array, i, array.length)
19 }
20 }
21
22 heapify(array: number[], i: number, length: number) {
23 this.incrementOpCounter()
24 const left = 2 * i + 1
25 const right = 2 * i + 2
26 let largest = i
27
28 if (left < length && array[left] > array[largest]) {
29 largest = left
30 }
31
32 if (right < length && array[right] > array[largest]) {
33 largest = right
34 }
35
36 if (largest !== i) {
37 this.swap(array, i, largest)
38 this.heapify(array, largest, length)
39 }
40 }
41
42 // eslint-disable-next-line class-methods-use-this
43 swap(array: number[], i: number, j: number): void {
44 const tmp = array[i]
45 array[i] = array[j]
46 array[j] = tmp
47 }
48}