Heap Sort Visualization

How Heap Sort Works

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It divides its input into a sorted and an unsorted region, and iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of using a heap data structure rather than a linear-time search to find the maximum.

function heapSort(array):
    buildMaxHeap(array)
    for i from array.length - 1 to 1:
        swap array[0] and array[i]
        heapify(array, 0, i)
        visualize(array, 0, i)

function buildMaxHeap(array):
    for i from (array.length / 2) - 1 to 0:
        heapify(array, i, array.length)

function heapify(array, i, heapSize):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < heapSize and array[left] > array[largest]:
        largest = left
    if right < heapSize and array[right] > array[largest]:
        largest = right
    if largest != i:
        swap array[i] and array[largest]
        heapify(array, largest, heapSize)
    visualize(array, i, largest)