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
Daily Recommendation
views 267
views 232
views 231