Heap Sort in Data Structure: Algorithm Working, Examples, Types

Heap sort is a sorting algorithm that follows the heap algorithm to convert a list of unsorted elements into a heap structure, and then sorts the heap. This algorithm has a time complexity of O(n log n), making it suitable for large datasets. Instead of other sorting algorithms such as quicksort or merge sort, heap sort guarantees O(n log n) performance for both best and worst cases, making it a reliable sorting method.

Data structures that satisfy the heap property are specialized binary tree-based structures. Heaps are usually represented as binary heaps and come in two main types:

• Max heap: In a max heap, the value of the parent node is greater than or equal to the values of its children. This ensures that the largest element is always at the root.
• Min heap: Nodes that have a value less than or equal to the value of their children are called min heaps. The smallest node in a min-heap is at the root.

Heaps are typically used to implement priority queues, where the highest or lowest priority element must be accessed quickly.

HeapSort uses the Max-Heap structure to sort an array. The main idea behind HeapSort is to:

Build a Max-Heap from the input array.

• Swap the root (maximum value) with the last element in the array.
• Reduce the heap size by 1 (excluding the sorted elements at the end).
• Re-heapify the heap to restore the heap property.

The heap sort algorithm uses a binary heap data structure to perform comparison-based sorting. It works in two major phases: 

• Building the Max-Heap 
• Extracting Root and Sort the array

Let’s take an example of the unsorted array: [45, 21, 67, 34, 89, 12, 56, 90, 72]

1. Building the Max-Heap

To begin with, we need to convert the given array into a max heap. The max-heap consists of a binary tree in which each parent node is greater than its child nodes. We'll heapify the array starting from the last non-leaf node.

Here are a few steps to build the max heap:

Step 1: The last non-leaf node is at index 3 (element 34). We begin by heapifying this subtree. 

After heapifying:

        45
       /  \
     21    67
    /  \   / \
  34   89 12  56
 /  \
90  72

Step 2: We heapify node 67. After heapifying, the array becomes:

         45
       /   \
     67     56
    /  \   /  \
  34   89 12  21
 /   \
90  72

Step 3: Now, we heapify node 21. After heapifying, the tree looks like this:

        45
       /  \
     67    56
    /  \   / \
  89   72 12  21
 /  \
90  34

Step 4: Finally, we heapify the root node (45). After heapifying, the array becomes:

        90
       /  \
     89    56
    /  \   / \
  72   67 12  21
 /  \
34  45

Step 5: Finally, the max heap array: [90,89,56,72,67,12,21,34,45]

2. Extracting the Root and Sorting the Array

Now that we have a max-heap, we can start extracting the root (largest element) and placing it at the end of the array.

Let us take an array of max heap to extract the root of the sorted array: [90,89,56,72,67,12,21,34,45]

Here are the steps to extract the root:

Step 1: Swap the root with the last element (90 and 45). Then remove the last element (90).

        90
       /  \
     89    56
    /  \   / \
  72   67 12  21
 /  \
34  45 

Step 2: The largest child of 45 is 89, so swap 45 with 89. Now the heap is no longer a max heap, so continue heapifying down.

        89
       /  \
     45    56
    /  \   /  \
  72   67 12  21
 /  \
34

Step 3: Heapify the subtree rooted at 45. The largest child is 72

        89
       /  \
     72    56
    / \    / \
  45   67 12  21
 /  \
34

Step 4: Heapify the subtree rooted at 45. Swap the largest child of 45 is 34.

        89
       /  \
     72    56
    /  \   / \
  34   67 12  21
 /  \
45

Step 5: Extract the next root (89), swap with the last element (45), and heapify the root. Now, Swap 89 with 45, and remove 89. 

The largest child of 45 is 72, so swap 45 with 72. After heapify:

        72
       /  \
     45    56
    /  \   / \
  34   67 12  21

Step 6: Heapify the subtree rooted at 45. The largest child of 45 is 67, so swap 45 with 67.

        72
       /  \
     67    56
    /  \   /  \
  34   45 12  21

