# Heap sort in Java ### What is heap?

Heap is a special kind of complete binary tree in which the all node has a value greater (or smaller ) than all of its children .

A complete binary tree is a binary tree where all levels are completely filled except the last level which can be complete or incomplete . All nodes should be filled from left to right .

There are two types of heap , [Min heap](https://www.prepbytes.com/blog/heap/min-heappaid/ “Min heap”) and [Max heap](https://www.prepbytes.com/blog/heap/max-heap-in-java/ “Max heap”) . In Max heap all nodes have value greater than the children’s value whereas in Min heap all nodes have value smaller than the children’s value . ### What is heap sort?

Heap sort is a sorting technique in which we use heap operations to sort the given array in ascending or descending order . For sorting in ascending order , we first create the max heap from the given array .
One by one we remove the max number (i.e root of heap ) to the end of the array and adjust other numbers to maintain heap property using heapify() . At the end , we have the array in ascending order .

heapify() : This is the most important operation in the heap sort algorithms . It ensures that heap property is maintained . Following is the process to heapify

1. For heapify(i) , compare value of this node with left node (2 i+1) and right node (2 i+2) .
2. If heap[i] >= max(heap[2 i+1] , heap[2 i+2] ) , then stop the process
3. Else swap( heap[i] , heap[largest] ) , where ‘largest’ is child with larger value among left child and right child
4. Call heapify(largest) .

Time complexity for the heapify method is O(logn).

### Algorithm for heap sort :

1. Create the max heap of given array
2. Swap the root node of heap with the last node
3. Decrease the size of heap and perform heapify
4. Repeat 2-3 until the heap is empty .

Now let’s see the working of heap sort in detail by using an example. ### Implementation of heap sort algorithm in java

```/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

class HeapSort{
private int size;

private void heapify(ArrayList<Integer> arr,int i){
int next=i;
if(2*i+1 < size && arr.get(2*i+1) > arr.get(next))next=2*i+1;
if(2*i+2 < size && arr.get(2*i+2) > arr.get(next))next=2*i+2;

if( next  == i)return;
Collections.swap(arr,i,next);
heapify(arr,next);
}

public void sort(ArrayList<Integer> arr){
size = arr.size();
for(int i= size-1; i>=0;i--){
heapify(arr,i);
}

while(size > 0){
Collections.swap(arr,0,size-1);
size -- ;
heapify(arr, 0);
}
}
}

class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
ArrayList<Integer> arr = new ArrayList<Integer> ();

System.out.println("before sorting :" + arr);
new HeapSort().sort(arr);
System.out.println("after sorting :" + arr);

}
}
```

Time complexity for the above algorithm will be O(nlogn) in all cases . We are also not using any extra space as we are creating the heap using the given array itself , so space complexity will be O(1).

Similarly , we can create a Min heap for sorting the array in descending order . All we need to do is change the heapify method in HeapSort class .

This article tried to discuss Heap sort in Java. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.