Heap Sort Algorithm Explained

Learn Heap Sort Algorithm Explained with practical examples, explanations, best practices, and real-world coding techniques.

What Is Heap Sort?

Heap Sort is a comparison-based sorting algorithm that uses a binary heap to arrange elements. It combines the heap data structure with repeated heapify operations to sort an array.

Heap Sort is commonly implemented using a Max Heap when sorting values in ascending order. The largest value is moved to the end of the array during each iteration.

Unlike some sorting approaches that require an additional array, Heap Sort can be implemented in place, using constant auxiliary space.

How Heap Sort Works

Heap Sort has two main phases:

  1. Build a Max Heap from the input array.
  2. Repeatedly move the maximum value to the end and restore the heap.
Unsorted array
      ↓
Build Max Heap
      ↓
Largest value at root
      ↓
Swap root with last unsorted element
      ↓
Reduce heap size
      ↓
Heapify down
      ↓
Repeat
      ↓
Sorted array

Heap Sort Example

Consider the following array: 

[4, 10, 3, 5, 1]

First, build a Max Heap: 

[10, 5, 3, 4, 1]

The largest value, 10, is now at the root. Swap it with the last element in the unsorted portion: 

[1, 5, 3, 4, 10]

The value 10 is now in its final sorted position. Heapify the remaining portion: 

[5, 4, 3, 1, 10]

Continue the same process until all elements are positioned: 

[1, 3, 4, 5, 10]

Why Use a Max Heap for Ascending Order?

A Max Heap always places the largest value at the root. If that root is swapped with the last element of the unsorted portion, the largest remaining value is placed at its final position. 

Max Heap:

        10
       /  \
      5    3
     / \
    4   1

Largest = 10

Move 10 to the end:

[1, 5, 3, 4, 10]

The sorted portion grows from right to left while the active heap becomes smaller.

Heap Sort Algorithm

The complete Heap Sort process can be described in two stages.

Stage 1: Build a Max Heap

  1. Treat the array as a complete binary tree.
  2. Find the last internal node.
  3. Apply heapify down from that node toward the root.
  4. The resulting array satisfies the Max Heap property.

Stage 2: Extract Maximum Values

  1. Swap the root with the last element in the active heap.
  2. Reduce the heap size by one.
  3. Heapify down from the root.
  4. Repeat until the active heap contains one element.

Heap Sort Step by Step

Consider: 

[6, 2, 8, 4, 1, 5]

Step 1: Build Max Heap

[8, 4, 6, 2, 1, 5]

The largest value, 8, is at index 0.

Step 2: Move the Maximum to the End

[5, 4, 6, 2, 1, 8]

The value 8 is now fixed and belongs to the sorted portion.

Step 3: Heapify the Remaining Portion

[6, 4, 5, 2, 1, 8]

Step 4: Continue Extracting

[1, 4, 5, 2, 6, 8]

→ [5, 4, 1, 2, 6, 8]

→ [2, 4, 1, 5, 6, 8]

→ [4, 2, 1, 5, 6, 8]

→ [1, 2, 4, 5, 6, 8]

The array is now sorted in ascending order.

Heap Sort Using JavaScript

The following implementation performs Heap Sort in place using a Max Heap. 

function heapSort(values) {
  const heap = [...values];

  function heapifyDown(size, index) {
    while (true) {
      const left = 2 * index + 1;
      const right = 2 * index + 2;

      let largest = index;

      if (
        left < size &&
        heap[left] > heap[largest]
      ) {
        largest = left;
      }

      if (
        right < size &&
        heap[right] > heap[largest]
      ) {
        largest = right;
      }

      if (largest === index) {
        break;
      }

      [heap[index], heap[largest]] =
        [heap[largest], heap[index]];

      index = largest;
    }
  }

  // Build Max Heap.
  for (
    let index = Math.floor(heap.length / 2) - 1;
    index >= 0;
    index--
  ) {
    heapifyDown(heap.length, index);
  }

  // Move maximum values to the end.
  for (
    let end = heap.length - 1;
    end > 0;
    end--
  ) {
    [heap[0], heap[end]] =
      [heap[end], heap[0]];

    heapifyDown(end, 0);
  }

  return heap;
}

const values = [6, 2, 8, 4, 1, 5];

console.log(heapSort(values));
// [1, 2, 4, 5, 6, 8]

How the Heap Size Changes

One important detail in Heap Sort is that the heap does not continue to include the entire array after every extraction. 

Initial:

[8, 4, 6, 2, 1, 5]
 ↑---------------↑
    active heap

After placing 8:

[6, 4, 5, 2, 1, 8]
 ↑-----------↑   ↑
 active heap   sorted

After placing 6:

[5, 4, 1, 2, 6, 8]
 ↑--------↑   ↑-----↑
 active      sorted