Step 7: Extract the next root (72), swap with the last element (21), and heapify the root.

        67
       /  \
     45    56
    /  \   /  
  34   21 12 

Step 8: Now, heapify the subtree rooted at 21. Since the largest child of 21 is 34, swap 21 with 34.

        67
       /  \
     45    56
    /  \   
  34   21

Step 9: Extract the next root (67), swap with the last element (12), and heapify the root.

        56
       /  \
     45    12
    /  \   
  34   21

Step 10: Finally, by performing all steps we get a sorted array is [12,21,34,45,56,67,72,89].

Here are the programs of heap sort in C, C++ and Java language:

C Program

#include <stdio.h>

// Function to heapify the 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

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

    // Check if right child is larger than largest so far
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // Change root, if needed
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

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

// Main function to implement heapsort
void heapSort(int arr[], int n) {
    // Build a maxheap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

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

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

// Function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Driver code
int main() {
    int arr[] = {90,89,56,72,67,12,21,34,45};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Unsorted array: \n");
    printArray(arr, n);

    heapSort(arr, n);

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

    return 0;
}

C++ Program

#include <iostream>
using namespace std;

// Function to heapify the 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

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

    // Check if right child is larger than largest so far
    if (right < n && arr[right] > arr[largest])
        largest = right;
 // Change root, if needed
    if (largest != i) {
        swap(arr[i], arr[largest]);

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

// Main function to implement heapsort
void heapSort(int arr[], int n) {
    // Build a maxheap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Extract elements from heap one by one
    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);
    }
}

// Function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Driver code
int main() {
    int arr[] = {90,89,56,72,67,12,21,34,45};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Unsorted array: \n";
    printArray(arr, n);

    heapSort(arr, n);
cout << "Sorted array: \n";
    printArray(arr, n);

    return 0;
}

Java

import java.util.*;

public class Heapsort {

    // Function to heapify the subtree rooted at index i
    public static 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

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

        // Check if right child is larger than largest so far
        if (right < n && arr[right] > arr[largest])
            largest = right;

        // Change root, if needed
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

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

    // Main function to implement heapsort
    public static void heapSort(int arr[]) {
        int n = arr.length;

        // Build a maxheap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

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

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

    // Function to print the array
    public static void printArray(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int arr[] = {90,89,56,72,67,12,21,34,45};
        System.out.println("Unsorted array: ");
        printArray(arr);

        heapSort(arr);

        System.out.println("Sorted array: ");
        printArray(arr);
    }
}

Output

Unsorted array: 
90 89 56 72 67 12 21 34 45 
Sorted array: 
12 21 34 45 56 67 72 89 90

Here are the advantages and disadvantages of Heap Sort in data structures:

Advantages

• Heap sort does not require additional memory, as it sorts the array in place.
• It guarantees O(n log n) time complexity in all cases (best, worst, and average).
• Instead of other sorting algorithms (like quicksort), heap sort does not suffer from worst-case performance.

Disadvantages

• Heap sort is not a stable sorting algorithm, meaning that equal elements may not retain their original order.
• The performance of heap sort does not improve with partially sorted data.

Here's an overview of its time complexity and space complexity across different cases:

In conclusion, heap sort is a sorting algorithm based on a binary heap data structure. It has a time complexity of O(n log n) in both the average and worst cases, making it more predictable than algorithms like QuickSort in terms of performance. Heap Sort requires only a constant amount of extra space, which makes it memory efficient. While not stable, its ability to sort efficiently and its suitability for scenarios where memory constraints are important makes it a valuable tool for various applications, especially in priority queue operations.

1. Is heap sort stable?

No, heap sort is not a stable sorting algorithm, meaning that it does not guarantee that equal elements will maintain their relative order.

2. How does heap sort work?

Heap sort works by building a heap from the input array, then repeatedly extracting the maximum (or minimum) element and rebuilding the heap until the array is sorted.