## Write a Java program to implement HeapSort Algorithm.

Category : Java | Sub Category : Java Programs | By Prasad Bonam Last updated: 2021-04-19 09:09:52 Viewed : 680

Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. Then repeat the same process for the remaining element. Let’s write the program and understand its working.

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061 `package` `runnerdev;``public` `class` `HeapSort``{``public` `void` `sort(``int` `arr[])``{``int` `n = arr.length;``// Build heap (rearrange array)``for` `(``int` `i = n / ``2` `- ``1``; i >= ``0``; i--)``heapify(arr, n, i);``// One by one extract an element from heap``for` `(``int` `i=n-``1``; i>=``0``; i--)``{``// Move current root to end``int` `temp = arr[``0``];``arr[``0``] = arr[i];``arr[i] = temp;``// call max heapify on the reduced heap``heapify(arr, i, ``0``);``}``}``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 left child is larger than root``if` `(l< n && arr[l] >arr[largest])``largest = l;``// If right child is larger than largest so far``if` `(r < n && arr[r] > arr[largest])``largest = r;` `// If largest is not root``if` `(largest != i)``{``int` `swap = arr[i];``arr[i] = arr[largest];``arr[largest] = swap;``// Recursively heapify the affected sub-tree``heapify(arr, n, largest);``}``}``/* A utility function to print array of size n */``static` `void` `printArray(``int` `arr[])``{``int` `n = arr.length;``for` `(``int` `i=``0``; i

Output:

 1 `5``,``6``,``7``,``11``,``12``,``13`