Heap Sort Using Java Collection
Steps:
- Convert the input array into a max heap using the priority queue.
- Remove the top element of the max heap and place it at the end of the array.
- Repeat step 2 for all the remaining elements in a heap.
Java
import java.util.*;public class HeapSortUsingSTL { // Function to perform the heap sort public static void heapSort(int[] arr) { PriorityQueue<Integer> maxHeap = new PriorityQueue<>( Collections.reverseOrder()); for (int i = 0; i < arr.length; i++) { maxHeap.offer(arr[i]); } for (int i = arr.length - 1; i >= 0; i--) { arr[i] = maxHeap.poll(); } } // Driver Code public static void main(String[] args) { int[] arr = { 60, 20, 40, 70, 30, 10 }; System.out.println("Before Sorting: " + Arrays.toString(arr)); heapSort(arr); System.out.println("After Sorting: " + Arrays.toString(arr)); }} |
Output
Before Sorting: [60, 20, 40, 70, 30, 10] After Sorting: [10, 20, 30, 40, 60, 70]
Complexity of the above program:
Time Complexity: O(n log n)
Auxiliary Space: O(n)
Please refer complete article on Heap Sort for more details!
Java Program for Heap Sort
Heap sort is a comparison-based sorting technique based on the Binary Heap data structure. It is similar to the selection sort where first find the maximum element and place it at the end. We repeat the same process for the remaining element.