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