Heap Sort in C - Sorting Algorithm

Introduction to Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It works by first building a max heap from the input array, then repeatedly extracting the largest element from the heap and placing it at the end of the array.

A binary heap is a complete binary tree where each node is greater than or equal to its children (max heap) or less than or equal to its children (min heap). Heap Sort uses a max heap to sort in ascending order.

Key characteristics of Heap Sort:

• In-place algorithm: Sorts the array without using extra memory
• Not stable: Does not preserve the relative order of equal elements
• Guaranteed O(n log n) performance: Works consistently well
• Useful for priority queues: Efficient for finding largest/smallest elements

C Program for 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 at index i
// n is the size of the heap
void heapify(int arr[], int n, int i) {
    int largest = i;       // Initialize largest as root
    int left = 2 * i + 1;  // Left child index
    int right = 2 * i + 2; // Right child index

    // 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, swap and continue heapifying
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        // Recursively heapify the affected subtree
        heapify(arr, n, largest);
    }
}

// Main function to perform heap sort
void heapSort(int arr[], int n) {
    // Build max heap (rearrange array)
    // Start from the last non-leaf node
    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 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 to test the heap sort
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7, 1, 9, 3, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    heapSort(arr, n);

    printf("Sorted array:   ");
    printArray(arr, n);

    return 0;
}

Sample Output

Original array: 12 11 13 5 6 7 1 9 3 10
Sorted array:   1 3 5 6 7 9 10 11 12 13

Another Example:

Original array: 45 23 78 12 56 34 89 10 67 90
Sorted array:   10 12 23 34 45 56 67 78 89 90

Program Explanation

Let's break down the code step by step:

1. Include Header File: #include <stdio.h> includes the standard input/output library.
2. Swap Function: swap() exchanges two integer values using a temporary variable.
3. Heapify Function:
   • Takes an array, heap size n, and index i
   • Finds the largest among root, left child, and right child
   • If root is not largest, swaps and recursively heapifies the affected subtree
   • This maintains the max heap property
4. HeapSort Function:
   • Step 1 - Build Max Heap: Starting from the last non-leaf node (n/2 - 1) up to root, call heapify
   • Step 2 - Extract Elements: Swap root (largest) with last element, reduce heap size, heapify the new root
   • Repeat until all elements are sorted
5. PrintArray Function: Displays all elements of the array.
6. Main Function:
   • Creates an unsorted array
   • Displays the original array
   • Calls heapSort() to sort
   • Displays the sorted array

Step-by-Step Approach

Algorithm for Heap Sort

1. Build Max Heap:
   • For i = n/2 - 1 down to 0:
     • Call heapify(arr, n, i)
2. Sort:
   • For i = n - 1 down to 1:
     • Swap arr[0] and arr[i]
     • Call heapify(arr, i, 0)
3. Done: Array is now sorted in ascending order

Time & Space Complexity

// To sort in descending order, use MIN HEAP instead of MAX HEAP
// Change the comparison in heapify function:

if (left < n && arr[left] < arr[smallest]) {
    smallest = left;
}

if (right < n && arr[right] < arr[smallest]) {
    smallest = right;
}

// This creates a min heap, resulting in descending order
// after extraction.

int findKthLargest(int arr[], int n, int k) {
    // Build max heap
    for (int i = n/2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    
    // Extract k-1 elements
    for (int i = n-1; i > n-k; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
    return arr[0]; // kth largest
}

Frequently Asked Questions

Previous Topic: -->> Quick Sort in C   ||   Next topic: -->> Merge Sort in C