手写优先队列

优先队列

用数组实现大/小顶堆，子节点=父节点*2或者*2+1。

用数组构造二叉树，push元素时先存到最后一个节点，然后从最后一个节点迭代与父节点比较交换，一直到第一个节点或者停止交换。

pop时直接交换第一个节点和最后一个节点，然后从第一个节点迭代与两个子节点中较大/小的那个比较交换，一直到最后一层节点或者停止交换。

#include<iostream>

using namespace std;

int a[10010];
int siz;

void push(int x){
    a[++siz] = x;
    int son = siz;
    int par = son/2;
    while(par>=1){ 
        if(a[son]>a[par]){ // 小顶堆为 < 
            swap(a[son], a[par]);
            son = par;
            par = son/2;
        }else{
            break;
        }
    }
}

int top(){
    return a[1];
}

int pop(){
    a[1] = a[siz--];
    
    int par = 1;
    int son = par*2;
    while(son<=siz){
        if(son+1<=siz&&a[son+1]>a[son]){ // 小顶堆为 < 
            son ++;
        }
        if(a[son]>a[par]){ // 小顶堆为 < 
            swap(a[son], a[par]);
            par = son;
            son = par*2;
        }else{
            break;
        }
    }
}

int main(){

    int n;
    cin>>n;
    siz = 0;
    int x;
    for(int i=1;i<=n;i++){
        cin>>x;
        push(x);
    }
    for(int i=1;i<=n;i++){
        cout<<top()<<" ";
        pop();
    }
    
    return 0;
}