The content is introduced

Introduction to heap Sort

We have introduced the heap structure, and it is possible to construct a heap structure. If you are not familiar with heap structure, you can take a look at the previous article “Animation heap structure, an easy-to-understand heap structure article”. Just to recap, the heap with the largest root node is called the maximum heap or large root heap, as shown below:

To get the maximum value of the maximum heap is to get the elements at the top of the heap. The heap is a data structure where you swap the top element of the heap with the last element in the heap, the maximum value goes to the last place, and then you exclude the largest element from the heap, and when you swap the last element to the top, it doesn’t satisfy the heap, We need to take the front element and let the heap continue to satisfy the heap’s rules by a release call.

Obtaining a maximum heap can be divided into two steps:

  1. Swap the top maximum and the last element in the heap.
  2. useShiftDownLet the first element sink into place, and still satisfy the heap nature.

    Animation demo effect is as follows:


The idea of heap sort

We know that the value of the top element is the maximum value in the heap, so when we take and remove the maximum value from the heap, the ShiftDown will allow the binary tree to still satisfy the heap’s rules. The second largest value in the heap will reach the top and take the maximum value again. It’s actually the second largest value in all of the data, and so on, and you’ve done heap sorting.

Heap sort animation demonstration

In general, there is no special requirement for sorting algorithms to sort in ascending order, small first, big last. The array consists of {5, 3, 1, 9, 7, 2, 8, 6}.

Heap sorting analysis



As shown in the figure above, when we remove 9 from the top of the heap, the second largest value in the heap, 8, comes to the top of the heap. When we remove 8 again, the maximum number of remaining elements in the heap goes up to the top of the heap.

Delete 8 from heap

Effect of heap delete 7:

Effect of heap 6 deleted:

Effect of heap deletion 5:

Effect of heap delete 4:

Effect of heap delete 3:

Effect of heap deletion 2:

Delete 1 from heap

We can see the steps of the heapsort algorithm:

  1. The unordered binary tree is constructed into a binary heap.
  2. Iterate over the top of the heap, move it to the end of the array, adjust the binary heap, get the maximum value of the new heap and put it on the top of the heap.

Heap sort code

public class HeapSort {

    public static void main(String[] args) {

        int[] arr = {6.3.7.5.8.2.1.4.9};



        heapSort(arr);

        System.out.println("After heap sort:" + Arrays.toString(arr));

    }



    / * *

* heap sort

     * @paramArr The array to sort

* /

    public static void heapSort(int[] arr) {

        heapify(arr);

        System.out.println("Build heap:" + Arrays.toString(arr));



        // Swap the top element with the last element in the heap

        for (int i = arr.length-1; i > 0; i--) {

            swap(arr, i, 0);

            shiftDown(arr, 0, i);

        }

    }



    / * *

* Heapify adjusts the unordered complete binary tree to a binary heap

     * @paramArr The array to be adjusted

* /

    private static void heapify(int[] arr) {

        Shift Down builds each subtree into the maximum heap, starting with non-leaf nodes

        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {

            shiftDown(arr, i, arr.length);

        }

    }



    / * *

* Sink operation, sinks the specified element to the appropriate position in the subtree, so that the tree meets the heap rules.

     * @paramArr The array to be adjusted

     * @paramIndex Indicates the index of the element to sink

     * @paramCount The valid range of the heap

* /

    private static void shiftDown(int[] arr, int index, int count) {

        // Reduce the assignment when sinking, save the sinking element first, then swap it out

        int temp = arr[index];

        // j stands for left child index

        int childIndex = 2*index + 1;

        // loop to find children to switch places. The left child must not cross the line

        while (childIndex < count) {



            // Determine whether there are children and whether the right child is larger than the left child

            if (childIndex+1 < count && arr[childIndex+1] > arr[childIndex]) {

                childIndex++; // If so, switch with the right child

            }



            // If the current node is larger than two children, there is no need to swap

            if (temp > arr[childIndex])

                break;



            // The current node is smaller than the child. Swap the current node with the older child

            // Record the index to be swapped without actually exchanging it

            arr[index] = arr[childIndex];



            // Decide the next level

            index = childIndex;

            childIndex = 2*index + 1;

        }

        arr[index] = temp;

    }



    public static void swap(int[] arr, int start, int end) {

        if (start == end) return;



        int temp = arr[start];

        arr[start] = arr[end];

        arr[end] = temp;

    }

}

Copy the code

The complexity of heap sort

Time complexity of heap sort: The running time of heap sort is mainly consumed by the sink of data when the heap is started and rebuilt after the maximum is taken out. In the process of heap construction, the construction starts from the last non-leaf node of the complete binary tree, and the last non-leaf node is (n-1)/2. It is compared and exchanged with its children. For each non-leaf node, it will be compared at most twice, so the time complexity of heap construction is 0(n). When you sort, the heap top element has to swap places with the last valid element in the heap and sink, and the time is O(logi), and there are n-1 times to get the maximum of the heap top, so the time to get the maximum in sequence is O(nlogn). Build heap and get heap top maximum sort are two operations before and after, so the total heap sort time complexity is O(nlogn).

We can see that heap sort is not sensitive to sorted data, no matter what the data is, the heap sort is the best, the worst, the average time complexity is O(nlogn), there is no room for optimization, so when really sorting, we do not choose heap sort, but choose fast sort with better optimization performance.

Spatial complexity of heapsort: Only one additional variable is required to record the data to be exchanged during heapsort, so the spatial complexity of heapsort is O(1). Heap sort is an unstable sorting algorithm because it causes the elements on the top of the heap to sink to the appropriate position after reaching a maximum value.

conclusion

Heap sort process:

  1. Build a heap of a complete binary tree
  2. Loop to get the maximum value of the top of the heap, place it behind the heap, and rebuild the heap.


———- End ———-


Original articles and animation production is really not easy, your thumbs up is the biggest support!

For more articles, please pay attention to wechat public number: Cousin Animation learning programming