Heap is an important structure in the data structure. After understanding the concept and operations of "heap", you can quickly master heap sorting.
The concept of heap
Heap is a special complete binary tree. If the values of all nodes of a completely binary tree are not smaller than their children, it is called a large root heap (or large top heap); if the values of all nodes are not larger than their children, it is called a small root heap (or small top heap).
In an array (storing the root node in the subscript number 0), it is easy to get the following equation (these two equations are very important):
1. The node with subscript is i, and the coordinates of the parent node are (i-1)/2;
2. The node with subscript is i, the coordinates of the left child node are 2*i+1, and the right child node is 2*i+2.
Heap establishment and maintenance
The heap can support multiple operations, but now we only care about two issues:
1. Given an unordered array, how to build it as a heap?
2. After deleting the top element of the heap, how to adjust the composition to a new heap?
Let’s look at the second question first. Suppose we already have a ready-made large root pile. Now we delete the root element, but we don't move the other elements. Think about what happened: the root element is empty, but the other elements still maintain the properties of the heap. We can move the last element (code name A) to the position of the root element. If it is not a special case, the properties of the heap are destroyed. But this is simply because A is smaller than one of its child elements. So, we can switch A and this child element to position. If A is greater than all its child elements, the heap is adjusted; otherwise, repeat the above process, element A continues to "sink" in the tree structure until it is appropriate, and the array restores the properties of the heap. The above process is generally called "screening", and the direction is obviously from top to bottom.
This is true when deleting an element, and so is inserting a new element. The difference is that we put the new element at the end and then compare it with its parent node, that is, filter it from the bottom up.
So, how to solve the first problem?
Many of the books on data structures I have read are filtering down from the first non-leaf node until the root element is filtered. This method is called "filtering method", which requires loop filtering n/2 elements.
But we can also learn from the idea of "creating something out of nothing". We can regard the first element as a heap and then constantly add new elements to it. This method is called "insert method", which requires loop insertion of (n-1) elements.
Since the filtering method and insertion method are different, the heaps they create are generally different for the same data.
After a rough understanding of the heap, the heap sorting is a natural thing.
Algorithm overview/ideas
We need an ascending sequence, what should we do? We can build a minimum heap and then output the root element each time. However, this method requires extra space (otherwise it will cause a lot of element movement, and its complexity will soar to O(n^2)). What if we need in-place sorting (i.e., there is no O(n) space complexity allowed)?
There is a way. We can build the maximum heap, and then we output the maximum value in the last position, and the second maximum value in the last position... Since the maximum element output each time will free up the first space, we can just place such an element without needing extra space. Very beautiful idea, right?
public class HeapSort { public static void main(String[] args) { int[] arr = { 50, 10, 90, 30, 70, 40, 80, 60, 20 }; System.out.println("Before sorting: "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } // Heap sorting heapSort(arr); System.out.println(); System.out.println("After after sorting: "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } /** * Heap sort*/ private static void heapSort(int[] arr) { // Construct the sequence to be sorted into a large top heap for (int i = arr.length / 2; i >= 0; i--){ heapAdjust(arr, i, arr.length); } // Gradually swap the root node of each maximum value with the end element, and adjust the binary tree to make it a large top heap for (int i = arr.length - 1; i > 0; i--) { swap(arr, 0, i); // Exchange the heap top record with the last record of the currently unsorted subsequence heapAdjust(arr, 0, i); // After the exchange, it is necessary to recheck whether the heap meets the big top heap. If it does not meet, it needs to be adjusted} } /** * Process of building the heap* @param arr Array that needs to be sorted* @param i The number of the root node of the heap that needs to be built* @param n The length of the array*/ private static void heapAdjust(int[] arr, int i, int n) { int child; int father; for (father = arr[i]; leftChild(i) < n; i = child) { child = leftChild(i); // If the left subtree is smaller than the right subtree, you need to compare the right subtree with the parent node if (child != n - 1 && arr[child] < arr[child + 1]) { child++; // Increase the serial number by 1, pointing to the right subtree} // If the parent node is smaller than the child node, you need to exchange if (father < arr[child]) { arr[i] = arr[child]; } else { break; // The large top heap structure is not destroyed, no adjustment is required} } arr[i] = father; } // Get the left child node private static int leftChild(int i) { return 2 * i + 1; } // Swap element position private static void swap(int[] arr, int index1, int index2) { int tmp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = tmp; } }