Heap sort

It is divided into large root heap and small root heap, in which ascending order uses the large root heap, descending order uses the small root heap.

Data structure used: complete binary tree

Note: A complete binary tree is a binary tree in which nodes are sequentially arranged.

Perfect binary tree: a complete binary tree whose leaves are all in the same layer;

Heap sort: The core problem is the process of initializing the large root heap and swapping and adjusting the large root heap.

Time complexity: O(nlogn)

Algorithm flow:

  1. Adjust the large root heap
  2. Replace the root: replace the root element with the last element to determine the maximum position
  3. Adjust new root position: Adjust the newly replaced root to the appropriate position, keeping the large root heap property
  4. Repeat steps 2,3 until the entire binary tree has been traversed

The schematic diagram of the big root heap construction algorithm is as follows:

The implementation code is as follows:

/*** * heap sort * use binary tree mode * Heap is a complete binary tree, large root heap, is after each iteration, the root node is the largest number, and the last leaf node is replaced. * The average time complexity of heap sort is two o (nlogn). * /
public class HeapSort {
    public static void main(String[] args) {
        // Initializes a random number group
        int[] data = new int[8];
        for (int i = 0; i < 8; i++){
            data[i] = new Random().nextInt(20) + 1;
        }
        // Heap sort (order)
        HeapSort.heapSord(data);
    }

    // Heap sort main process
    public static int[] heapSord(int[] data){
        // The queue length of the heap attribute needs to be maintained
        int len = data.length - 1;

        /** * step 1: Build a large root heap * start from the last non-leaf node, adjust to match the large root heap attributes (leaves do not need to be compared) ** /
        int end = len / 2 - 1;   // The last non-leaf node
        for (int i = end ; i >= 0 ; i--){
            heapAdjust(data,len,i);
        }

        /** * step 2: replace the maximum value, adjust the large root heap ** /
        for(int i = data.length - 1; i > 0 ; i --){
            // Replace the first element (the maximum value) with the last value
            int tmp_value = data[0];
            data[0] = data[i];
            data[i] = tmp_value;
            // The array length is reduced by 1(the last element is already determined)
            len --;
            heapAdjust(data,len,0);

        }
        return data;
    }

    Int [] data: raw data * int len: total length of the array to be adjusted * int index: subscript of the element to be adjusted ** /
    private static void heapAdjust(int[] data,int len,int index){
        // Determine the subscript of the largest element in the current node and the left and right child nodes
        int tmp_index = max(data,len,index);
         /** * recursive function end condition: the current node is the largest, do not need to adjust ** /
        if (tmp_index == index){
            return;
        }

        // Swap the maximum value
        int tmp_value = data[index];
        data[index] = data[tmp_index];
        data[tmp_index] = tmp_value;
        // Recursively adjust to the final result
        heapAdjust(data,len,tmp_index);
    }
    // Get the index of the current element and the index of the left and right element
    private static int max(int[] data,int len,int index){
        int max = index;
        // index the left node
        int left = index * 2 + 1;
        // subscript the right node
        int right = index * 2 + 2;
        // Ensure that the left and right child nodes exist
        if (left < len && data[left] > data[max]){
            max = left;
        }

        if (right < len && data[right] > data[max]){
            max = right;
        }
        returnmax; }}Copy the code