C Program to Implement Heap Sort

Introduction

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It’s an in-place, non-stable sorting algorithm with a time complexity of O(n log n). The algorithm builds a max-heap from the input data and then repeatedly extracts the maximum element (which is at the root) and rebuilds the heap until all elements are sorted.

Example:

• Input: Unsorted array [4, 10, 3, 5, 1]
• Output: Sorted array [1, 3, 4, 5, 10]

Problem Statement

Create a C program that:

• Implements the Heap Sort algorithm to sort an array.
• Takes an unsorted array as input and outputs the sorted array.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> for standard input-output functions.
2. Implement the Heapify Function: This function ensures that a subtree rooted at a given index satisfies the heap property.
3. Implement the Heap Sort Function: This function builds the heap and then sorts the array.
4. Create a Main Function: Allow the user to input the array, apply heap sort, and display the sorted array.

C Program to Implement Heap Sort

#include <stdio.h> // Function to swap two elements void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // Function to heapify a subtree rooted with node i, which is an index in arr[]. void heapify(int arr[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left < n && arr[left] > arr[largest]) largest = left; // If right child is larger than largest so far 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 subtree heapify(arr, n, largest); } } // Function to implement Heap Sort void heapSort(int arr[], int n) { // Build a maxheap 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--) { // Move current root to end swap(&arr[0], &arr[i]); // Call heapify on the reduced heap heapify(arr, i, 0); } } int main() { int n; // Input the size of the array printf("Enter the number of elements in the array: "); scanf("%d", &n); int arr[n]; // Input the elements of the array printf("Enter %d elements:\n", n); for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); } // Apply Heap Sort heapSort(arr, n); // Output the sorted array printf("Sorted array: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; // Return 0 to indicate successful execution } 

Explanation

Function to Swap Two Elements

• The swap function exchanges the values of two variables using a temporary variable.

Function to Heapify a Subtree

• The heapify function ensures that the subtree rooted at a given index i satisfies the heap property. If the root is not the largest element, it swaps the root with the largest child and then recursively heapifies the affected subtree.

Function to Implement Heap Sort

• The heapSort function first builds a max heap by calling heapify on all non-leaf nodes.
• After building the heap, the function repeatedly extracts the largest element (the root of the heap) by swapping it with the last element and then reducing the heap size by one. It then heapifies the reduced heap to maintain the heap property.

Main Function

• The main function allows the user to input the size of the array and the elements.
• It then applies Heap Sort to the array and displays the sorted array.

Output Example

Example Output:

Enter the number of elements in the array: 5 Enter 5 elements: 4 10 3 5 1 Sorted array: 1 3 4 5 10 

Example Output (Already Sorted):

Enter the number of elements in the array: 6 Enter 6 elements: 1 2 3 4 5 6 Sorted array: 1 2 3 4 5 6 

Conclusion

This C program demonstrates how to implement Heap Sort, a popular sorting algorithm known for its efficiency and in-place sorting capability. Heap Sort is particularly useful when a stable sort is not required, and it provides a reliable O(n log n) time complexity, making it suitable for large datasets. This program is a practical example of heap operations and sorting in C programming.