The size parameter in heapify tells the algorithm where the active heap ends. Elements after that boundary are already sorted and must not be modified.

Heapify Down in Heap Sort

After the root is moved to the end, the new root may violate the Max Heap property. Heapify down restores the heap within the reduced active range. 

[4, 7, 6, 2, 1, 8]

Swap root and last:

[8, 7, 6, 2, 1, 4]

Active heap:
[8, 7, 6, 2, 1]

Sorted portion:
[4]

In the actual algorithm, the root before the swap is the maximum. After the swap, the new root must be heapified only within the unsorted portion.

Build Max Heap for Heap Sort

The initial heap construction uses the same bottom-up technique used to build a normal Max Heap. 

for (
  let index = Math.floor(heap.length / 2) - 1;
  index >= 0;
  index--
) {
  heapifyDown(heap.length, index);
}

This construction takes O(n) time.

Why Heap Sort Is O(n log n)

Heap Sort has two major phases.

  • Building the Max Heap takes O(n).
  • There are n - 1 extraction steps.
  • Each extraction performs heapify down in O(log n).

Therefore, the dominant sorting phase takes:

O(n log n)

The overall time complexity of Heap Sort is therefore O(n log n).

Heap Sort Space Complexity

Heap Sort can be implemented in place because the heap is stored directly inside the input array.

An iterative implementation uses O(1) auxiliary space apart from the input array.

If Heap Sort is implemented recursively for heapify operations, the recursive call stack can require O(log n) additional space.

Heap Sort Complexity

Case Time Auxiliary Space
Best case O(n log n) O(1) iterative
Average case O(n log n) O(1) iterative
Worst case O(n log n) O(1) iterative

Heap Sort Is Not Stable

Heap Sort is generally considered an unstable sorting algorithm. This means equal elements may change their relative order during heap construction and extraction.

For primitive numeric values this distinction may not matter, but it becomes important when sorting objects with multiple fields.

Heap Sort Is an In-Place Algorithm

An in-place sorting algorithm rearranges the input collection without requiring another collection proportional to the input size.

Heap Sort uses the input array itself as the heap and places sorted elements at the end of that same array. 

Before:

[4, 10, 3, 5, 1]

During Heap Sort:

[10, 5, 3, 4, 1]
[5, 4, 3, 1, 10]
[4, 1, 3, 5, 10]
[3, 1, 4, 5, 10]
[1, 3, 4, 5, 10]

Same array → sorted result

Heap Sort vs Quick Sort

Heap Sort and Quick Sort are both comparison-based sorting algorithms, but they have different behavior and implementation characteristics.

Feature Heap Sort Quick Sort
Worst-case time O(n log n) O(n²)
Average time O(n log n) O(n log n)
Auxiliary space O(1) iterative Depends on recursion depth
Stable No Usually no

Heap Sort vs Merge Sort

Feature Heap Sort Merge Sort
Time O(n log n) O(n log n)
Typical array auxiliary space O(1) O(n)
Stable No Yes with the standard stable merge approach
Main technique Heap operations Divide and merge

Heap Sort vs Built-In JavaScript sort()

JavaScript provides the Array.prototype.sort() method for general-purpose sorting. Heap Sort is useful when learning algorithms, controlling the sorting implementation, or studying guaranteed O(n log n) comparison sorting. 

const values = [10, 3, 7, 1, 5];

values.sort((a, b) => a - b);

console.log(values);
// [1, 3, 5, 7, 10]

The built-in method is generally preferable for ordinary application code unless a specific algorithmic requirement calls for a custom sorting implementation.

Heap Sort with a Generic Comparison

The same heap-based idea can be adapted for different comparison rules. The standard ascending implementation uses a Max Heap, while a Min Heap can be used as part of a descending-order approach.

Descending Heap Sort

To produce descending order, the heap direction can be reversed. A Min Heap can be used so that the smallest remaining element is moved toward the end of the active range. 

Ascending:

Max Heap
largest → end


Descending:

Min Heap
smallest → end

Common Heap Sort Mistakes

Forgetting the Active Heap Size

Once a maximum value is placed at the end of the array, it belongs to the sorted portion. Heapify must operate only on the remaining unsorted elements.

Using the Wrong Child

Max Heap heapify down must select the larger child. Choosing the smaller child can violate the Max Heap property.

Sorting Before Building the Heap

Heap Sort starts with an unsorted array and builds the heap directly. Sorting the array first defeats the purpose of the algorithm.

Assuming Heap Sort Is Stable

Heap Sort is not generally stable because swapping elements can change the relative order of equal values.

Confusing Build Heap with Full Sorting

Building a heap only establishes heap order. The extraction phase is what completes the sorting process.

