Write at the front:
Hello, I am Time.
What I’m going to show you today is heap sort, which is a sort associated with binary trees. I’ll explain it in graphic form and try to write it thoroughly. Without further ado, begin!
Mind map:
1. Heap sort concept
HeapSort refers to a sort algorithm designed using the data structure of heap. A heap is an almost complete binary tree structure, while satisfying the property of a heap: the key or index of a child node is always smaller (or greater) than that of its parent node.
Related concepts:
1.1. Binary trees
Feature: Each node has at most 2 child nodes (no node with degree greater than 2)
1.2, Full binary tree
Full binary tree:
The leaves are all at the bottom;
Each node, except the leaf node, has left and right children;
1.3, Complete Binary Tree
Complete binary tree:
The leaves are all in the bottom two layers;
The last layer is missing only the right leaf node, so there must be a leaf node on the left;
Except for the last layer, the number of nodes in other layers reaches the maximum;
1.4, Maximum heap and minimum heap
Maximum heap: The top of the heap is the largest element in the entire heap
Minimal heap: The top of the heap is the smallest element in the entire heap
2. Algorithm thinking
Let’s get this idea of heap sort straight, let’s get the logic straight, let’s not rush to write the code.
So let’s first have an unordered array, let’s say
,2,8,0,5,7,1,3,9 int [] arr = {4};Since we need a heap, we must first build the number fabric into a binary heap. If you want to sort the array from small to large, build it to the maximum heap. An array that needs to be sorted from smallest to largest is built into the smallest heap.
2.1. First step, initialize the heap
So let’s first look at how does an array store a binary tree
Note: the current node considered here must be a non-leaf node of the full binary tree. And the left and right children of the node must be smaller than the size of the array, so we need to add constraints later.
From the formula in the figure above, we understand that an array can store a full binary tree while preserving the relationships between nodes. Take the array above as an example
So once you’ve stored it, how do you build a binary tree into a binary heap? Keep reading
For example, in this diagram, let’s take the maximum heap, if we want to build A binary heap, A has to be larger than B and C, B has to be larger than D and E, and C has to be larger than F and G. The parent node must be larger than the child node.
In this diagram, the maximum heap requirement is clearly not satisfied. Let’s start with the number 3,7, and 8 nodes. The node I =3 is smaller than the node I =7 and the node I =8, so we need to switch positions. Note that this graph starts at 0, meaning that the subscript of the mock array starts at 0.
How do I do that? Very simple. Lchild =index*2+1; Rchild =index*2+2; Rchild =index*2+2; Notice that the subscripts start at 0.
Public static void HeapAdjust(int[] arr,int index,int len){int Max = index; Int lchild = index*2+1; int lchild = index*2+1; int rchild = index*2+2; If (lchild<len && arr[lchild] > arr[Max]){Max =lchild; } if(rchild<len && arr[rchild] > arr[max]){ max=rchild; } // If swapping occurs, then Max is definitely not equal to index. The value of the Max node must be swapped with the value of the index node. If (Max! =index){ int temp=arr[index]; arr[index]=arr[max]; arr[max]=temp; // After swapping, we need to adjust the Max again because it is possible that the Max will not meet the maximum heap HeapAdjust(arr, Max,len); }}The above code is easy to understand. The two if statements in the middle are swapping the value of the node index. If one of the children is greater than the index, the swapping is required. If the parent index node is larger than both child nodes, then no swap is required.
If index swaps lchild and rchild, then index must not be equal to Max!
So why do we have a recursive notation in the last if statement? Let’s use an example to see what this array looks like after one swapping round:
So the first time we swap 0 with 9, Index=9;
The second time you swap, 8 is already bigger than 7 and 1, so you don’t have to swap;
The third swap, 2 is swapped with 9, so Index=9;
And then the fourth swap, 4 swapped with 9, right there
Index=9. That’s the end of the first swap.
At the end of one round, one of the partners has found the problem. Although 9 successfully becomes the top element of the largest heap, other elements below do not satisfy the requirement of the top element of the largest heap. For example, the binary tree of element 2, element 3, element 0 in the lower left corner does not satisfy the requirement of the top element of the largest heap, and element 4, element 2, element 5 do not satisfy the requirement of the top element of the largest heap.
Therefore, we need to perform recursive operation in the step of swapping node values, and then adjust the heap of index again after swapping node values:
// If the switch occurs, then Max is definitely not equal to index. The value of the Max node must be swapped with the value of the index node. If (Max! =index){ int temp=arr[index]; arr[index]=arr[max]; arr[max]=temp; // After swapping, we need to adjust the Max again because it is possible that the Max will not meet the maximum heap HeapAdjust(arr, Max,len); }Heap sort test:
Public static int[] HeapSort(int[] arr){int len=arr.length; /** * for(int I =len/2-1; int I =len/2-1; int I =len/2-1; i>=0; i--){ HeapAdjust(arr,i,len); } println(arr[0]); println(arr[0]); println(arr[0]); return arr; }The code above starts with the first non-leaf node in the full binary tree and prints the top element of the heap, which should be 9;
At this point, the first step, initialization of the heap, is complete, and the final result should look like this:
2.2. The second step is heap sort
The process of heap sort is to swap the top element (maximum or minimum value) with the last leaf node of the binary heap, and keep swapping until the order of the binary heap changes from small to large or from large to small, which achieves our purpose.
Let’s take the top element of the largest heap (the largest element) as an example, and the result of swapping is sorted from small to large.
In the first swap, we directly swap element 9 with element 0, where the top element of the heap is 0, and we set the current node
index= 0;
At this point, we need to heap sort the remaining elements (excluding element 9) until we get the following result:
Code:
/** * In the second step, swap the top (largest) element and the last leaf element in the binary heap. * I starts at the last leaf element in the binary heap, i.e., len-1 (array index starts at 0) */ for(int I =len-1; i>=0; i--){ int temp=arr[i]; arr[i]=arr[0]; arr[0]=temp; // When Index=0 HeapAdjust(arr,0, I); }Note: There is a small detail here. The initialization heap method we wrote earlier takes three arguments: array arr, current node index, and array length len, as follows:
HeapAdjust(int[] arr,int index,int len)So, why not just pass in two arguments and the length of the array can be expressed by arr.length? Initializes the heap can be, but the back at the top of the heap exchange elements and at the end of the leaf node, with the rest of the element to sort the array length is not arr. Length, should be to change the parameters of I, because after the exchange of elements (such as 9) is not included in the heap sort, so need three parameters.
We do a second swap, we directly swap element 8 with element 2, the top element of the heap is 2, let’s say the current node
index= 2;
At this point, we need to heap sort the remaining elements (excluding elements 9 and 8) until we get the following result:
At this point, we repeat the above steps and keep swapping the top and the last node elements of the heap. Then we keep sorting the remaining elements and finally we can get the sorted heap from small to large, as shown in the figure below. This is the result we want:
3. Complete code
import java.util.Arrays; Public class Head_Sort {public static void main(String[] args) {int[] arr={4,2,8,0,5,7,1,3,9}; System.out.println(" before sort :"+Arrays.toString(arr)); System.out.println(" Arrays :"+Arrays.toString(HeapSort(Arr)))); } public static int[] HeapSort(int[] arr){int len=arr.length; /** * The first step is to initialize the heap, from small to large. * I starts at the first non-leaf node in the full binary tree, i.e., len/2-1 (array index starts at 0) */ for(int I =len/2-1; i>=0; i--){ HeapAdjust(arr,i,len); } /** * In the second step, swap the top (largest) element of the heap and the last leaf element of the binary heap. * I starts at the last leaf element in the binary heap, i.e., len-1 (array index starts at 0) */ for(int I =len-1; i>=0; i--){ int temp=arr[i]; arr[i]=arr[0]; arr[0]=temp; // When Index=0 HeapAdjust(arr,0, I); } return arr; } /** * Initialize the heap * @Param arr * @Param index * @Param index * @Param index * @Param index * @Param index Public static void heapAdjust (int[] arr,int index,int len){// Adjust(int[] arr,int index,int len) index; Int lchild = index*2+1; int lchild = index*2+1; int rchild = index*2+2; If (lchild<len && arr[lchild] > arr[Max]){Max =lchild; } if(rchild<len && arr[rchild] > arr[max]){ max=rchild; } // If swapping occurs, then Max is definitely not equal to index. The value of the Max node must be swapped with the value of the index node. If (Max! =index){ int temp=arr[index]; arr[index]=arr[max]; arr[max]=temp; // After swapping, we need to adjust the Max again because it is possible that the Max will not meet the maximum heap HeapAdjust(arr, Max,len); }}}Running results:
4. Algorithm analysis
4.1. Time complexity
Heapadjust is the key to heap sorting when the heap is built. The time complexity is O(log n). Here are two processes for heap sorting.
The first step, initializing the heap, is O(n);
The second step, the process of swapping the top heap elements, required n-1 cycles and HeapAdjust was used at each time, so the time complexity was (n-1)*log n)~O(nlog n).
The final time complexity is O(n)+O(nlog n), the latter is higher than the former, so the time complexity of heap sort is O(nlog n);
4.2. Spatial complexity
The space complexity is O(1), because I’m not using any extra set space.
4.3. Algorithm stability
The heap sort is not stable. For example, the binary tree [6a, 8,13, 6b] (6a and 6b are both 6 in value, only for the difference between 6) becomes [6b, 6a, 8,13] after the heap is initialized and sorted. You can see that heap sort is unstable.