# 1. Introduction

Heap Sort is a comparison-based sorting algorithm that utilizes the binary heap data structure. By repeatedly removing the maximum element from the heap and reconstructing it, the array can be sorted in ascending order. Heap Sort is in-place and doesn't require any additional storage.

# 2. Program Overview

The program's structure is as follows:

1. heapify: A function that ensures the array satisfies the properties of a heap.

2. heapSort: The primary function that implements the Heap Sort algorithm.

3. printArray: A utility function to display the contents of the array.

4. main: The main function where the program execution starts.

# 3. Code Program

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

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

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

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

// If right child is larger than the current largest
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 sub-tree
heapify(arr, n, largest);
}
}

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

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

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

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

// Driver program
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 is: \n");
printArray(arr, n);
return 0;
}
``````

### 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. heapSort starts by building a max heap using the heapify function. This ensures the largest element of the array is placed at the root.

2. The maximum element (at the root) is then swapped with the last element of the array.

3. After the swap, the last element is the largest and is in its correct final position.

4. The heap size is reduced by one (excluding the last element which is already in place), and the heapify function is called for the root.

5. The process is repeated until the whole array is sorted.

Heap Sort ensures that at every stage, the largest element is placed in its correct position, thus sorting the array in ascending order. It has a time complexity of O(n log n) due to the logarithmic nature of the heapification process.