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, &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 < a[j]) { topk = 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 = 100001; a = 100002; a = 123456; a = 100003;
a = 100009; a = 111111; a = 222222; a = 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
Daily Recommendation
views 2076
views 274
views 267
views 243
views 232
views 231