## Introduction to Heap Sort In Java

Heapsort in Java is a comparison based sorting technique, where data structure Binary Heap is used. This sorting is almost the same as that of selection sort where largest element will be selected and places in the end and the process will be repeated for all the elements. In order to understand Heap Sort, let us see what Binary Heap Sort in Java.

- Tree-based Data Structure.
- Complete Binary Tree.
- It can have up to two children.
- Value in the root node can be greater(Max Heap) or Smaller (Min Heap)

### How does Heap Sort work in Java?

Before moving to the algorithm, let us see what is Heapify.

#### Heapify

After a heap is created with the input data, heap property may not be satisfied. In order to achieve it, a function called heapify will be used to adjust the nodes of the heap. If we want to create max heap, the current element will be compared with its children and if the value of children is greater than the current element, swapping will be done with the largest element in a left or right child. Similarly, if min-heap needs to be created, swapping will be done with the smallest element in the left or right child. For Example, The following is our input array,

We can consider this as a tree instead of an Array. The first element will be root, second will be the left child of root, the third element will be the right child of root and so on.

In order to transform heap into a tree, traverse the tree in a bottom-up direction. Since the leaf nodes do not have children, let us look into the next level. i.e is 5 and 7.

We can begin at 5 as it is on the left. Here, 5 has two children: 9 and 4, where 9 is greater than the parent node 5. To make parents larger, we will swap 5 and 9. After swapping, the tree will be as shown below.

4.8 (7,468 ratings)

View Course

Let us move to the next element 7 where 8 and 2 are the children. Similar to the elements 9 and 4, 7 and 8 will be swapped as in the below tree.

Finally, 3 has two children-9 and 8 where 9 is greater among the children and root. So, swapping of 3 and 9 will be done to make the root greater. Repeat the process until a valid heap is formed as shown below.

### Algorithm for Heap Sort in Ascending Order

- Create a Max Heap with the input data
- Replace the last element with the largest element in the heap
- Heapify the Tree
- Repeat the process until the array is sorted

### Algorithm for Heap Sort in Descending Order

- Create a Min Heap with the input data
- Replace the last element with the smallest element in the heap
- Heapify the Tree
- Repeat the process until the array is sorted

Now, let us try to sort the above-obtained Heap in the ascending order using the given algorithm. First, remove the largest element. i.e root and replace it with the last element.

Now, heapify the tree formed and insert the removed element in the last of the array as shown below

Again, remove the root element, replace it with the last element and Heapify it.

Insert the removed element to the vacant position. Now you can see that the end of the array is being sorted.

Now, Remove element 7 and replace it with 2.

Heapify the tree, as shown below.

Repeat the process until the array is sorted. Removing element 5.

Heapifying the tree.

Removing element 4.

Heapfying again.** **

At last, a sorted array like this will be formed.

### Examples

Now, let us see the source code of Heap Sort in Java

`//Java program to sort the elements using Heap sort`

import java.util.Arrays;

public class HeapSort {

public void sort(int array[]) {

int size = array.length; //Assigning the length of array in a variable

// Create heap

for (int i = size / 2 - 1; i >= 0; i--)

heapify(array, size, i);

//Find the maximum element and replace it with the last element in the array

for (int i=size-1; i>=0; i--) {

int x = array[0];//largest element(It is available in the root)

array[0] = array[i];

array[i] = x;

// Recursively call __heapify__ until a heap is formed

heapify(array, i, 0);

}

}

// __Heapify__ function

void heapify(int array[], int SizeofHeap, int i) {

int largestelement = i; // Set largest element as root

int leftChild = 2*i + 1; // index of left child = 2*i + 1

int rightChild = 2*i + 2; //index of right child = 2*i + 2

// left child is greater than root

if (leftChild < SizeofHeap && array[leftChild ] > array[largestelement])

largestelement = leftChild ;

//right child is greater than largest

if (rightChild < SizeofHeap && array[rightChild ] > array[largestelement])

largestelement = rightChild ;

// If __largestelement__ is not root

if (largestelement != i) {

int temp = array[i];

array[i] = array[largestelement];

array[largestelement] = temp;

// Recursive call to heapify the sub-tree

heapify(array, SizeofHeap, largestelement);

}

}

public static void main(String args[]) {

int array[] = {3,5,7,9,4,8,2};

System.*out*.println("Input array is: " + Arrays.*toString*(array));

HeapSort obj = new HeapSort();

obj.sort(array);

System.*out*.println("Sorted array is : " + Arrays.*toString*(array));

}

}

**Output**

### Conclusion

Heap Sort is a sorting technique that depends on the Binary Heap Data structure. It is almost similar to selection sort and does not use separate arrays for sorting and heap.

### Recommended Articles

This has been a guide to Heap Sort in Java. Here we discuss the working, Sorting Algorithm with Ascending and Descending Order and examples with sample code. You can also go through our other suggested articles to learn more –