# 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, &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);

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.