Data Structure and Algorithm

Heap Sort

Data Structure and Algorithm 285 views Nov 05, 2025 1 min read

Heap Sort Algorithm

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to efficiently find and remove the largest (or smallest) element repeatedly.

Algorithm Steps

  1. Build a max heap from the input data.
  2. Swap the root (maximum) with the last element.
  3. Reduce the heap size and heapify again.
  4. Repeat until all elements are sorted.

Example (C++)

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int 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) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

Time Complexity

  • All Cases: O(n log n)

Advantages

  • Consistent O(n log n) performance.
  • In-place sorting, no extra space needed.

Disadvantages

  • Not a stable sort.
  • More complex than insertion or selection sort.

Conclusion

Heap Sort is a reliable, efficient, and in-place sorting algorithm widely used where consistent performance is required.

Some advanced sections are available for Registered Members
Register Now
Share this Post
🚀 Want to Test Your Knowledge?

Take quizzes related to this topic and see where you stand!

Start Quiz Now
Back to Tutorials