











Heap Sort in Java
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.


Heap Sort in Java
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


Working of Heap Sort in Java








Implementation Of Heap Sort
- 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
- 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


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(); } }
Login/Signup to comment