How to implement heap sort in Java
Heap sort utilizes the heap data structure to perform
Algorithm
An array-based representation for the binary heap is space-efficient. Here, if the parent node is at index i, then the left child node is at 2i+1 and the right child is at 2i+2, as shown in the diagram below:
build-max-heap: creates a max heap from an unsorted array.
build-min-heap: creates a min heap from an unsorted array.
This algorithm discusses the sorting of the heap in ascending order; hence, we will build a max heap from the input. The maximum value will reside on the root of the heap.
We will swap the first element, i.e., the largest element with the last element of the heap, and then reduce the size of the heap by 1. Once we have successfully done that, we will call the heapify method for the root of the tree. We will then repeat this step until the size of the heap is greater than 1.
heapify() is similar to build-max-heap/build-min-heap, but comparatively faster due to the assumption made in heapify that some part of the array is already sorted. However, at the very start, we may use the heapify method to build max heap as well. Slight modifications in conditions in the heapify method will enable us to create a min-heap.
Code
class HeapSort{void print(int array[],int size){int index = 0;while(index < size){System.out.print(" " + array[index]);index++;}}void heapify(int arr[], int size, int index){int maximum = index;int leftChild = 2*index + 1;int rightChild = 2*index + 2;int swapper;//now check if right and left child are greater than parent and the right and left child index are not out of bound.if(leftChild < size && arr[leftChild] > arr[maximum]){maximum = leftChild;}if(rightChild < size && arr[rightChild] > arr[maximum]){maximum = rightChild;}//if maximum is not equal to its initial declaration(root) then swap.if(maximum != index){swapper = arr[index];arr[index] = arr[maximum];arr[maximum] = swapper;//we will recursively heapify the affected sub-treeheapify(arr,size,maximum);}}void sort(int array[]){int size = array.length;int swapper;//building max heap using heapifyint index = (size/2) - 1;while(index >=0){heapify(array,size,index);index--;}//We will extract elements from heap one by one and reduce size of the heap (assuming part of array is sorted controlled by index)for(index = size -1; index > 0; index--){//largest resides on root in max-heapswapper = array[0];array[0] = array[index];array[index] = swapper;//call heapify on root of reduced heapheapify(array,index, 0);}}public static void main(String args[]){int array[] = { 3, 1, 4, 9, 8, 6 };int size = array.length;HeapSort object = new HeapSort();object.sort(array);System.out.println("After Heap Sort: ");object.print(array,size);}}
Time complexity
The time complexity of heap sort is , where is the size of the array.
