Heap Sort
Heap Sort [Hard]
- Write a function that takes in an array of integers and returns a sorted version of that array. Use the Heap Sort algorithm to sort the array.
- If you’re unfamiliar with Heap Sort, we recommend watching the Conceptual Overview section of this question’s video explanation before starting to code.
Sample Input
array=[8,5,2,9,5,6,3]
Sample Output
[2,3,5,5,6,8,9]
Hints
Hint 1
Divide the input array into two subarrays in place. The second subarray should be sorted at all times and should start with a length of 0, while the first subarray should be transformed into a max (or min) heap and should satisfy the heap property at all times.
Hint 2
Note that the largest (or smallest) value of the heap should be at the very beginning of the newly-built heap. Start by swapping this value with the last value in the heap; the largest (or smallest)value in the array should now be in its correct position in the sorted subarray, which should now have a length of 1; the heap should now be one element smaller, with its first element out of place. Apply the "sift down" method of the heap to re-position this out-of-place value.
Hint 3
Repeat the step mentioned in Hint #2 until the heap is left with only one value, at which point the entire array should be sorted.
Method 1
【O(nlog(n))time∣O(1)space】
package Sorting;
import java.util.Arrays;
/**
* @author zhengstars
* @date 2023/04/10
*/
public class HeapSort {
public static int[] heapSort(int[] array) {
// Build the max heap first.
buildMaxHeap(array);
// Traverse the array from the end.
for (int i = array.length - 1; i > 0; i--) {
// Move the largest element to the end of the array.
swap(0, i, array);
// Adjust the heap for the unsorted elements to find the next largest element.
siftDown(0, i - 1, array);
}
return array;
}
public static void buildMaxHeap(int[] array) {
// Calculate the index of the first non-leaf node.
int firstParentIdx = (array.length - 2) / 2;
// Adjust the heap for each non-leaf node from last to first.
for (int currentIdx = firstParentIdx; currentIdx >= 0; currentIdx--) {
// Adjust the heap for the current node.
siftDown(currentIdx, array.length - 1, array);
}
}
public static void siftDown(int currentIdx, int endIdx, int[] heap) {
// Calculate the index of the left child node.
int childOneIdx = currentIdx * 2 + 1;
// When the left child node is within the array range.
while (childOneIdx <= endIdx) {
// Calculate the index of the right child node.
int childTwoIdx = currentIdx * 2 + 2 <= endIdx ? currentIdx * 2 + 2 : -1;
int idxToSwap;
// If the right child node exists and is larger than the left child node.
if (childTwoIdx != -1 && heap[childTwoIdx] > heap[childOneIdx]) {
// Swap the right child node and the current node.
idxToSwap = childTwoIdx;
} else {
// Swap the left child node and the current node.
idxToSwap = childOneIdx;
}
// If the node to swap is larger than the current node.
if (heap[idxToSwap] > heap[currentIdx]) {
// Swap the two nodes and continue adjusting the heap for the new subtree.
swap(currentIdx, idxToSwap, heap);
currentIdx = idxToSwap;
// The exchanged child node may also have its own child node, so we need to continue to adjust the heap
childOneIdx = currentIdx * 2 + 1;
} else {
// If the node to swap is smaller than the current node, no need to swap, return directly.
return;
}
}
}
public static void swap(int i, int j, int[] array) {
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
public static void main(String[] args) {
int[] array = new int[]{8,5,2,9,5,6,3};
System.out.println(Arrays.toString(heapSort(array)));
}
}
Enjoy Reading This Article?
Here are some more articles you might like to read next: