Heap Sort

July 6, 2019

Heap Sort in Java

Heap Sort is a comparison based sorting technique, used for sorting linear data structures, it got it name because, it is based on Binary Heap Data Structures. Heap resembles a complete binary tree.

A complete binary tree is a tree in which each parent node has exactly two child nodes, and its all the levels are completely filled, except the possible last level, in which all the nodes are as far as possible.

Heap sort, sorts the array by converting them into heaps, which are then converted into min heap and max heap, as required.
The converted Heaps have the largest element at the top node, and after each iteration we remove the root node from the heap, and move it to it right position in the array, you can have a better idea on the implementation by following the pictorial representation below

Implementation Of Heap Sort

Now, since this tree is already in the max heap form, we don’t need to make any changes, we just swap the last node with the root node
After switching the nodes, we remove the last node of the tree

We have our first digit in its place.
Now, we,ll again create a max heap with the remaining nodes, and repeat the above procedure

Code for Heap Sort in Java


// Java program for implementation of Heap Sort 
public class PrepInsta
{ 
    //Main() for the execution of the program 
    public static void main(String args[]) 
       { 
          int a[] = {12, 11, 13, 5, 6, 7}; 
          int len = a.length; 

           PrepInsta ob = new PrepInsta(); 
           ob.sort(a); 

            System.out.println("Sorted array is"); 
            printArray(a); 
       } 
           public void sort(int a[]) 
               { 
                  int len = a.length; 

                 // Build heap (rearrange array) 
                 for (int i = len / 2 - 1; i >= 0; i--) 
                 heapify(a, len, i); 

                 // One by one extract an element from heap 
                 for (int i=len-1; i>=0; i--) 
                       { 
                         // Move current root to end 
                          int temp = a[0]; 
                          a[0] = a[i]; 
                          a[i] = temp; 

                           // call max heapify on the reduced heap 
                           heapify(a, i, 0); 
                          } 
                  }  

         // To heapify a subtree rooted with node i which is 
        // an index in arr[]. n is size of heap 
       void heapify(int a[], int len, 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 left child is larger than root 
               if (l < len && a[l] > a[largest]) 
               largest = l; 

               // If right child is larger than largest so far 
               if (r < len && a[r] > a[largest]) 
               largest = r; 

               // If largest is not root 
               if (largest != i) 
                     { 
                        int swap = a[i]; 
                        a[i] = a[largest]; 
                        a[largest] = swap; 

                       // Recursively heapify the affected sub-tree 
                         heapify(a, len, largest); 
                       } 
                   } 

           /* A utility function to print array of size n */
           static void printArray(int a[]) 
                 { 
                     int len = a.length; 
                     for (int i=0; i<len; ++i) 
                     System.out.print(a[i]+" "); 
                     System.out.println(); 
                  } 


      }

Please Login/Signup to comment