Heap acwing 838 Heap sort

Pile up AcWing 838. Heap sort

Original link

AcWing 838. Heap sort

Algorithm tags

Pile up

Ideas

The nature of the heap

Perfect binary tree

Common heap

Heap The root node stores the minimum value , The storage value of the left and right nodes is greater than that of the root node
Big root pile The maximum storage value of the root node , The storage value of the left and right nodes is smaller than that of the root node

storage
Use one-dimensional array storage . Be careful ： Here the array subscript is from 1 Start
If from 0 Start , Then the root node will be overwritten by the left son of the root node

Basic operation of the heap

down operation Compare the current node with the left and right sons , If the current node > The smaller of the left and right sons , Exchange the current node with the position of the smaller value in the left and right sons , Recursively perform the above operations after exchange , Until you find the right place
up operation Compare the current node with the root node , If the current node < The root node , Exchange the current node with the root node , Recursively perform the above operations after exchange , Until you find the right place
To ensure the stability of the reactor structure , For insert and delete operations , Choose to operate at the end of the array

The basic operation pseudo code of heap

The construction of the heap

If it is inserted from the tail in turn , Time complexity of each insertion log(n), Need to insert n Elements , Time complexity n*log(n)
If from N/2 Insert , It can be guaranteed in O(n) The time complexity is inserted n Elements
Proof process

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 100005;
// p Storage node ancestor node  s Store the number of connected block nodes 
int a[N];
int s;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
//  Select the smaller value of the left and right nodes 
void down(int x){
    int u=x;
    if(x*2<=s&&a[x*2]<a[u]){
        u=x*2;
    }
    if(x*2+1<=s&&a[x*2+1]<a[u]){
        u=x*2+1;
    }
    if(x!=u){
        swap(a[x], a[u]);
        down(u);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n=read(), m=read();
    s=n;
    rep(i, 1, n+1){
        a[i]=read();
    }
    Rep(i, n/2, 0){
        down(i);
    }
    while(m--){
        printf("%lld ", a[1]);
        a[1]=a[s--];
        down(1);
    }
    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support