Program 12 : Heap Sort

Develop a program to Implement Heap Sort for n number of elements.

Heap Sort

#include <stdio.h>

// Function to heapify a subtree rooted at index i
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
    int temp;

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

    // If right child is larger than current largest
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // If largest is not root
    if (largest != i) {
        // swap
        temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // Recursively heapify the affected subtree
        heapify(arr, n, largest);
    }
}

// Function to perform heap sort
void heapSort(int arr[], int n) {
    int i, temp;

    // Build max heap (rearrange array)
    for (i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // One by one extract elements from heap
    for (i = n - 1; i > 0; i--) {
        // Move current root to end
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

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

void displayArray(int arr[], int n) {
    printf("Sorted array:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[100], n;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    heapSort(arr, n);
    displayArray(arr, n);

    return 0;
}

---

Explanation of Heap Sort

Heap Sort is a comparison-based sorting technique based on a binary heap data structure. It works in two main phases:

1. Build a Max Heap:

• Arrange the input array into a max heap, where the largest element is at the root.

2. Extract Elements from the Heap:

• Swap the root (maximum value) with the last element.

• Reduce the heap size by one.

• Call heapify() on the root to restore heap property.

• Repeat until the heap size is 1.

---

Time Complexity

Phase	Time
Build Heap	O(n)
Sorting	O(n log n)

• Worst, Best, and Average Case: O(n log n)

• In-place: Yes (does not use extra memory)

• Stable: No (does not maintain the order of equal elements)