Heap Sort in Java
Heap sort in Java uses the data structure binary heap, min-heap, or max heap to do the sorting of element. Since min-heap always gives the minimum element first, heap sort becomes similar to the selection sort where min-heap is used to sort the array. When max heap is used for sorting purposes, the heap sort resembles bubble sort, as max heap gives the maximum element first.
In this section, we have discussed the max-heap for sorting the elements.
Max Heap Algorithm
Step 1: Build max heap for the given input array using the method heapify().
Step 2: swap the root with the last element of the array. Reduce the size of the heap by 1.
Step 3: Call the heapify() method again to maintain the property of max heap on remaining elements.
Step 4: Repeat steps 3 & 4 till the whole array gets sorted.
Pseudo Code
// Perform the operation heapify-down or down-heap for getting a max-heap
// arr: an array representing the heap, indexing starting from 0
// j: represents the index from where heapifying down begins
Heapify(arr, j):
leftChild ? 2 * j
rightChild ? 2 * j + 1
highest ? j
if leftChild < size(arr) and arr[leftChild] > A[highest] then:
highest ? leftChild
if rightChild < size(arr) and A[rightChild] > A[highest] then:
highest ? rightChild
if highest ? j then:
swap arr[j] and arr[highest]
Heapify(arr, highest)
Java Program
The following Java program implements the heap sort using the pseudo-code explained above.
FileName: HeapSortExample.java
