P1177 【模闆】快速排序 題解

本質為sort，這裡我們用優先隊列（堆）解決。

什麼是堆？

堆

堆是一個完全二叉樹，而且是每層都有規律的二叉樹

規律大概是：

小根堆：最上層數的大小最小，往下每層結點都比父親結點大，比兩個兒子結點小

大根堆：最上層數的大小最大，往下每層結點都比父親結點小，比兩個兒子結點大

這裡sort為從小到大排序，那麼我們用小根堆就OK足矣

（能看這篇題解的人都是想學習的好孩子（不想學的直接一遍sort過了），我為你點贊！QWQ）

涉及英文單詞：priority _ queue：    　優先 _ 隊列 QWQ

代碼如下：

#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;//開一個名字為q的優先隊列 
//vector我不知道是幹啥的後面肯定會學。。反正必須要加背過就行了 
//greater為小根堆，不加的話為大根堆 
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        q.push(x);//push為入隊操作，然後系統自動為你建立小根堆并維護 
    }
    while(!q.empty()){//非空 
        printf("%d ",q.top());//輸出堆頂元素 
        q.pop();//删除（彈出）堆頂，然後維護 
    }
    return 0;
}      

完結✿ヽ(°▽°)ノ✿

推薦一個呗

轉載于:https://www.cnblogs.com/lbssxz/p/10777821.html