1. Introduction to heap sorting
 Heap sorting is a sort algorithm designed with heap as the data structure. Heap sorting is an optional sort with the worst, best, and average time complexity of O(nlogn), which is also an unstable sort.
Large Top heap and Small Top heap
 A heap is a complete binary tree with the following properties: Each node has a value greater than or equal to the value of its left and right child nodes, called a heap with a large top;
 Each node has a value that is less than or equal to the value of its left and right child nodes, known as the smalltop heap. As follows:
Nodes in a heap are numbered layer by layer, mapping this logical structure to an array
Top heap: arr[i] >= arr[2i+1] & & arr[i] >= arr[2i+2]
Small Top Heap: arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
2. Execution of heap sorting
1. Create a heap and construct a large top heap for a given disordered sequence (generally large top heap for ascending and small top heap for descending).
 At this point, we start with the last nonleaf node (the leaf node naturally does not need to be adjusted, the first nonleaf node arr.length/21=5/21=1, that is, the following six nodes), from right to left, and from bottom to top.
 A second nonleaf node 4 was found because 9 elements in [4,9,8] were the largest, 4, and 9 exchanged.
At this time, the exchange caused the subroot [4,5,6] to be structurally chaotic and continued to adjust, with 6 being the largest among [4,5,6], and 4 and 6 being exchanged.
2. Adjust the heap to exchange the top and end elements of the heap so that the end elements are the largest. Then continue adjusting the heap and swap the top and end elements to get the second largest element. Exchange, rebuild, exchange so repeatedly.

a. Exchange elements 9 at the top and 4 at the end of the heap

b. Readjust the structure to continue meeting the heap definition

c. The top element 8 is then exchanged with the end element 5 to get the second largest element 8.

The subsequent process continues to adjust, swap, and repeat so that the entire sequence is ordered
Summarize the basic ideas for heap sorting:

Build a heap of unnecessary sequences and select large or small top heaps according to ascending and descending requirements.

Swap the top and end elements of the heap and "sink" the largest element to the end of the array;

Readjust the structure so that it satisfies the heap definition, then continue swapping heap top elements with current end elements, repeating the adjustment+swap steps until the entire sequence is ordered.
3. Java code implementation
package com.xizi.sort; //Heap Sorting Demo public class HeapSort { public static void main(String[] args) { // int[] arr = {5, 1, 7, 3, 1, 6, 9, 4}; int[] arr = {16, 7, 3, 20, 17, 8}; System.out.println("Before Sorting: "); for (int i : arr) { System.out.print(i + " "); } heapSort(arr); System.out.println(); System.out.println("After sorting: "); for (int i : arr) { System.out.print(i + " "); } } /** * Create a heap, * @param arr Columns to Sort */ private static void heapSort(int[] arr) { //Create Heap // (arr.length  1) / 2 First nonleaf node for (int i = (arr.length  1) / 2; i >= 0; i) { //From the first nonleaf node from bottom to top, from right to left adjustHeap(arr, i, arr.length); } //Adjust Heap Structure + Swap Heap Top and End Elements for (int i = arr.length  1; i > 0; i) { //Swap heap top elements with end elements int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; //Readjust heap adjustHeap(arr, 0, i); } } /** * Adjust heap * @param arr Columns to Sort * @param parent Parent Node * @param length Index of endofcolumn elements to be sorted */ private static void adjustHeap(int[] arr, int parent, int length) { //Use temp as parent node int temp = arr[parent]; //left child int lChild = 2 * parent + 1; while (lChild < length) { //Right Child int rChild = lChild + 1; // If there is a right child node and the value of the right child node is greater than the left child node, then the right child node is selected if (rChild < length && arr[lChild] < arr[rChild]) { lChild++; } // If the value of the parent node is greater than the value of the child node, it ends directly if (temp >= arr[lChild]) { break; } // Assign the value of a child node to a parent node arr[parent] = arr[lChild]; //Select the left child node of the child node and continue filtering down parent = lChild; lChild = 2 * lChild + 1; } //Assign parent node to child node arr[parent] = temp; } }