# Heap Sort

## 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;                           a = 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();                   }       }   `