C Programming Data Structures Heap Sort Complete Guide

Step 1: Understand the Binary Heap

A binary heap is a special complete binary tree that satisfies the heap property. There are two types of binary heaps:

1. Max Heap: In this heap, for any given node, the value of that node is greater than or equal to the values of its children.
2. Min Heap: In this heap, for any given node, the value of that node is less than or equal to the values of its children.

For Heapsort, we will use a max heap, as it simplifies the process of finding the maximum element.

Step 2: Build the Max Heap

To sort an array using Heapsort, we first need to build a max heap from the input array. This involves heapifying each non-leaf node starting from the last non-leaf node up to the root node.

Step 3: Perform Heapsort

Once we have a max heap, we can repeatedly extract the maximum element (which will be at the root) and place it at the end of the array. After extracting the maximum element, we reduce the heap size by one and then heapify the root. We repeat this process until the heap size becomes zero.

Complete Example in C

Let's implement Heapsort in C with detailed comments for clarity.

#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
// n is size of heap
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);
    }
}

// Main function to perform heapsort
void heapSort(int arr[], int n) {
    // Build heap (rearrange array)
    for (int i = n/2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // One by one extract an element 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 an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver program to test above functions
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr)/sizeof(arr[0]);

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

    heapSort(arr, n);

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

    return 0;
}

Step-by-Step Explanation

1. Swap Function:

   void swap(int *a, int *b) {
       int temp = *a;
       *a = *b;
       *b = temp;
   }
   

   This utility function swaps two integer elements.

2. Heapify Function:

   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);
       }
   }
   

   The heapify function ensures that the subtree rooted at index i satisfies the max heap property. It does this by comparing the current node (arr[i]) with its children (arr[2*i + 1] and arr[2*i + 2]). If either child is larger, it swaps the current node with the largest child and recursively calls heapify on the affected subtree.

3. HeapSort Function:

   void heapSort(int arr[], int n) {
       // Build heap (rearrange array)
       for (int i = n/2 - 1; i >= 0; i--)
           heapify(arr, n, i);
   
       // One by one extract an element 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);
       }
   }
   

   The heapSort function first builds a max heap from the input array by calling heapify from the last non-leaf node up to the root. Then, it performs the extraction step by repeatedly swapping the root of the heap (the maximum element) with the last element of the heap and reducing the heap size by one before calling heapify again to reestablish the max heap property.

4. Utilties Functions and Main Program:

   // Function to print an array
   void printArray(int arr[], int n) {
       for (int i = 0; i < n; i++)
           printf("%d ", arr[i]);
       printf("\n");
   }
   
   // Driver program to test above functions
   int main() {
       int arr[] = {12, 11, 13, 5, 6, 7};
       int n = sizeof(arr)/sizeof(arr[0]);
   
       printf("Original array: \n");
       printArray(arr, n);
   
       heapSort(arr, n);
   
       printf("Sorted array: \n");
       printArray(arr, n);
   
       return 0;
   }
   

   In the main function, we define an array arr[] and calculate its size n. We then print the original array, call heapSort to sort the array, and finally print the sorted array.

Output of the Code