Basic knowledge of

  • Heap sort is an unstable sort with O(N*logN) time complexity and O(1) extra space complexity.

  • The structure of a heap can be divided into large root heap and small root heap, which is a complete binary tree and heap sort is a kind of sorting based on the data structure of the heap. Let’s first look at what are large root heap and small root heap.

Big root heap and small root heap

Property: The value of each node is greater than the value of its left and right child nodes, called the big root heap; The value of each node is less than the value of its left and right children, called the small root heap. The following figure

We labeled each of the numbers in the figure above, and the structure mapped to an array looks like this

One more basic concept: find the parent and the left and right children of a number in an array, such as a number whose index is I, then

  • Parent index :(I *-1)/2

  • Left child index: 2* I +1

  • Right child index: 2* I +2

So the above two arrays can be thought of as heaps because they satisfy the defining properties of a heap:

Arr (I)> ARr (2i+1) && ARr (I)>arr(2i+2)

Small root heap: ARr (I)< ARr (2i+1) &&arr (I)

Basic steps for heap sort

Basic idea:

  • 1. First, organize the numbers to be sorted into a large root heap. In this case, the maximum value of the entire array is the top of the heap structure

  • 2. Swap the number at the top and the number at the end. In this case, the number at the end is the maximum and the number of arrays to be sorted is N-1

  • 3. Construct the remaining n-1 numbers into a large root heap, and then swap the top number with the n-1 position. Repeat the process to obtain an ordered array

Constructing heap

Organize unordered numbers into a large root heap (large root heap for ascending order, small root heap for descending order)

Suppose the following array exists

Main idea: the first guarantee 0-0 position of the large root heap structure (nonsense), the second guarantee 0-1 position of the large root heap structure, the third guarantee 0-2 position of the large root heap structure… Until a large root heap structure is guaranteed at 0-n-1 (each new insert is compared with its parent, swapped with the parent if the number of inserts is larger than the parent, otherwise swapped up until less than or equal to the parent, or reached the top)

When 6 is inserted, if 6 is greater than its parent 3, that is, arr(1)>arr(0), then swap; At this point, positions 0~1 are guaranteed to be large root heap structure, as shown in the following figure:

When 8 is inserted, 8 is greater than its parent 6, that is, arr(2)>arr(0), then swap; At this point, positions 0~2 are guaranteed to be the large root heap structure, as shown in the following figure

When 5 is inserted, 5 is larger than its parent, 3, so it swaps, and after the swap, 5 turns out to be smaller than 8, so it doesn’t swap; At this point, the large root heap structure at positions 0~3 is guaranteed, as shown in the following figure

When I insert 7, 7 is bigger than its parent 5, so I swap, and after I swap, 7 turns out to be smaller than 8, so I don’t swap; The entire array is now a big root heap

Fixed maximum value to rebuild heap

Now that we have a big root heap, let’s swap the top number with the last digit, and then construct the rest into a big root heap

At this point the number 8 has come at the end of it fixed, you just need to perform operations on data on the top of the back, to the handstand number with children around large number, if the number is greater than the children around the larger number at the top of the, then stop, if the number is less than about their children at the top of the large number of exchange, and then continue to compare with the child

In the figure below, among the left and right children of 5, child 7 on the left is 6 older than child 7 on the right. If 5 is found to be less than 7, the child is switched. After switching, 5 is already larger than his left child, indicating that the remaining numbers have formed a large root heap, followed by repeatedly fixing the maximum value, and then building a large root heap

As shown below: The top number 7 is exchanged with the last mantissa number 3, and 7 is fixed.

The remaining numbers start to form a large root heap, then swap the top number with the last mansa, fix the maximum number and then form a large root heap, repeat the above operation, and you end up with an ordered array

conclusion

At this point, you should have your own ideas about heap sorting, so let’s summarize the above process:

1. First, make a large root heap (the newly inserted data is compared with its parent)

2. Fix a maximum value, reconstruct the remaining numbers into a large root heap, and repeat the process

code

There are two main methods in the code:

  • 1. Organize the numbers to be sorted into a large root heap (element ascending)

  • 2. Fix a maximum value and reconstruct the rest into a large root heap (element drop)

/ * * *@Auther: huangshuai
 * @Date: 2021/10/5 21:26
 * @Description: *@Version: * /
public class HeapSort {

    / / heap sort
    public static void heapSort(int[] arr) {
        // Build a big root heap
        heapInsert(arr);
        int size = arr.length;
        while (size > 1) {
            // Set the maximum value
            swap(arr, 0, size - 1);
            size--;
            // Build a big root heap
            heapify(arr, 0, size); }}// Build a big root heap (raised by new inserts)
    public static void heapInsert(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // The index currently inserted
            int currentIndex = i;
            // Parent index
            int fatherIndex = (currentIndex - 1) / 2;
            // If the currently inserted value is greater than that of its parent, the values are swapped and the index points to the parent
            // Then continue to compare with the parent value until it is not greater than the parent value, then exit the loop
            while (arr[currentIndex] > arr[fatherIndex]) {
                // Swap the value of the current node with the parent node
                swap(arr, currentIndex, fatherIndex);
                // Point the current index to the parent index
                currentIndex = fatherIndex;
                Recalculate the parent index of the current index
                fatherIndex = (currentIndex - 1) / 2; }}}// Make the rest of the number into a large root heap (down through the top number)
    public static void heapify(int[] arr, int index, int size) {
        int left = 2 * index + 1;// Left child node
        int right = 2 * index + 2;// Right child node
        while (left < size) {
            int largestIndex;// Store the largest index of the left and right child nodes
            // Determine the index of the larger value in the child (make sure the right child is within the size range)
            if (arr[left] < arr[right] && right < size) {
                largestIndex = right;
            } else {
                largestIndex = left;
            }
            // Compare the parent value with the larger value of the child, and determine the index of the maximum value
            if (arr[index] > arr[largestIndex]) {
                largestIndex = index;
            }
            // If the parent index is the maximum index, it is already a large root heap, then exit the loop
            if (index == largestIndex) {
                break;
            }
            // The parent is not the maximum and is swapped with the larger value in the child
            swap(arr, largestIndex, index);
            // Redirect the index to the index of the larger value in the child, i.e. adjust the heap from top to bottom
            index = largestIndex;
            // Recalculate the index of the swapped child
            left = 2 * index + 1;
            right = 2 * index + 2; }}// Swap the values of two elements in an array
    public static void swap(int[] arr, int i, int j) {
        inttemp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}Copy the code