With heap sort, the elements are created using the min-heap and max-heap based on the elements of the given array.

In a min-heap or max-heap, the root element represents the minimum or maximum element of the array.

The heap sort recursively performs two main operations –

• Create a heap H with the elements of the array.
• Delete the root element of the heap formed in the first phase repeatedly.

What is a Heap?

A heap is a complete binary tree, and a binary tree is a tree in which a node can have two children.

Complete binary trees are trees in which all the levels except for the last one, i.e., the leaf node, are filled and all the nodes are left-justified.

What is a Heap sort?

Heapsort is an efficient and popular sorting algorithm.

Heap sorting involves removing the elements one by one from the heap part of the list.

Then, insert the elements into the sorted portion of the list.

Time Complexity

Best Case O(n log n): It occurs when there is no sorting needed, i.e. the array is already sorted.

Average Case O(n log n): The array elements are in a jumbled order that is not properly ascending and descending.

Worst Case O(n log n): This occurs when the array elements need to be sorted in reverse order.

Space Complexity

The space complexity of heap sort is O (1).

Example

C Program

#include <stdio.h>  
/* function to heapify a subtree. Here 'i' is the   
index of root node in array a[], and 'n' is the size of heap. */   
void heapify(int a[], int n, int i)  {  
    // Initialize largest as root  
    int largest = i; 
    // left child  
    int left    = 2 * i + 1; 
    // right child  
    int right   = 2 * i + 2; 
    // If left child is larger than root  
    if (left < n && a[left] > a[largest])  
        largest = left;  
        
    // If right child is larger than root  
    if (right < n && a[right] > a[largest])  
        largest = right;  
        
    // If root is not largest  
    if (largest != i) {  
        // swap a[i] with a[largest]  
        int temp    = a[i];  
        a[i]        = a[largest];  
        a[largest]  = temp;  
          
        heapify(a, n, largest);  
    }  
}

/*function to implement the heap sort*/  
void heap_sort(int a[], int n)  {  
    for (int i = n / 2 - 1; i >= 0; i--)  
        heapify(a, n, i);  
        
    // One by one extract an element from heap  
    for (int i = n - 1; i >= 0; i--) {  
        /* Move current root element to end*/  
        // swap a[0] with a[i]  
        int temp    = a[0];  
        a[0]        = a[i];  
        a[i]        = temp;  
          
        heapify(a, i, 0);  
    }  
}  
/* function to print the array elements */  
void print(int arr[], int n)  {  
    for (int i = 0; i < n; ++i) {  
        printf("%d", arr[i]);  
        printf(" ");  
    }  
}  

int main() {  
    int a[] = {42, 12, 17, 25, 40, 10, 33, 31};  
    int n = sizeof(a) / sizeof(a[0]);  
    printf("Before sorting array elements are - n");  
    print(a, n);  
    
    heap_sort(a, n);  
    printf("nAfter sorting array elements are - n");    
    print(a, n);  
    return 0;  
}  

This program implements Heap Sort, a sorting algorithm that uses a data structure called a binary heap. Let’s break it down step by step:

1. heapify Function:

• Purpose: To ensure that a part of the array satisfies the “max-heap” property. In a max-heap:
  • Each parent node is greater than or equal to its child nodes.
• Parameters:
  • a[]: The array representing the heap.
  • n: The size of the heap.
  • i: The index of the current “root” node to be heapified.

How it works:

1. Start with the assumption that the root node at index i is the largest (largest = i).
2. Calculate the indices of the left and right children:
   • Left child: 2 * i + 1
   • Right child: 2 * i + 2
3. Compare the left child with the current largest value.
   • If the left child is larger, update largest.
4. Similarly, compare the right child with the current largest value and update if needed.
5. If largest is no longer the root (i), swap the root with the largest child and call heapify recursively on the affected subtree.

2. heap_sort Function:

• Purpose: To sort the array using the heap structure.

How it works:

1. Build a max-heap:
   • Start from the last non-leaf node (n / 2 - 1) and move upwards, calling heapify to ensure the max-heap property is satisfied.
2. Extract elements one by one:
   • Swap the root (largest element) with the last element in the array.
   • Reduce the heap size (i) and call heapify on the new root to restore the max-heap property.
   • Repeat until the entire array is sorted.

3. print Function:

• Purpose: To display the elements of the array.
• Loops through the array and prints each element with a space in between.

4. main Function:

1. Input: The array a[] = {42, 12, 17, 25, 40, 10, 33, 31}.
2. Output:
   • Before sorting: Displays the original array.
   • After sorting: Displays the sorted array.
3. Calls heap_sort to sort the array using the heap sort algorithm.

Execution Flow:

1. Start with the array: {42, 12, 17, 25, 40, 10, 33, 31}.
2. Build a max-heap: The array is rearranged to satisfy the max-heap property.
3. Extract the largest element (root), place it at the end, and heapify the remaining elements.
4. Repeat until the array is sorted.

Final Output:

Before sorting array elements are - 
42 12 17 25 40 10 33 31 
After sorting array elements are - 
10 12 17 25 31 33 40 42 

Java Program

public class HeapSort {  
    /* function to heapify a subtree. Here 'i' is the   
    index of root node in array a[], and 'n' is the size of heap. */  
    static void heapify(int a[], int n, int i) {  
        // Initialize largest as root  
        int largest = i; 
        // left child  
        int left    = 2 * i + 1; 
        // right child  
        int right   = 2 * i + 2; 
        
        // If left child is larger than root  
        if (left < n && a[left] > a[largest])  
            largest = left;  
            
        // If right child is larger than root  
        if (right < n && a[right] > a[largest])  
            largest = right;  
            
        // If root is not largest  
        if (largest != i) {  
            // swap a[i] with a[largest]  
            int temp    = a[i];  
            a[i]        = a[largest];  
            a[largest]  = temp;  
              
            heapify(a, n, largest);  
        }  
    }  
    
    /*function to implement the heap sort*/  
    static void heapSort(int a[], int n) {  
        for (int i = n / 2 - 1; i >= 0; i--)  
            heapify(a, n, i);  
      
        // One by one extract an element from heap  
        for (int i = n - 1; i >= 0; i--) {  
            /* Move current root element to end*/  
            // swap a[0] with a[i]  
            int temp    = a[0];  
            a[0]        = a[i];  
            a[i]        = temp;  
              
            heapify(a, i, 0);  
        }  
    }  
    
    /* function to print the array elements */  
    static void print(int a[], int n)  {  
        for (int i = 0; i < n; ++i)  
            System.out.print(a[i] + " ");  
    }  
    
    public static void main(String args[]) {  
        int a[] = {42, 12, 17, 25, 40, 10, 33, 31};  
        int n = a.length;  
        System.out.print("Before sorting array elements are - n");
        print(a, n);  
        
        heapSort(a, n);  
        System.out.print("nAfter sorting array elements are - n");
        print(a, n);  
    }  
}  

Execution Flow

1. Input: The array a[] = {42, 12, 17, 25, 40, 10, 33, 31}.
2. Build a max-heap:
   • Rearrange the array so that each parent node is larger than its children.
3. Extract the largest element (root) repeatedly and place it at the end of the array.
4. Reduce the heap size and restore the max-heap property until all elements are sorted.

Output

Before sorting:

Before sorting array elements are - 
42 12 17 25 40 10 33 31 

After sorting:

After sorting array elements are - 
10 12 17 25 31 33 40 42 

Key Points

• Heapify ensures the tree satisfies the max-heap property.
• Heap Sort uses the max-heap to sort the array in ascending order.
• The array is sorted in-place (without using extra space).