Overview
Heap sorting is a tree selection sorting, which is an effective improvement on direct selection sorting.
The heap is defined as follows: a sequence of n elements (k1,k2,...,kn), if and only if satisfied:
It is called a pile at that time. As can be seen from the definition of the heap, the top element of the heap (i.e. the first element) must be the smallest item (small top heap) or the largest item (large top heap).
If a heap is stored in a one-dimensional array, the heap corresponds to a completely binary tree, and the values of all non-leaf nodes (nodes with children) are not greater than (or not less than) their children's values, and the values of the root node (top element of the heap) are the smallest (or largest).
(a) Large top heap sequence: (96, 83, 27, 38, 11, 09)
(b) Small top heap sequence: (12, 36, 24, 85, 47, 30, 53, 91)
Initially, the sequence of n numbers to be sorted is regarded as a binary tree stored sequentially (one-dimensional array storage binary tree), adjust their storage order to make it a heap, output the top element of the heap to obtain the smallest (or largest) element of the n elements. Then readjust the remaining n-1 elements to become heap, output the top element of the heap, and obtain the element that is the second small (or the second large) among the n elements. And so on until you finally get an ordered sequence with n nodes. Call this process heap sort.
Steps & Examples
There are two problems to solve in implementing heap sorting:
(1) How to build n numbers to be sorted into piles;
(2) After outputting the top element of the heap, how to adjust the remaining n-1 elements to make it a new heap.
Build heap method (small top heap):
The process of building a heap for the initial sequence is a process of repeated screening.
A complete binary tree of n nodes, then the last node is the subtree of n/2th node.
Filter starts with the subtree with the n/2th node as the root (n/2 is the last node with the subtree), so that the subtree becomes a heap.
Then, filter the subtrees with each node as root in sequence forward to make it a heap until the root node.
As shown in the figure, the disordered sequence of the initial process of building a heap: (49, 38, 65, 97, 76, 13, 27, 49)
(a) Unordered sequence, initial binary tree, 97 (8/2=4 node) is the parent node of the last node (49).
(b) 97>=49, replace the position, and then filter the previous node 65 of n/2.
(c) 13<=27 and 65>=13, replace the positions of 65 and 13, and then replace 38 (both greater than it, no operation is required), filter 49.
(d) 13<=38 and 49>=13, replace the positions of 49 and 13, 49>=27, replace the positions of 49 and 27.
(e) Finally get a heap, 13 is the minimum number we get.
Methods to adjust the heap (small top heap):
A heap of m elements is provided. After outputting the top elements of the heap, m-1 elements are left. The bottom element of the heap is fed to the top of the heap, and the heap is destroyed, because the root node does not meet the properties of the heap.
Exchange the root node with smaller elements in the left and right subtrees.
If exchanged with the left subtree: if the left subtree heap is corrupted, repeat method (2).
If exchanged with the right subtree, repeat method (2) if the right subtree heap is destroyed.
Continue to perform the above exchange operation on subtrees that do not meet the heap properties until the leaf nodes and the heap is built.
To adjust the heap, you only need to consider the corrupted nodes, and other nodes do not need to be adjusted.
Code Implementation (Java)
Run the code and compare the comments with the above example steps for comparison.
package com.coder4j.main;public class HeapSort { /** * Adjust to a small top heap (the result is from large to small after sorting) * * @param array is the heap array to be adjusted* @param s is the position of the array element to be adjusted* @param length is the length of the array * */ public static void heapAdjustS(int[] array, int s, int length) { int tmp = array[s]; int child = 2 * s + 1;// The position of the left child node System.out.println("The node to be adjusted is: array[" + s + "] = " + tmp); while (child < length) { // child + 1 is the right child currently adjusting the node // If there is a right child and is smaller than the left child, use the right child to compare with the node, otherwise use the left child if (child + 1 < length && array[child] > array[child + 1]) { child++; } System.out.println("Will be with the child array[" + child + "] = " + array[child] + " Compare"); // If the smaller child is smaller than this node if (array[s] > array[child]) { System.out.println("Child is smaller than it, swap position"); array[s] = array[child];// Move the smaller child upwards and replace the current node to be adjusted s = child;// Move the adjusted node to the original position of the younger child array[child] = tmp; child = 2 * s + 1;// Continue to judge whether the node to be adjusted needs to continue to be adjusted if (child >= length) { System.out.println("There are no children, the adjustment is over"); } else { System.out.println("Continue to compare with the new child"); } // continue; } else { System.out.println("The children are older than them, the adjustment is over"); break;// The current node to be adjusted is smaller than its left and right children, and it does not need to be adjusted, exit directly} } } /** * Adjust to a large top heap (the result is from small to large after sorting) * * @param array is the heap array to be adjusted* @param s is the position of the array element to be adjusted* @param length is the length of the array * */ public static void heapAdjustB(int[] array, int s, int length) { int tmp = array[s]; int child = 2 * s + 1;// The position of the left child node System.out.println("The node to be adjusted is: array[" + s + "] = " + tmp); while (child < length) { // child + 1 is the right child currently adjusting the node // If there is a right child and it is larger than the left child, use the right child to compare with the node, otherwise use the left child if (child + 1 < length && array[child] < array[child + 1]) { child++; } System.out.println("Will be with the child array[" + child + "] = " + array[child] + " Compare"); // If the older child is larger than this node if (array[s] < array[child]) { System.out.println("child is larger than it, swap position"); array[s] = array[child];// Move the older child upwards and replace the current node to be adjusted s = child;// Move the adjusted node to the original position of the older child array[child] = tmp; child = 2 * s + 1;// Continue to judge whether the node to be adjusted needs to be adjusted if (child >= length) { System.out.println("There are no children, the adjustment is over"); } else { System.out.println("Continue to compare with the new child"); } // continue; } else { System.out.println("The children are smaller than them, the adjustment is over"); break;// The current node to be adjusted is larger than its left and right children, and exit directly without adjustment} } } /** * Heap sorting algorithm * * @param array * @param inverse true In reverse order, false in positive order*/ public static void heapSort(int[] array, boolean inverse) { // Initial heap// The position of the last node with a child i = (length - 1) / 2, so as to adjust each node upward to conform to the heap System.out.println("Initial heap start"); for (int i = (array.length - 1) / 2; i >= 0; i--) { if (inverse) { heapAdjustS(array, i, array.length); } else { heapAdjustB(array, i, array.length); } } System.out.println("Initial heap end"); for (int i = array.length - 1; i > 0; i--) { // Swap the heap top element H[0] and the last element in the heap int tmp = array[i]; array[i] = array[0]; array[0] = tmp; // After each swap the heap top element and the last element in the heap, the heap must be adjusted if (inverse) { heapAdjustS(array, 0, i); } else { heapAdjustB(array, 0, i); } } } public static void main(String[] args) { int[] array = { 49, 38, 65, 97, 76, 13, 27, 49 }; heapSort(array, false); for (int i : array) { System.out.print(i + " "); } }}Running results:
The node to be adjusted at the beginning of the initial heap is: array[3] = 97 The child will be smaller with the child array[7] = 49 The child is smaller with the child, and the node to be adjusted at the end of the adjustment is: array[2] = 65 The child is smaller with the child array[5] = 13 The child is smaller with the child, and the node to be adjusted at the end of the adjustment is: array[1] = 38 The child is larger with the child array[3] = 49 The child is larger with the child array[0] = 49 The child is smaller with the child array[2] = 13 The child is smaller with the child array[6] = 27 The child is smaller than the exchange position, and there is no child in the exchange position. The node to be adjusted after the adjustment is: array[0] = 97 The child is smaller than the child. The child is smaller than the child. The exchange position continues to compare with the new child. The child is array[6] = 49 The child is smaller than the exchange position, and there is no child in the exchange position. The node to be adjusted after the adjustment is: array[0] = 97 The child is smaller than the child. The child is smaller than the child. The child is smaller than the child. The child is array[1] = 38 The child is smaller than the child. The child is array[3] = 49 The child is smaller than the child. The child is smaller than the exchange position. The node to be adjusted after the adjustment is: array[0] = 65 The child is array[1] = 49 The child is smaller than the child, and the exchange position continues to be compared with the new child. The child will be larger than the child. The node to be adjusted after the adjustment is: array[0] = 76 The child is larger than the child. The node to be adjusted after the adjustment is: array[0] = 76 The child is smaller than the child. The node to be adjusted after the adjustment is: array[0] = 49 The child is smaller than the child. The node to be adjusted after the adjustment is: array[0] = 97 The child is smaller than the child. The node to be adjusted after the adjustment is: array[0] = 97 76 65 49 49 38 27 13
PS: The difference between heap sorting and direct insert sorting
In the direct selection order, in order to select the record with the smallest keyword from R[1..n], n-1 comparison must be performed, and then select the record with the smallest keyword in R[2..n], n-2 comparisons must be performed. In fact, in the following n-2 comparisons, many comparisons may have been made in the previous n-1 comparisons, but because these comparison results were not retained in the previous order, these comparison operations were repeated during the next order.
Heap sorting can save part of the comparison results through a tree structure, which can reduce the number of comparisons.