Heap Sort in Ascending Order in C++

1. Introduction

In this blog post, we will learn how to write a C++ program to sort an array of integers in Ascending Order using the Heap Sort algorithm.

Heap Sort is a comparison-based sorting algorithm. It utilizes the properties of a binary heap, where the greatest (or smallest) element is always at the root. We build a max heap and then iteratively extract the maximum element to place it in its correct position. 

2. Program Overview

1. heapify(): Function to maintain the heap property.

2. heapSort(): Main function that performs heap sort.

3. printArray(): Utility function to print the array.

4. main(): Driver function to test the above.

3. Code Program

#include<iostream>
using namespace std;

// To heapify a subtree rooted with node i which is an index in arr[].
void heapify(int arr[], int n, int i) {
    int largest = i;  // Initialize largest as root
    int l = 2*i + 1;  // left child
    int r = 2*i + 2;  // right child

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

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

    // If largest is not root
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);  // Recursively heapify the affected subtree
    }
}

// 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);

    // Extract elements from heap one by one
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);  // Move current root to end
        heapify(arr, i, 0);    // Call heapify on the reduced heap
    }
}

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

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

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

    heapSort(arr, n);

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

Output:

Original array is:
12 11 13 5 6 7 
Sorted array is: 
5 6 7 11 12 13 

4. Step By Step Explanation

1. heapify(): Ensures the heap property is maintained. This means the parent node will always have a value greater than or equal to those of its children.

2. heapSort(): Builds a max heap from the array and then extracts the maximum (which will always be at the root of the heap) iteratively and puts it at its correct position in the sorted array.

3. printArray(): A simple utility to print array elements.

4. main(): We test our HeapSort function on a sample array and print before and after sorting.

Building a max heap ensures the maximum element is at the root. By swapping the root with the last item and reducing the size of the heap by one (while ignoring the last element), we effectively place the maximum element in its correct position. The process is repeated until the whole array is sorted.

Related C++ Programs on Sorting Algorithms

• Bubble Sort in Ascending Order in C++
• Bubble Sort in Descending Order in C++
• Selection Sort in Ascending Order in C++
• Selection Sort in Descending Order in C++
• Insertion Sort in Ascending Order in C++
• Insertion Sort in Descending Order in C++
• Merge Sort in Ascending Order in C++
• Merge Sort in Descending Order in C++
• Quick Sort in Ascending Order in C++
• Quick Sort in Descending Order in C++
• Heap Sort in Ascending Order in C++
• Heap Sort in Descending Order in C++