C Program: Heap Sort in Ascending Order

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[0], &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[0]);

    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.

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