# Implement Heap Sort in Java

If you’re in a computer science background, widening your technical horizons is the best thing you should do. However, your programming skills matter the most. And one must continuously keep sharpening these skills, to become a better programmer in the future. Though there are multiple things to focus on, one specific area you must focus on is the world of data structures. Data structures in general are particular approaches to solve problems so that computer resources get used minimum. In general, there are multiple data structures you can learn and implement as well. However, we’ve covered some basic data structures before, so, now we’ll move towards some advanced data structures. Hence, today we’re going to learn how to Implement Heap Sort using Java.

## What is Heap Sort?

- It is a
**comparison-based sorting algorithm**that works on the principles of Binary Heap data structure.

- The algorithm
**creates a heap of input element**s similar to that of binary trees. Elements are divided into sorted and unsorted heaps.

- The largest elements are moved from the unsorted heap to the sorted heap. So the
**smallest element is kept at the top**.

- And this
**process is repeated further till the entire heap gets sorted**.

**Also Read: Implement Bubble Sort using Java**

## What’s The Approach?

- Firstly we’ll
**divide our input array into two parts**i.e, inside thefunction.`heapify()`

- While doing so, we are going to
**start from the middle of the input array**, and**with each iteration, we’re going to decrement the index i by one**.

- While creating heaps, we’ll
**make sure to keep the largest element as the root**(head element).

- The
**above two instructions will continue to execute till we reach the starting index**of the array.

- At the end of the
function, use recursion to sort the sub-heaps as well.`heapify()`

## Java Program To Implement Heap Sort

**INPUT:**

` `

`12`

`, `

`11`

`, `

`13`

`, `

`5`

`, `

`6`

`, `

`7`

**OUTPUT:**

**Sorted array is
5 6 7 11 12 13 **

system.out.print("Hello Deep

// Java program for implementation of Heap Sort 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); } } // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap 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 < n; ++i) System.out.print(arr[i] + " "); System.out.println(); } // Driver code public static void main(String args[]) { int arr[] = { 12, 11, 13, 5, 6, 7 }; int n = arr.length; HeapSort ob = new HeapSort(); ob.sort(arr); System.out.println("Sorted array is"); printArray(arr); } }