Heap sort is one of the fastest sorting algorithms.

It uses binary heap data structure and its time complexity is O(Log n).

  • In this sorting algorithm, we first build a heap using the given elements.
  • If we want to sort the elements in ascending order, we create a Min Heap.
  • If we want to sort the elements in descending order, we create a Max Heap.
  • We delete the root node from heap and put last node into root position and repeat the steps until covered all the elements.

Please remember that min heap is when all nodes are the greater than or equal to its parent node.

Lets apply the heap sort and see how it woks internally.

Implementation:

C

#include <stdio.h>

void heapify(int arr[], int n, int i) ;
void heapSort(int arr[], int n);
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // Initialize largest as root 
    int l = 2*i + 1; // left = 2*i + 1 
    int r = 2*i + 2; // right = 2*i + 2 
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 
    if (largest != i) 
    { 
       
        heapify(arr, n, largest); 
    } 
} 
void heapSort(int arr[], int n) 
{ 
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 
    for (int i=n-1; i>=0; i--) 
    { 
        swap(arr[0], arr[i]);
        heapify(arr, i, 0); 
    } 
} 
void printArray(int arr[], int n) 
{ 
    for (int i=0; i<n; ++i) 
        printf("%d",arr[i]);
    printf("\n");	    
} 
int main() 
{ 
    int arr[] =  {11, 20, 6, 2, 5, 1}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    heapSort(arr, n); 
    printf("Sorted array is \n"); 
    printArray(arr, n); 
}

C++

#include <iostream> 
using namespace std; 
  
void heapify(int arr[], int n, int i) 
{ 
    int largest = i;  
    int l = 2*i + 1; 
    int r = 2*i + 2; 
  
   
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 
  
    
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 
  
     
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 
  
        
        heapify(arr, n, largest); 
    } 
} 
  

void heapSort(int arr[], int n) 
{ 
    
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 
  
    
    for (int i=n-1; i>=0; i--) 
    { 
        
        swap(arr[0], arr[i]); 
  
        
        heapify(arr, i, 0); 
    } 
} 
  

void printArray(int arr[], int n) 
{ 
    for (int i=0; i<n; ++i) 
        cout << arr[i] << " "; 
    cout << "\n"; 
} 
  

int main() 
{ 
    int arr[] = {11, 20, 6, 2, 5, 1}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
  
    heapSort(arr, n); 
  
    cout << "Sorted array is \n"; 
    printArray(arr, n); 

Java

public class HeapSort 
{ 
    public void sort(int arr[]) 
    { 
        int n = arr.length; 
  
        
        for (int i = n / 2 - 1; i >= 0; i--) 
            heapify(arr, n, i); 
  
        
        for (int i=n-1; i>=0; i--) 
        { 
            int temp = arr[0]; 
            arr[0] = arr[i]; 
            arr[i] = temp; 
  
            
            heapify(arr, i, 0); 
        } 
    } 
  
    
    void heapify(int arr[], int n, int i) 
    { 
        int largest = i;  
        int l = 2*i + 1; 
        int r = 2*i + 2; 
  
        
        if (l < n && arr[l] > arr[largest]) 
            largest = l; 
  
        
        if (r < n && arr[r] > arr[largest]) 
            largest = r; 
  
        
        if (largest != i) 
        { 
            int swap = arr[i]; 
            arr[i] = arr[largest]; 
            arr[largest] = swap; 
  
           
            heapify(arr, n, largest); 
        } 
    } 
  
   
    static void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i]+" "); 
        System.out.println(); 
    } 
  
    
    public static void main(String args[]) 
    { 
        int arr[] = {11, 20, 6, 2, 5, 1}; 
        int n = arr.length; 
  
        HeapSort ob = new HeapSort(); 
        ob.sort(arr); 
  
        System.out.println("Sorted array is"); 
        printArray(arr); 
    } 
}

Python

def heapify(arr, n, i): 
    largest = i # Initialize largest as root 
    l = 2 * i + 1     
    r = 2 * i + 2     
  
    # See if left child of root exists and is 
    # greater than root 
    if l < n and arr[i] < arr[l]: 
        largest = l 
  
    # See if right child of root exists and is 
    # greater than root 
    if r < n and arr[largest] < arr[r]: 
        largest = r 
  
    # Change root, if needed 
    if largest != i: 
        arr[i],arr[largest] = arr[largest],arr[i] # swap 
  
        # Heapify the root. 
        heapify(arr, n, largest) 
  
# The main function to sort an array of given size 
def heapSort(arr): 
    n = len(arr) 
  
    for i in range(n, -1, -1): 
        heapify(arr, n, i) 
  
  
    for i in range(n-1, 0, -1): 
        arr[i], arr[0] = arr[0], arr[i] # swap 
        heapify(arr, i, 0) 
  
# Driver code to test above 
arr = [11, 20, 6, 2, 5, 1] 
heapSort(arr) 
n = len(arr) 
print ("Sorted array is") 
for i in range(n): 
    print ("%d" %arr[i])

Few Interview questions on Quick Sort:

Question: What is the best, average and worst case time complexity of quick sort ?

Answer:

  • Worst Case: O(n log n) .
  • Avegare Case: O(n log n)
  • Best Case: O(n log n)

Question: Which heap is used when we would like to achieve sorting ascending order and descending order?

Answer:

  • Ascending Order: Min Heap
  • Descending Order: Max Heap

That’s all I have and thanks a lot for reading. Please let me know if any corrections/suggestions. Please do share and comments if you like the post. Thanks in advance… 😉

Thanks a lot Abhijeet Gupta helping us to grow day by day. Abhijeet is a expert in the data structure and loves to solve complex programming questions.


0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert