How does heap sort work step by step?

Heap sort first builds a max-heap from the array so the largest value sits at the root. It then repeatedly swaps the root with the last unsorted element, shrinks the heap by one, and calls heapify to restore the max-heap property. Repeating this extracts every element in descending order.

What is the time and space complexity of heap sort?

Heap sort always runs in O(n log n) time - best, average, and worst case - with O(1) auxiliary space because it sorts in place.

No. Heap sort is NOT stable because the heap operations move elements non-adjacently, which can reorder equal keys.

Heap Sort

How to use ?

Enter an array separated by commas as : 16,15,15,10,1 or just press the hand icon to generate a random array then press enter or Sort button. Sorting will start and you can watch each pass as it gets sorted. When it shows green it means the two of them are being compared when red shows, it means the left number is greater than right number so it needs swapping The blue color means the number is at its correct position and thus sorted it will continue to check other numbers until it reaches end.

Heap Sort Overview

History

Heap sort is based on the binary heap data structure and was developed in the 1960s. It is considered an efficient sorting algorithm and is often used in systems that require high performance.

Current Uses

Data Processing: Used in systems that require efficient sorting and management of data.
Priority Queues: Often employed in implementing priority queues due to its underlying heap structure.
Embedded Systems: Suitable for environments with limited memory resources.

Time and Space Complexity

Time Complexity

Best Case: O(n log n) - Performance is consistent regardless of input.
Average Case: O(n log n) - Efficient average performance.
Worst Case: O(n log n) - Consistent performance even in the worst case.

Space Complexity

Space Complexity: O(1) - It is an in-place sorting algorithm that requires minimal additional space.

Pseudo Code

function heapSort(arr):
    n = length(arr)
    // Build heap (rearrange array)
    for i from n/2 - 1 to 0:
        heapify(arr, n, i)
    // One by one extract elements from heap
    for i from n-1 to 0:
        swap arr[0] and arr[i]
        heapify(arr, i, 0)

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

Key Characteristics

In-Place: Heap sort operates in place, requiring minimal additional memory.
Not Stable: The algorithm is not stable, as equal elements may change order.

Summary

Heap sort is a comparison-based sorting algorithm that utilizes the properties of a binary heap. With a time complexity of O(n log n), it is efficient and suitable for applications requiring guaranteed performance.

How Heap Sort Works

Heap sort turns the array into a max-heap - a binary tree where every parent is larger than its children and the largest value sits at the root. It then repeatedly extracts that root:

Build a max-heap from the input array by calling heapify on every internal node, from bottom up.
Swap the root (largest element) with the last unsorted element.
Shrink the heap by one and call heapify on the new root to restore the max-heap property.
Repeat extracting the root until only one element remains - the array is now sorted in ascending order.

Heap sort is notably in-place (O(1) extra space) and guarantees O(n log n) in every case, but it is not cache-friendly like quick sort and is not stable.

When To Use Heap Sort

Guaranteed O(n log n): reliable performance no matter the input order.
Priority queues: the heap data structure behind task scheduling.
Embedded systems: in-place sorting with bounded memory usage.
Fallback in Introsort: C++ std::sort switches to heap sort when recursion gets too deep.

Heap Sort Code Implementation