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

Java Program

The following Java program implements the heap sort using the pseudo-code explained above.

FileName: HeapSortExample.java

Output:

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.

Heap Sort in Java

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.

Time Complexity

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.

Space Complexity

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.

Conclusion

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.

Pin It on Pinterest

Share This