“This article has participated in the good article call order activity, click to see: back end, big front end double track submission, 20,000 yuan prize pool for you to challenge!”
Write in front:
Hello, I’m Time.
What I’m going to bring you today is a sort algorithm called heap sort, which is related to binary trees. I use the way of illustration to explain, try to write thoroughly. Without further ado, go!
Mind mapping:
1. Heapsort concept
Heapsort is a kind of sorting algorithm designed by using the data structure of heap. The stack is an approximate complete binary tree structure and satisfies the stack property: that is, the key value or index of the child node is always less than (or greater than) its parent node.
Related concepts:
1.1 binary trees
Feature: Each node has a maximum of 2 children (no nodes with a degree greater than 2)
1.2 full binary tree
Full binary tree: all the leaves are at the bottom; Except the leaf node, each node has left and right children;
1.3. Complete binary tree
Complete binary tree: leaves are all in the bottom two layers; The last layer only lacks the leaf node on the right, so there must be leaf nodes 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
Minimum heap: the top of the heap is the smallest element in the entire heap
2. Algorithm idea
Let’s get this heaping idea out of the way, let’s get the logic out of the way, let’s not write the code.
We first have an unordered array, let’s say
int[] arr={4.2.8.0.5.7.1.3.9};
Copy the codeSince we use the heap, we must first construct the number fabric into a binary heap. If you want to sort an array from small to large, build it into the maximum heap; If you want to sort an array from small to large, you build the smallest heap.
2.1. The first step is to initialize the heap
So let’s start with how do arrays store binary trees
Note: The current node considered here must be a non-leaf node of a complete binary tree. And the left and right children of the node must be smaller than the array length, so you need to add a restriction later.
Looking at the formula in the figure above, we see that an array can store a full binary tree while preserving the relationships between the 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
In this diagram, let’s take the maximum heap as an example. To build A binary heap, A must be larger than B and C, B must be larger than D and E, and C must be larger than F and G. In other words, the parent node must be larger than the child node.
In this diagram, the maximum heap requirement is clearly not met. We first study the three nodes whose serial numbers are 3,7 and 8. The node I =3 is smaller than the node I =7 and I =8, so we need to switch positions. Note that the figure starts at 0, that is, the mock array index starts at 0.
How do you exchange? Very simple. If we look at node 0 and we set the current node index, then its lChild =index*2+1, its rChild =index*2+2; Notice that the indices start at 0.
// Initialize the heap
public static void HeapAdjust(int[] arr,int index,int len){
// Save the index of the current node
int max = index;
// Save the left and right child array subscripts
int lchild = index*2+1;
int rchild = index*2+2;
// To start adjusting, the left and right subscripts must be less than len, that is, to ensure that the array does not cross the line
if(lchild<len && arr[lchild] > arr[max]){
max=lchild;
}
if(rchild<len && arr[rchild] > arr[max]){
max=rchild;
}
// If an exchange occurs, Max must not be equal to index. In this case, the value of the Max node needs to be exchanged with the value of the index node
if(max! =index){
int temp=arr[index];
arr[index]=arr[max];
arr[max]=temp;
// After the exchange, you need to adjust Max again, because Max may not satisfy the maximum heap
HeapAdjust(arr,max,len);
}
}
Copy the codeThe above code is easy to understand. The two if statements in the middle are exchanging node index values. If one child node is greater than index, the exchange is required. If the parent index is larger than both of the children, there is no need to swap.
We know that as long as index is exchanged with lChild and rChild, index must not be Max!
So why do we have to add a recurrence to the last if statement? To see how this works, let’s take a look at what happens after a round of swapping, using the same array as above:
The first time I switch, 0 and 9, Index=9;
The second time you switch, 8 is bigger than 7 and 1, so you don’t have to switch;
On the third exchange, 2 is switched to 9, and Index is 9;
On the fourth swap, 4 and 9, Index is equal to 9, and that’s the end of the first swap.
After the round, some partners have found the problem. Although 9 successfully becomes the top element of the maximum heap, the other elements below do not meet the requirements of the maximum heap. For example, the binary tree of element 2, element 3, and element 0 in the bottom left corner does not satisfy, and neither does element 4, element 2, and element 5.
So in this step, we need to recurse and adjust the index again:
// If an exchange occurs, Max must not be equal to index. In this case, the value of the Max node needs to be exchanged with the value of the index node
if(max! =index){
int temp=arr[index];
arr[index]=arr[max];
arr[max]=temp;
// After the exchange, you need to adjust Max again, because Max may not satisfy the maximum heap
HeapAdjust(arr,max,len);
}
Copy the codeHeapsort tests:
/ / heap sort
public static int[] HeapSort(int[] arr){
int len=arr.length;
/ * *
* First step, initialize the heap, the maximum heap, from small to large
* I starts with the first non-leaf node of a complete binary tree, i.e., len/2-1 (array subscript starting at 0)
* /
for(int i=len/2-1; i>=0; i--){
HeapAdjust(arr,i,len);
}
// Print the top element of the heap, which should be the maximum element 9
System.out.println(arr[0]);
return arr;
}
Copy the codeThis code starts at the first non-leaf node of 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, 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 becomes from small to large or from large to small, which will achieve our purpose.
Here we take the top element of the maximum heap (the largest element) as an example, and the result of the last transpose is the result of sorting from the smallest to the largest.
For the first swap, we swap element 9 directly with element 0. At this time, the top element of the heap is 0, and we set the current node index=0;
At this point, we need to heap the remaining elements (excluding element 9) until the following result:
Code:
/ * *
* Second step, swap the heap-top (maximum) element with the last leaf node element of the binary heap. The purpose is to exchange elements
* I starts with the last leaf element of 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;
// After the swap, you need to readjust the binary heap from the beginning. At this point, Index=0
HeapAdjust(arr,0,i);
}
Copy the codeNote: There is a small detail here. The initialization method we wrote earlier takes three arguments: array arr, current node index, and array length len.
HeapAdjust(int[] arr,int index,int len)
Copy the codeSo, why not just pass in two arguments and just use 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.
Let’s do the second swap, we’ll swap element 8 directly with element 2, and then the top element is 2, and we’ll set the current node index=2;
At this point, we need to heap the remaining elements (excluding 9 and 8) until the following result:
At this point, we can repeat the above steps, constantly swapping the top and the last node elements of the heap, and continuously sorting the remaining elements, and finally we can get the sorted heap from the smallest to the largest, 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 sorting :"+Arrays.toString(arr));
System.out.println("After sorting :"+Arrays.toString(HeapSort(arr)));
}
/ / heap sort
public static int[] HeapSort(int[] arr){
int len=arr.length;
/ * *
* First step, initialize the heap, the maximum heap, from small to large. The purpose is to sort the elements
* I starts with the first non-leaf node of a complete binary tree, i.e., len/2-1 (array subscript starting at 0)
* /
for(int i=len/2-1; i>=0; i--){
HeapAdjust(arr,i,len);
}
/ * *
* Second step, swap the heap-top (maximum) element with the last leaf node element of the binary heap. The purpose is to exchange elements
* I starts with the last leaf element of 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;
// After the swap, you need to readjust the binary heap from the beginning. At this point, Index=0
HeapAdjust(arr,0,i);
}
return arr;
}
/ * *
* Initialize the heap
* @paramArr Binary tree to be adjusted (array)
* @paramIndex Index of the node to be adjusted, the first non-leaf node of the binary tree
* @paramLen Specifies the array length to be adjusted
* /
public static void HeapAdjust(int[] arr,int index,int len){
// Save the index of the current node
int max = index;
// Save the left and right child array subscripts
int lchild = index*2+1;
int rchild = index*2+2;
// Start the adjustment, left and right child subscripts must be less than len, that is, make sure index must be non-leaf node
if(lchild<len && arr[lchild] > arr[max]){
max=lchild;
}
if(rchild<len && arr[rchild] > arr[max]){
max=rchild;
}
// If an exchange occurs, Max must not be equal to index. In this case, the value of the Max node needs to be exchanged with the value of the index node
if(max! =index){
int temp=arr[index];
arr[index]=arr[max];
arr[max]=temp;
// After the exchange, you need to adjust Max again, because Max may not satisfy the maximum heap
HeapAdjust(arr,max,len);
}
}
}
Copy the codeRunning result:
4. Algorithm analysis
4.1. Time complexity
HeapAdjust, which is the key to heapsort, takes order log n time, so let’s look at the two heapsort processes;
The first step is to initialize the heap, which takes O(n) time.
The second step, swapping the top elements of the heap, takes n-1 cycles, and each time it uses (HeapAdjust), so the time complexity is ((n-1)*log n)~O(nlog n);
The final time complexity is O(n)+O(nlog n), the latter is more complicated than the former, so the time complexity of heapsort is O(nlog n);
4.2. Space complexity
The space complexity is O(1), because the extra set space is not used.
4.3 Algorithm stability
Heapsort is unstable, for example, a binary tree [6a, 8,13, 6b], (6a and 6b are both 6, just to distinguish them), after heap initialization and sorting becomes [6b, 6a, 8,13]; You can see that heap sorting is unstable.