Heap sort in Java uses the data structure binary heap, min-heap, or max heap to do the sorting of elements. 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.
// 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
The following Java program implements the heap sort using the pseudo-code explained above.
// Java program that uses max heap to do the sorting
// rearranging array elements so that it
// resembles max heap
// One by one extract the top element, which is
// also the maximum element from the heap
// Moving the maximum element of the current heap to the end
// invoking method heapify on the reduced heap
// The heapfiy() method does the rearrangement of elements of
// the given input array to resemble it like a max heap
// Element present at the index j resembles the root of the max heap
// length gives the size of the max heap
inthighest=j;// assign highest as root
intleft=2*j+1;// leftChild = 2 * j + 1
intright=2*j+2;// rightChild = 2 * j + 2
// If the root element is smaller the left child
// If the root element so fat is smaller the right child
// If root is not the highest
// Heapifying the affected sub-tree recursively
// main method
// given input array
// calculating size of the array
System.out.println("The array before sorting is: ");
// invoking method maxHeapSort()
System.out.println("The array after sorting is: ");
// displaying the sorted array
The arraybefore sorting is:
The arrayafter sorting is:
Explanation: The above program is imitating bubble sort. The heapify() method ensures that the maximum value element sits at the index 0. Then in one swap, the maximum element is put at the end of the array. When the heapify() method is called the second time, it puts the second maximum element at index 0.
The swapping process puts the second maximum element at the second last index of the array, and the process of invoking the heapify() method and swapping of elements continues till the whole array is sorted. The following diagram demonstrates the same.
Note that instead of using the max-heap, min-heap can also be used to sort. Using the min-heap, the heap sort resembles the selection sort as the root of the min-heap always gives the element of least value.
Analysis of the Heap Sort
Even though heap sort resembles the selection or bubble sort, the heap sort is much faster than the selection or bubble sort. However, similar to the selection or bubble sort, heap sort also divides the input array virtually into two halves; one is sorted, and another is unsorted.
The heapify() method does the heapification process in O(log(n)) times, where n is the size of the input array. Also, the for-loop is iterating over each element of the array from right to left (see code). In each iteration, the heapify() method is invoked. Thus, for the for-loop time complexity is O(n) and O(log(n)) for the heapify() method. Hence, the total time complexity turns out to be O(n * log(n)) = O(nlog(n)). As O(nlog(n) is always less than O(n^2); therefore, heap sort is better than selection or bubble sort. One can think of the heap sorting algorithm as an improved version of selection sort or bubble sort.
Similar to selection or bubble sort, heap sort algorithm also does the in-place sorting. The heap sort tries to visualize the input array as either min heap or max heap. Therefore, the space complexity for the heap sort turns out to be O(1), i.e., constant space for sorting the input array or list.
Heap sort works faster than bubble or selection sort. However, for larger data sets, it is found that merge sort is a better choice than heap sort, even though merge as well heap sort gives the time complexity of O(nlog(n)). Also, unlike merge sort, heap sort is not a stable sorting algorithm. However, by some modification, one can make merge sort stable. However, making heap sort stable increases the complexity of the algorithm.