# 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

`1export default class HeapSort extends Algorithm {2  name = "Heap Sort"3  timeComplexityBest = Complexities.linearithmic4  timeComplexityAverage = Complexities.linearithmic5  timeComplexityWorst = Complexities.linearithmic67  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  }1415  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  }2122  heapify(array: number[], i: number, length: number) {23    this.incrementOpCounter()24    const left = 2 * i + 125    const right = 2 * i + 226    let largest = i2728    if (left < length && array[left] > array[largest]) {29      largest = left30    }3132    if (right < length && array[right] > array[largest]) {33      largest = right34    }3536    if (largest !== i) {37      this.swap(array, i, largest)38      this.heapify(array, largest, length)39    }40  }4142  // eslint-disable-next-line class-methods-use-this43  swap(array: number[], i: number, j: number): void {44    const tmp = array[i]45    array[i] = array[j]46    array[j] = tmp47  }48}`