©2020-2024 ioDraw All rights reserved
The time complexity of the last heap sorting through the array is O(NlogN), The space complexity is O(N).
Time complexity after optimization O(NlogN), Spatial complexity O(1).
Consider the optimization scheme ：
1. Adjust reactor building downward .
2. Adjust reactor building upward .
The heap is built only to find the largest or smallest element in the heap .
1. Adjust reactor building upward
Use up adjustment , The idea of inserting data to build a heap .
The essence of the optimization scheme is to process the original array without opening up new space , Make its spatial complexity O（1）.
void HeapSort2(int* a,int n) { for (int i = 1; i < n; i++) { AdjustUp(a, i); }
for(int i= 0;i<n;i++) printf("%d ", a[i]); printf("\n"); }
Now calculate its time complexity , For the convenience of calculation , Full binary tree is used to calculate .
The worst case scenario is considered below ：
The second floor ： 2^1 Nodes , Upward adjustment 1 layer ;
Third floor ： 2^2 Nodes , Move up 2 layer ;
……
The first h layer ：2^(h-1) Nodes , Move up h-1 layer .
The number of nodes to be moved ：
T (n) = 2^1 * 1+ 2^2*2 +…+ 2^(h-1)*(h-1)
According to the summation formula of the dislocation subtraction method of the sequence
T(n) = (N+1) * ( log(N+1) - 2 )+2 When n-> Infinity T(n) = NlogN
The time complexity of upward heap building is O(N*logN).
2. Adjust reactor building downward
Prerequisite requirements ： Yes, it must be a lot or a small pile .
So we need to adjust the array first .
Start from the penultimate non leaf node （ Parent node of the last node ）.
Because leaf nodes can be regarded as large or small piles alone .
Draw a picture ：
Adjustment times ：4 second
code ：
void HeapSort3(int* a, int n) { for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(a, n, i); } for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n"); }
Spatial complexity ：O（1）, Time complexity O（N）
It is proved that the time complexity ：
first floor ：2^0 Nodes , Need to move down h-1 layer .
The second floor ：2^1 Nodes , Need to move down h-2 layer .
Third floor ：2^2 Nodes , Downward adjustment required h-3 layer .
……
The first h-1 layer ,2^(h-2) Nodes , Need to move down 1 layer .
So the total number of moves ：
T(n) = 2^0 *(h-1) + 2^1 *(h-2) + …+ 2^(h-2)* 1
According to the dislocation subtraction method ：
T(n) = 2^h - 1 - h
also n = 2^h - 1
T(n) = n - log(n+1)
When n Infinite time , Approximate view T(n) = n
Proof complete .
Now that there are two methods to build a heap up and a heap down , So what kind of situation is to build a team , Which one is more suitable to see ??
Ascending order -- Build a pile
reason ： If you build a small heap in ascending order, the smallest number is already in the first position , The rest of the relationship is in a mess , The reactor needs to be rebuilt , Building pile O(N), Choose the next smaller one , Continuous heap selection , So with time complexity O(N) It's not as easy as traversing directly .
in short , Build small piles in ascending order , Low efficiency , Also complex .
Descending order -- Build a small pile
So how to build a stack to complete sorting ?
Building a pile is essentially to maintain the stability of the pile as much as possible .
After finding the maximum number , Swap the number of root positions with the last number , stay n-1 Downward adjustment in group data , Small number of times found , Connect the root with the second n-1 Number exchange of positions , In order to achieve ascending order .
Related code ：
void HeapSort4(int* a, int n) { for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
// Build a pile AdjustDown(a, n, i); } // Find the subscript of the last number int end = n - 1; while (end > 0) {
// Swap the values of the root and the last position Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } for (int i
= 0; i < n; i++) printf("%d ", a[i]); printf("\n"); }
Top - k problem
Find the front and middle of data combination k Maximum or minimum elements , Generally, the amount of data is relatively large .
Top-k The simplest method in is sorting , If the amount of data is very large , There will be problems with sorting （ Data cannot be loaded into memory at one time ）, But heap sorting can be solved .
1. Use the first element in the array to build the heap .
Find the maximum to build a small pile , Find the minimum and build a pile .
And ascending order , The principle of building small reactors in descending order is similar .
2. Use the remaining n-k Compare the elements with the elements on the top , To replace the opposite top element .
Remember to adjust downward .
void TopK(int* a,int n,int k) { // Build a small pile int* topk = (int*)malloc(sizeof(int) *
k); assert(topk); for (int i = 0; i < k; i++) { topk[i] = a[i]; } // Adjust reactor building downward for
(int i = (k - 1 - 1) / 2; i >= 0; i--) { AdjustDown(topk, k, i); } for (int j =
k; j < n; j++) { if (topk[0] < a[j]) { topk[0] = a[j]; AdjustDown(topk, k, 0);
} } for (int i = 0; i < k; i++) { printf("%d ", topk[i]); } printf("\n");
free(topk); } int main() { int n = 10000; int* a = (int*)malloc(sizeof(int) *
n); assert(a); srand(time(0)); for (int i = 0; i < n; i++) { a[i] = rand() %
10000; } a[0] = 100001; a[101] = 100002; a[159] = 123456; a[7459] = 100003;
a[7412] = 100009; a[7826] = 111111; a[7712] = 222222; a[9635] = 999999;
TopK(a,n,8); return 0; }
Time complexity O( K+ K*log(N-K) )
Spatial complexity ：O(K)
When K<<N Time , Very efficient, too .
If there is something wrong, please point it out .
Technology