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:

  • 3223. Minimum Length of String After Operations
  • 1208. Get Equal Substrings Within Budget
  • 2730. Find the Longest Semi-Repetitive Substring
  • 1493. Longest Subarray of 1's After Deleting One Element
  • 2275. Largest Combination With Bitwise AND Greater Than Zero