Breaking
Priority Queue

# Heap sort

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

Write a program to implement the heapsort

## Source Code

```package com.dsacode.DataStructre.priorityqueue;

public class HeapSortImpl {

private int heapsize;

public HeapSortImpl() {
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[] array = new int[20];
array[1] = 45;
array[2] = 45;
array[3] = 9;
array[4] = 89;
array[5] = 34;

System.out.print("Before Sorting: ");
for (int i = 1; i <= 5; i++)
System.out.print(array[i] + " ");

System.out.println();
HeapSortImpl obj = new HeapSortImpl();
obj.heapsort(array, 5);

System.out.print("After Sorting: ");
for (int i = 1; i <= 5; i++)
System.out.print(array[i] + " ");

}

}```

## Output

```Before Sorting: 45 45 9 89 34
After Sorting: 9 34 45 45 89```