C Program: Heap Sort in Descending Order

1. Introduction

Heap Sort is a powerful comparison-based sorting technique, employing a binary heap data structure. It systematically removes the minimum element from the heap and reconstructs the heap to sort an array in descending order. One of Heap Sort's standout features is its in-place sorting ability, eliminating the need for additional storage.

2. Program Overview

The program's key components are:

1. heapify: This function ensures the array aligns with the heap's characteristics.

2. heapSort: The central function implementing the Heap Sort algorithm.

3. printArray: A handy function to showcase the array's elements.

4. main: The primary function signifying the start of program execution.

3. Code Program

#include <stdio.h>
#include <stdlib.h>

// Swapping two elements
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Guaranteeing the subtree rooted with node 'i' is a min heap
void heapify(int arr[], int n, int i) {
    int smallest = i;  // Initialize smallest as root
    int left = 2 * i + 1;
    int right = 2 * i + 2;

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

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

    // If smallest isn't the root
    if (smallest != i) {
        swap(&arr[i], &arr[smallest]);

        // Recursively heapify the affected sub-tree
        heapify(arr, n, smallest);
    }
}

// Main heapSort function
void heapSort(int arr[], int n) {
    // Build a min heap
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // Extract elements from heap one at a time
    for (int i = n - 1; i > 0; i--) {
        // Move the current root to the end
        swap(&arr[0], &arr[i]);

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

// Utility function to display array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

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

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

    heapSort(arr, n);

    printf("Sorted array in descending order is: \n");
    printArray(arr, n);
    return 0;
}

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. The heapSort function initializes by constructing a min heap using the heapify function, ensuring the smallest array element occupies the root.

2. Following this, the smallest element (at the root) gets swapped with the last element.

3. After the swap, the array's last element is its smallest and occupies its correct final position.

4. Reducing the heap size by one (disregarding the correctly placed last element), the heapify function is recalled for the root.

5. This procedure continues until sorting is achieved for the whole array.

Through this mechanism, Heap Sort ensures the smallest element is consistently placed in its rightful position, culminating in an array sorted in descending order. The process boasts a time complexity of O(n log n) given the logarithmic nature inherent to the heapification.

Related C Programs on Sorting Algorithms

1. Bubble Sort in Ascending Order in C
2. Bubble Sort in Descending Order in C
3. Selection Sort in Ascending Order in C
4. Selection Sort in Descending Order in C
5. Insertion Sort in Ascending Order in C
6. Insertion Sort in Descending Order in C
7. Merge Sort in Ascending Order in C
8. Merge Sort in Descending Order in C
9. Quick Sort in Ascending Order in C
10. Quick Sort in Descending Order in C
11. Heap Sort in Ascending Order in C
12. Heap Sort in Descending Order in C