Heap Sort - Algorithm, Visualization, Examples

Problem Statement❯

You are given an array of integers. Your task is to sort the array using the Heap Sort algorithm. Heap Sort works by converting the array into a max heap and repeatedly removing the maximum element and placing it at the end of the array until it is fully sorted.

Examples❯

Input	Output	Description
[4, 10, 3, 5, 1]	[1, 3, 4, 5, 10]	Normal case with a mix of unsorted values. Heap Sort first builds a max heap, then repeatedly extracts the largest value.
[1]	[1]	Edge case with a single element. Already sorted by definition.
[]	[]	Empty array. There’s nothing to sort, so the result is also an empty array.
[9, 8, 7, 6, 5]	[5, 6, 7, 8, 9]	Array in descending order. Heap Sort will reorder it in ascending order by repeatedly extracting the maximum.

Visualization Player

Solution❯

Case 1 - Normal Case

This is the typical scenario where the input array is randomly unordered.

Step 1: Build a max heap from the array. For example, given [4, 10, 3, 5, 1], it becomes [10, 5, 3, 4, 1].
Step 2: Swap the first and last elements: [1, 5, 3, 4, 10].
Step 3: Heapify the root element (1) back into max heap form: [5, 4, 3, 1, 10].
Step 4: Repeat the process, reducing the heap size each time.
Final sorted array: [1, 3, 4, 5, 10]

Case 2 - Single Element

If the input array has only one element, e.g., [1]:

There’s no heap to build. The single element is trivially a heap and also sorted.
Return the array as-is.

Case 3 - Empty Array

An empty array has nothing to sort:

No heap can be constructed.
The algorithm returns an empty array immediately.

Case 4 - Reverse Sorted Input

Input like [9, 8, 7, 6, 5] is already in descending order, which is ideal for heap construction.

Max heap will look like [9, 8, 7, 6, 5].
Swap max with last and heapify: [5, 8, 7, 6, 9]
Repeat until all values are extracted and reinserted in sorted order.
Final output: [5, 6, 7, 8, 9]

Heap Sort ensures O(n log n) performance across best, average, and worst cases, with in-place sorting and no additional space required beyond the array itself.

Algorithm Steps❯

Build a max heap from the input array.
The largest element is now at the root of the heap.
Swap the root with the last element, then reduce the heap size by one.
Heapify the root to maintain the heap property.
Repeat steps 3 and 4 until the heap size is 1.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

def 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:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    return arr

if __name__ == '__main__':
    arr = [6, 3, 8, 2, 7, 4]
    heap_sort(arr)
    print("Sorted array is:", arr)

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(n log n)	Building the max heap takes O(n) time, and the subsequent n extractions each require O(log n) heapify operations, resulting in O(n log n) even in the best case.
Average Case	O(n log n)	Heap sort performs n extract-max operations, and each requires a heapify step that takes O(log n) time. This results in an average-case time complexity of O(n log n).
Worst Case	O(n log n)	In the worst case, every extraction causes the largest number of heapify steps (log n), repeated n times. Thus, the overall time complexity is O(n log n).

Space Complexity❯

O(1)

Explanation: Heap sort is performed in-place with no need for additional memory allocation beyond a few variables, resulting in constant auxiliary space usage.

⬅ Previous TopicQuick Sort

Next Topic ⮕Find Maximum and Minimum in Array using Loop