1. Basic introduction to heap sort

  1. Heap sort is a kind of sorting algorithm designed by using heap data structure. Heap sort is a kind of selection sort, whose worst, best and average time complexity are O(nlogn), and it is also unstable sort.
  2. A heap is a complete binary tree with the property that the value of each node is greater than or equal to the value of its left and right children, called the big top heap. Note: there is no requirement for the relationship between the value of the left child and the value of the right child.
  3. The value of each node is less than or equal to the value of its left and right children, called the small top heap.
  4. Example of big top heap:

The nodes in the heap are numbered by layer and mapped to an array like this:Copy the code

Large top heap features: ARr [I] >= ARr [2* I +1] && arr[I] >= ARr [2* I +2] // What node does I correspond to? I is numbered from 0Copy the code
  1. Small top heap example:

Small top heap: arr[I] <= arr[2* I +1] && arr[I] <= arr[2* I +2] // number of nodes corresponding to I, I is numbered from 0

  1. In general, large top heap is used for ascending and small top heap is used for descending

2. The basic idea of heap sort

  1. The sequence to be sorted forms a big top heap, and the maximum value of the entire sequence is the root node of the top of the heap
  2. Swap it with the trailing element, where the trailing element is the maximum
  3. The remaining n-1 elements are then reconstructed into a heap, resulting in the subsmallest values of n elements, which is repeated to produce an ordered sequence

You can see that as you build the big top heap, the number of elements gets smaller and smaller, and you end up with an ordered sequence.

3. Heap sorting diagram

Example: Use heap sort to sort the array {4, 6, 8, 5, 9} in ascending order

Step 1: Construct the initial heap. Construct the given unordered sequence into a large top heap

  1. Construct the array as a big top heap like this:

  1. Start from the bottom non-leaf node (arr. Length /2-1 = 5/2-1 = 1, that is, the node of value 6) and adjust from left to right, bottom to top

Among the children of non-leaf node 1, the value of node 4 is larger and larger than that of non-leaf node 1, so the value of non-leaf node 1 is swapped with that of node 4.

  1. Find the parent of node 1, 0(i.e., the non-leaf node in the upper layer), and swap the values of both nodes since the value of node 1 is larger than that of node 0.

  1. The above exchange leads to the disordered structure of the child root [4, 5, 6]. Further adjustment, 6 is the largest in [4, 5, 6]. Swap 4 and 6, that is, swap the value of node 1 and node 4.

At this point, an unordered sequence is constructed into a large top heap.

Step 2: Swap the top element with the last element, which is the largest, and remove the last element from the heap. We then continue to adjust the heap and swap the top element with the bottom element to get the second largest element. And so on and so forth.

  1. Swap the value of 0 at the top of the heap with the value of 4 at the end

  1. Resize the heap to a large top heap

  1. The value of 0 at the top of the heap is then swapped with the value of 3 at the end

  1. Continue to adjust to the big top heap, swap the top and end of the heap, and so on until you get an ordered sequence

4. Summarize the basic idea of heap sorting

  1. The unordered sequence is constructed into a heap, which can be selected as a big top heap or a small top heap as required
  2. Swap the top element with the end element so that the largest element “sinks” to the end of the array
  3. Restructure the heap, continuing to swap the top elements for the bottom elements, and repeat steps 1 and 2 until the sequence is in order

5. Code implementation

package com.atguigu.Tree;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class HeapSort {

    public static void main(String[] args) {
        // Sort the array in ascending order
        //int arr[] = {4, 6, 8, 5, 9};

        // Create an array of 80,000 random numbers
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 8000000);
        }

        System.out.println("Pre-sort");
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(date1);
        System.out.println("Time before heap sort is:" + date1Str);

        heapSort(arr);

        Date date2 = new Date();
        String date2Str = simpleDateFormat.format(date2);
        System.out.println("The sorted time is:" + date2Str);

        System.out.println(Arrays.toString(arr));
    }

    // Write a heap sort method
    public static void heapSort(int arr[]) {
        int temp = 0;
        System.out.println("Heap sort!!");

        //// step by step
        //adjustHeap(arr, 1, arr.length);
        // system.out. println(" first: "+ array.toString (arr)); //4, 9, 8, 5, 6
        //
        //adjustHeap(arr, 0, arr.length);
        // system.out.println (" array.toString (arr)); //9, 6, 8, 5, 4

        // Final code
        //1. Build the unordered sequence into a heap, and select a large or small top heap according to ascending or descending requirements
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        //2. Swap the top element with the end element, and "sink" the largest element to the end of the array
        //3. Rearrange the structure so that it meets the heap definition, and then continue swapping the top element with the current end element, repeating the adjustment + swap until the whole sequence is in order
        for (int j = arr.length - 1; j > 0; j--) {
            / / exchange
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }

        Println (" Array: "+ Arrays. ToString (arr)); //System.out.println(" Array:" + Arrays.
    }

    // Adjust an array (binary tree) to a large top heap

    Int arr[] = {4, 6, 8, 5, 9}; int arr[] = {4, 6, 8, 9}; => I =1 => adjustHeap => get: {4, 9, 8, 5, 6} * If you call adjustHeap again with I =0 => get {9, 6, 8, 5, 4} * *@paramArr adjusts the array *@paramI The index of the non-leaf node in the array *@paramHow many elements does length adjust? Length is decreasing */
    public static void adjustHeap(int arr[], int i, int length) {

        int temp = arr[i];// First fetch the value of the current element, save in a temporary variable
        // Start adjusting
        / / description:
        //1, k is the left child of I
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;//k points to the right child
            }
            if (arr[k] > temp) {// If the child is larger than the parent
                arr[i] = arr[k];// Assign the larger value to the current node
                i = k;// I points to k and continues the loop comparison
            } else {
                break; }}// When the for loop ends, the tree with parent I is at the top (local)
        arr[i] = temp;// Put the temp value in the adjusted position}}Copy the code
Output: the time before the heap sort is: The time after sorting is: 2019-07-31 13:31:04Copy the code

Heap sorting is very fast.