AlgoViz: Interactive Algorithm Visualization Tool

Heap Sort

Category: Sorting | Time: O(n log n) | Space: O(1)

Input Data

Visualization

Visual representation of the data structure

Enter an algorithm and input to start visualization.

About Heap Sort

A comparison-based sorting technique based on a Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining elements.

Code Editor

The code is for reference. Editing it won't affect the visualization.

function heapSort(arr) {
    var n = arr.length;
    for (var i = Math.floor(n / 2) - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (var i = n - 1; i > 0; i--) {
        var temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
    return arr;
}
function heapify(arr, n, i) {
    var largest = i;
    var l = 2 * i + 1;
    var r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
    if (largest != i) {
        var swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;
        heapify(arr, n, largest);
    }
}

What is Heap Sort?

How does Heap Sort build the initial heap?

What is the time complexity of Heap Sort?

What is the space complexity of Heap Sort?

Is Heap Sort stable?

What is a 'heapify' operation?

How does Heap Sort compare to Quick Sort?

Is Heap Sort a good choice for sorting linked lists?

What is the main sorting logic after the heap is built?

What are the main use cases for Heap Sort?

Where can I learn more?