Breaking
Sorting

# Heap sort

Heap sort is a comparison-based sorting algorithm and divides the input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region.

Heap sort is not stable sorting. A heap sort is especially efficient for data that is already stored in a binary tree. Heap sort does not take any extra space.

Write a program to implement heap sort.

## source Code

```package com.dsacode.Algorithm.sorting;

public class HeapSort {
private int heapsize;
public HeapSort(){
heapsize =0;
}

int left(int i){
return (2*i);
}

int right(int i){
return (2*i+1);
}

int parent(int i){
return (i/2);
}

void MaxHeapify(int A[], int i){

int largest,temp,l,r;

l=left(i);
r=right(i);

if( A[l] > A[i] && l <= heapsize)
largest=l;
else
largest=i;

if( A[r] > A[largest] && r <= heapsize)
largest=r;

if(largest!=i){
temp=A[i];
A[i]=A[largest];
A[largest]=temp;
MaxHeapify(A,largest);
}
}

void buildmaxheap(int A[], int n){
heapsize=n;
for(int i=n/2; i>=1;i--)
MaxHeapify(A,i);
}

void heapsort(int A[], int n){
int temp;
buildmaxheap(A,n);
for(int i=n;i>=2;i--){
temp=A[i];
A[i]=A[1];
A[1]=temp;

heapsize--;
MaxHeapify(A,1);
}
}

public static void main(String[] args) {

int []arr=new int[20];
arr[1]=12;
arr[2]=34;
arr[3]=56;
arr[4]=23;
arr[5]=45;
arr[6]=78;
arr[7]=99;

System.out.print("Unsorted array before sorting : [" );
for(int i=1; i <= 7; i++){
if(i==7)
System.out.print(arr[i] +"]");
else
System.out.print(arr[i] +",");
}
System.out.println();

HeapSort obj = new HeapSort();
obj.heapsort(arr,7);

System.out.print("Sorted array After Heap sorting :[");
for(int i = 1; i <= 7; i++){
if(i == 7)
System.out.print(arr[i] +"]");
else
System.out.print(arr[i] +",");
}
}
}
```

## Output

```Unsorted array before sorting: [12, 34, 56, 23, 45, 78, 99]
Sorted array After Heap sorting: [12, 23, 34, 45, 56, 78, 99]```