HEAP SORT

Heaps:
A heap is a specific tree based data structure in which all the nodes of tree are in a specific order. Let’s say if X is a parent node of Y, then the value of X follows some specific order with respect to value of Y and the same order will be followed across the tree.

There can be two types of heap:

Max Heap: In this type of heap, the value of parent node will always be greater than or equal to the value of child node across the tree and the node with highest value will be the root node of the tree.

Min Heap: In this type of heap, the value of parent node will always be less than or equal to the value of child node across the tree and the node with lowest value will be the root node of tree.

1) Heap Sort:

We can use heaps in sorting the elements in a specific order in efficient time.
Let’s say we want to sort elements of array Arr in ascending order. We can use max heap to perform this operation.

Processing:
1) Initially we will build a max heap of elements in Arr.

2) Now the root element that is Arr[ 1 ] contains maximum element of Arr. After that, we will exchange this element with the last element of Arr and will again build a max heap excluding the last element which is already in its correct position and will decrease the length of heap by one.

3) We will repeat the step 2, until we get all the elements in their correct position.

4) We will get a sorted array.
Example on Max Heap

Processing:
Step 1: 8 is swapped with 5.
Step 2: 8 is disconnected from heap as 8 is in correct position now and.
Step 3: Max-heap is created and 7 is swapped with 3.
Step 4: 7 is disconnected from heap.
Step 5: Max heap is created and 5 is swapped with 1.
Step 6: 5 is disconnected from heap.
Step 7: Max heap is created and 4 is swapped with 3.
Step 8: 4 is disconnected from heap.
Step 9: Max heap is created and 3 is swapped with 1.
Step 10: 3 is disconnected.

After building max-heap, the elements in the array Arr will be:

// Java program for implementation of Heap Sort
class rkheapsort
{
// Driver program
public static void main(String args[])
{
int arr[] = {2, 8, 6, 1, 4, 3};
int n = arr.length;

rkheapsort  hs = new rkheapsort();
hs.sort(arr);

System.out.printf("\n Sorted array : ");
hs.printArray(arr);
}
public void sort(int arr[])
{
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
{
System.out.printf("\n Maxheap : ");
    heapify(arr, n, i);
printArray(arr);
}
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
System.out.printf("\n Placing Maxheap value in its position :");
heapify(arr, i, 0);
printArray(arr);
}
}


// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int left = 2*i+ 1; // left = 2*i + 1
int right = 2*i + 2; // right = 2*i + 2

// If left child is larger than root
if (left < n && arr[left] > arr[largest])
largest = left;

// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest])
largest = right;

// If largest is not root
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;

// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}

/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
}
}