Where Heap Sort Is Useful

Heap Sort is useful when predictable O(n log n) sorting time and low auxiliary space are important.

  • Learning heap-based sorting algorithms.
  • Understanding priority-based data processing.
  • Situations requiring an in-place comparison sort.
  • Algorithm and data structure interviews.
  • Understanding the relationship between heaps and sorting.
  • Systems where worst-case O(n log n) comparison sorting is required.

Heap Sort Complexity Summary

Phase Time
Build Max Heap O(n)
Each extraction O(log n)
All extractions O(n log n)
Overall O(n log n)
Iterative auxiliary space O(1)

Key Takeaways

  • Heap Sort is a comparison-based sorting algorithm built around a binary heap.
  • Ascending Heap Sort commonly starts by building a Max Heap.
  • The largest value is repeatedly moved to the end of the active array.
  • Heapify down restores the Max Heap after each extraction.
  • Building the initial heap takes O(n) time.
  • The complete Heap Sort algorithm takes O(n log n) time.
  • Heap Sort can be implemented in place with O(1) auxiliary space.
  • Heap Sort is generally not stable.
  • The active heap becomes smaller after every extraction.
  • Heap Sort is different from simply building a heap because heap construction alone does not sort the array.

Code Examples 

function heapSort(values) {
  const heap = [...values];

  function heapifyDown(size, index) {
    while (true) {
      const left = 2 * index + 1;
      const right = 2 * index + 2;

      let largest = index;

      if (
        left < size &&
        heap[left] > heap[largest]
      ) {
        largest = left;
      }

      if (
        right < size &&
        heap[right] > heap[largest]
      ) {
        largest = right;
      }

      if (largest === index) {
        break;
      }

      [heap[index], heap[largest]] =
        [heap[largest], heap[index]];

      index = largest;
    }
  }

  // Build Max Heap.
  for (
    let index = Math.floor(heap.length / 2) - 1;
    index >= 0;
    index--
  ) {
    heapifyDown(heap.length, index);
  }

  // Move maximum values to the end.
  for (
    let end = heap.length - 1;
    end > 0;
    end--
  ) {
    [heap[0], heap[end]] =
      [heap[end], heap[0]];

    heapifyDown(end, 0);
  }

  return heap;
}

console.log(
  heapSort([10, 3, 7, 1, 5, 8])
);
// [1, 3, 5, 7, 8, 10]
    
function heapSortInPlace(array) {
  function heapifyDown(size, index) {
    while (true) {
      const left = 2 * index + 1;
      const right = 2 * index + 2;

      let largest = index;

      if (
        left < size &&
        array[left] > array[largest]
      ) {
        largest = left;
      }

      if (
        right < size &&
        array[right] > array[largest]
      ) {
        largest = right;
      }

      if (largest === index) {
        break;
      }

      [array[index], array[largest]] =
        [array[largest], array[index]];

      index = largest;
    }
  }

  // Build Max Heap.
  for (
    let index = Math.floor(array.length / 2) - 1;
    index >= 0;
    index--
  ) {
    heapifyDown(array.length, index);
  }

  // Sort in place.
  for (
    let end = array.length - 1;
    end > 0;
    end--
  ) {
    [array[0], array[end]] =
      [array[end], array[0]];

    heapifyDown(end, 0);
  }
}

const values = [12, 4, 9, 1, 7, 6];

heapSortInPlace(values);

console.log(values);
// [1, 4, 6, 7, 9, 12]
    
function heapSortWithSteps(values) {
  const array = [...values];

  function heapifyDown(size, index) {
    while (true) {
      const left = 2 * index + 1;
      const right = 2 * index + 2;

      let largest = index;

      if (
        left < size &&
        array[left] > array[largest]
      ) {
        largest = left;
      }

      if (
        right < size &&
        array[right] > array[largest]
      ) {
        largest = right;
      }

      if (largest === index) {
        break;
      }

      [array[index], array[largest]] =
        [array[largest], array[index]];

      index = largest;
    }
  }

  for (
    let index = Math.floor(array.length / 2) - 1;
    index >= 0;
    index--
  ) {
    heapifyDown(array.length, index);
  }

  console.log("Max Heap:", array);

  for (
    let end = array.length - 1;
    end > 0;
    end--
  ) {
    [array[0], array[end]] =
      [array[end], array[0]];

    heapifyDown(end, 0);

    console.log(
      `Sorted portion starts at index ${end}:`,
      array
    );
  }

  return array;
}

console.log(
  heapSortWithSteps([6, 2, 8, 4, 1, 5])
);

Pro Tip

For ascending Heap Sort, remember the core pattern: build a Max Heap, swap the root with the last unsorted element, reduce the heap size, and heapify down. The sorted portion grows from right to left.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.