Heap Sort in Data Structures

Heap Sort

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 utmost two children.

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

What is a Heap sort?

Heapsort is an efficient and popular sorting algorithm.

Heap sort 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

Case	Time Complexity
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n log n)

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

Space Complexity	O(1)
Stable	No

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

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

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