Heap Sort in Data Structure

Heap Sort

A heap is a tree-based data structure that has specific properties.

• Heap is always a complete binary tree (CBT). That is, all the nodes of the tree are completely filled.
• If the value placed in each node is greater than or equal to its two children, then that heap is called max heap.
• If the value placed in each node is less than or equal to its two children, then that heap is called min-heap.
• If you want to sort the list in ascending order (increasing order), then you create the min-heap.
• If you want to sort the list in descending order (decreasing order), then you create the max heap.

Complexity table of Heap sort

Complexity	Best case	Average case	Worst case
Time	O(nlogn)	O(nlogn)	O(nlogn)
Space			O(1)

Selection sort algorithm

Heapsort (A) 
Build_Max_heap(A)
for i ? length[A] down to 2
do exchange A[i] ? A[1]
heapsize(A) ? heapsize (A – 1)
Max_heapify (A, 1)  

This algorithm is for max heap sort.

Step 1: Create a new node.

Step 2: Assign a value to the node.

Step 3: Compare the value of the child node with the value of the parent node.

Step 4: If the child node value is greater than the parent node value, then interchange them. 

Step 5: Repeat steps 3 and 4 until the heap is sorted correctly.

Build_Max_heap(A)
heapsize(A) ? length[A]
for i ? length[A / 2] down to 1
Max_heapify (A, i)  

Max_heapify (A, i)
 l ? left[i]
r ? right[i]if l <= heapsize(A) and A[l] > A[i]
then largest ? l
also, largest ? iif r <= heapsize(A) and A[r] > A[largest]then largest ? rdo if i ? largestexchange A[i]  ? A[largest]Max_heapify (A, largest)  

Heap sort program in C language

#include<stdio.h>  
int val; 
void heapify(int arr[], int size, int i)
{      
int largest = i;       
int left = 2*i + 1;     
 int right = 2*i + 2;      
  if (left < size && arr[left] >arr[largest])         largest = left;      if (right < size && arr[right] > arr[largest])         largest = right;      if (largest != i)       
 {          
 val = arr[i];          
  arr[i]= arr[largest];        
     arr[largest] = val;         
   heapify(arr, size, largest);       
   }   
}     
 void heapSort(int arr[], int size) 
  {  
      int i;      
  for (i = size / 2 - 1; i >= 0; i--)      
 heapify(arr, size, i);      
  for (i=size-1; i>=0; i--)      
 {           
 val = arr[0];  
          arr[0]= arr[i];      
       arr[i] = val;         
   heapify(arr, i, 0);      
  }  
 }    
  void main() 
  {     
      int arr[] = {20, 50, 40, 10, 90, 80, 60, 70, 30, 100};   
        int i;     
      int size = sizeof(arr)/sizeof(arr[0]);   
       heapSort(arr, size);   
       printf("heap sorted elements\n");  
         for (i=0; i<size; ++i)      
    printf("%d\n",arr[i]);   }    

Output

heap sorted elements
10 
20 
30 
40 
50 
60 
70 
80 
90 
100  

Heap sort program in java language

public class HeapSort      
{       
public void sort(int arr[])       
  {            
int n = arr.length;        // Build max heap         
    for (int i = n / 2 - 1; i >= 0; i--)          
   {          
       heapify(arr, n, i);       
     }                // Heap sort     
 for (int i = n - 1; i >= 0; i--)    
   {       
    int temp = arr[0];    
    arr[0] = arr[i];    
    arr[i] = temp;             // Heapify root element        
 heapify(arr, i, 0);  
     }  
  } 
 void heapify(int arr[], int n, int i)
 {       // Find largest among root, left child and right child             
   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;            // Swap and continue heapifying if root is not largest        
 if (largest != i)      
   {          
  int swap = arr[i];   
         arr[i] = arr[largest];  
          arr[largest] = swap;    
       heapify(arr, n, largest);   
      }
 }              // Function to print an array       
 static void printArray(int arr[])  
        {          
    int n = arr.length;  
            for (int i = 0; i < n; ++i) 
             System.out.print(arr[i] + " ");       
       System.out.println();        
  }            // Driver code   public static void main(String args[]) 
     {      
   int arr[] = { 20, 50, 40, 10, 90, 80, 60, 70, 30, 100 }; 
        HeapSort hs = new HeapSort();     
    hs.sort(arr);     
    System.out.println("heap sorted elements");   
      printArray(arr);   
   } 
}

Output

heap sorted elements 
10
20 
30 
40 
50 
60 
70 
80 
90 
100