Heap Sort in Descending 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 Descending Order using the Heap Sort algorithm.

Heap Sort is a popular comparison-based sorting technique that employs binary heap properties. In the context of sorting an array in descending order, a min-heap is created. The smallest element (the root of the heap) is repeatedly extracted and the heap is adjusted until it's empty, resulting in a sorted array in descending order. Let's dive into the details of this algorithm in C++.

2. Program Overview

1. heapify(): A function to ensure the tree rooted at a given node is a min-heap.

2. heapSort(): The main function executing the heap sort algorithm.

3. printArray(): A utility function to display the array.

4. main(): The driver function to demonstrate the heap sort.

3. Code Program

#include<iostream>
using namespace std;

// To heapify a subtree rooted at the given index.
void heapify(int arr[], int n, int i) {
    int smallest = i;   // Initialize smallest as root
    int l = 2*i + 1;    // left child
    int r = 2*i + 2;    // right child

    // If left child is smaller than the root
    if (l < n && arr[l] < arr[smallest])
        smallest = l;

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

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

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

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

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

// 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 in descending order is: \n";
    printArray(arr, n);
}

Output:

Original array is:
12 11 13 5 6 7 
Sorted array in descending order is: 
13 12 11 7 6 5 

4. Step By Step Explanation

1. heapify(): This function is tailored to create a min-heap. The smallest element will always be at the root.

2. heapSort(): Initially, a min-heap is formed from the array. The root of the heap, which is the smallest element, is repeatedly swapped with the last unsorted element in the array, placing it in its correct position.

3. printArray(): A basic utility function to show the elements of the array.

4. main(): The main function demonstrates the functionality of heap sort using a test array.

This version of Heap Sort works by creating a min-heap to sort the array in descending order. The process ensures that the smallest element is always at the root of the heap. By swapping the root with the last unsorted element of the array and reducing the size of the heap, we position the smallest element at its correct spot in the sorted array.

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++