How to Write a Heap Sort Program in C++

C++ Data Structures and Algorithms | how-to |

Heap sort is one of those algorithms that can be either really captivating or really scary at the same time. If you’ve done sorting algorithms prior to this, you probably already know quick sort or even merge sort, or maybe even bubble sort. But heap sort? That’s a little different. Don’t worry, though; we’ll walk through it step by step and get you comfortable enough to write a heap sort program in C++ by the end of it. Let’s dive in!

What is Heap Sort?

First of all. Heap sort is one of the comparison-based sorting algorithms. What makes heap sort unique is its use of a binary heap—one form of binary tree in which every parent node is greater than or equal to each of its child nodes (max heap) or lesser than or equal to its child nodes (min-heap).

In simple words: Heap sort constructs a heap from the input data, rearranges the elements, and peels off the sorted elements one by one from the heap.

Here, let’s go into detail about the implementation of heap sort in C++.

Step-by-Step Breakdown of Heap Sort

  1. Build a Max Heap:
    • We start by turning our unsorted array into a max heap, where the largest element becomes the root node.
  2. Extract Elements:
    • Once the max heap is built, the largest element (root) is swapped with the last element of the heap.
  3. Heapify the Remaining Elements:
    • After extracting the largest element, we heapify the remaining unsorted portion of the array.
  4. Repeat until the array is fully sorted.

Sounds complicated? Don’t worry—it’s easier once you see the code.

Writing the Heap Sort Program in C++

#include <iostream>
using namespace std;

// A function to heapify a subtree with the root at index i
void heapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int left = 2 * i + 1; // left child
    int right = 2 * i + 2; // right child

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // If largest is not root
    if (largest != i) {
        swap(arr[i], arr[largest]);

        // Recursively heapify the affected subtree
        heapify(arr, n, largest);
    }
}

// Function to perform heap sort
void heapSort(int arr[], int n) {
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // One by one extract an element from heap
    for (int i = n - 1; i >= 0; i--) {
        // Move current root to end
        swap(arr[0], arr[i]);

        // Call heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

// A utility function to print array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << "\n";
}

// Main function
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Unsorted array: \n";
    printArray(arr, n);

    heapSort(arr, n);

    cout << "Sorted array: \n";
    printArray(arr, n);
}

Explanation of the Code

  • heapify function: This function rearranges the elements of the heap so that the parent node is larger than its child nodes. It recursively ensures the properties of a heap are maintained.
  • heapSort function: This is where the actual sorting happens. First, the array is converted into a heap, and then elements are extracted one by one, maintaining the heap property.

Why Heap Sort?

Now, you might be thinking, “Why should I even use heap sort when there are so many other sorting algorithms out there?”

Here’s the deal: heap sort has some unique advantages:

  • Worst-case performance: Heap sort has a worst-case time complexity of O(n log n), making it efficient even in the worst-case scenarios.
  • Memory efficiency: Heap sort is in place, meaning it doesn’t require additional memory proportional to the size of the input (unlike merge sort).

That said, heap sort isn’t perfect. Quick sort often performs better on average, especially with randomly ordered data.

Real-World Example: Why It Matters

Let’s say you’re writing a program that needs to efficiently handle priority tasks—maybe something like scheduling tasks in an operating system. You’d want to use a heap (or priority queue), and heap sort could be your go-to method to sort these tasks by priority.

Heap sort’s ability to manage data in constant memory while guaranteeing a stable time complexity makes it ideal in systems where deterministic performance is critical.

Conclusion

In conclusion, the heap sort program in C++ isn’t as daunting as it seems. With a solid understanding of heaps and how the algorithm works, you can easily implement it for practical use cases. It’s efficient, and although it may not be the fastest algorithm in all cases, its consistency and reliability make it a valuable tool in a developer’s toolkit.

So, the next time you need to sort a dataset efficiently—especially in the context of priority-based systems—heap sort might just be your best friend. Give it a try and see how it works for you!

Related Posts

Scroll to Top