## HeapSort ( array Based) implementation in Java

There are two types of heaps. First one is Max heap and second one is Min heap. Heap (Max/Min) is a special type of binary tree.The roots of  the max heap is greater than its child roots. Other heap is Min heap it is also a special type of heap which has minimum root than his child. We can sort the array values using heap sorting algorithm. In this algorithm the heap build is used to rebuild the heap.

In this example we sorting all elements of an array. The complexity of the heap sort is O(n.log(n)) since the method buildheap takes time O(n) and each of the (n-1) calls to maxheap takes time O(lg n).

Pesudo Code :

function heapSort(a, count) is
input:  an unordered array a of length count

(first place a in max-heap order)
heapify(a, count)

end := count-1 //in languages with zero-based arrays the children are 2*i+1 and 2*i+2
while end > 0 do
(swap the root(maximum value) of the heap with the last element of the heap)
swap(a[end], a[0])
(decrease the size of the heap by one so that the previous max value will
stay in its proper placement)
end := end - 1
(put the heap back in max-heap order)
siftDown(a, 0, end)

function heapify(a, count) is
(start is assigned the index in a of the last parent node)
start := count / 2 - 1

while start ≥ 0 do
(sift down the node at index start to the proper place such that all nodes below
the start index are in heap order)
siftDown(a, start, count-1)
start := start - 1
(after sifting down the root all nodes/elements are in heap order)

function siftDown(a, start, end) is
input:  end represents the limit of how far down the heap
to sift.
root := start

while root * 2 + 1 ≤ end do    (While the root has at least one child)
child := root * 2 + 1      (root*2 + 1 points to the left child)
swap := root        (keeps track of child to swap with)
(check if root is smaller than left child)
if a[swap] < a[child]
swap := child
(check if right child exists, and if it's bigger than what we're currently swapping with)
if child+1 ≤ end and a[swap] < a[child+1]
swap := child + 1
(check if we need to swap at all)
if swap != root
swap(a[root], a[swap])
root := swap          (repeat to continue sifting down the child now)
else
return

Code Description :

*maxheap(int[] a, int i) : It helps us to maintain the property of Max-Heap i.e. the root value is always greater than the child value and it takes a time of O(lg n). Therefore, we can say that the running time of maxheap(int [] a, int i) on a tree of height h  is O(h).

*buildheap(int[] a) : We use the maxheap() function in a bottom-up manner to create an array A[1..n], where n=A.length, into a Max-Heap. The function buildheap() goes through the remaining elements i.e. A[(n/2)+1, n] thus it take linear time, produces a max-heap from an unordered input array.

```public class HeapSort
{
private static int[] a;
private static int n;
private static int left;
private static int right;
private static int largest;

public static void buildheap(int []a){
n=a.length-1;
for(int i=n/2;i>=0;i--){
maxheap(a,i);
}
}

public static void maxheap(int[] a, int i){
left=2*i;
right=2*i+1;
if(left <= n && a[left] > a[i]){
largest=left;
}
else{
largest=i;
}

if(right <= n && a[right] > a[largest]){
largest=right;
}
if(largest!=i){
exchange(i,largest);
maxheap(a, largest);
}
}

public static void exchange(int i, int j){
int t=a[i];
a[i]=a[j];
a[j]=t;
}

public static void sort(int []a0){
a=a0;
buildheap(a);

for(int i=n;i>0;i--){
exchange(0, i);
n=n-1;
maxheap(a, 0);
}
}

public static void main(String[] args) {
int []a1={4,1,3,2,16,9,10,14,8,7};
sort(a1);
for(int i=0;i<a1.length;i++){
System.out.print(a1[i] + " ");
}
}
}

OUTPUT :```
```
```
`1 2 3 4 7 8 9 10 14 16 `
```
HeapSort Working :```

```
```
`Other Sorting Algo :`
```
```
`Merge Sort : View `
```
```
`Insertion Sort : View`

1. This is one of the programming questions asked on College semester exams , its also a entry level popular question like Finding length of Singly Linked List using Iteration and Recursion. By the way nice explanation.

2. hey what a nice to explain...
clearly understood the problem !!!

keep up the good work...

3. The program will not give the output specified. It will give
16 14 9 10 8 1 4 2 3 7 as the output.

Please check and let us know.

4. @Anonymous The outpt will be 1 2 3 4 7 8 9 10 14 16

5. Question, while doing maxheap, you check if left<=n, shouldnt you also check if the left child is greater than the right child of the tree? For the swap?

1. If the left child is bigger than the parent , largest=left , then the code compares the right child with largest ,if right is bigger ,largest= right.
it is the same as comparing the left with right to know which is bigger then swap;
reply to if i am wrong

6. here is simple version of heap sort http://goo.gl/K7e6Y1

1. That was like 10x harder to read. Author needs help with clean code.

7. Since you're using a 0-indexed array, should your left and right be 2*i+1 and 2*i+2 respectively?

1. The right code is:
left = 2*i+1 ;
right = 2*i+2;

8. In maxheap method you have written -> left=2*i; right=2*i+1; but logically it is supposed to be left=2*i+1; right=2*i+2;. Isn't it?. Or am i missing anything.

9. Under "maxheap" the line "if(right <= n && a[right] > a[largest])" can end up comparing "a[right]" which is out of bounds of your array.

If your array size is 0-6, you generate right = 2 * i + 1. which is 2 * 3 + 1 = 7, thus a[7] may or may not exist.

10. This does not give a sorted output?!?!?!?

11. hello there thanks for the info, would you mind to tell us how to animate heap sort in java? thanks

12. Code is wrong. It does not sort properly, and there are many mistakes.