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=;i<=n;i++){

        int x;

        scanf("%d",&x);

        q.push(x);//push为入队操作，然后系统自动为你建立小根堆并维护

    }

    while(!q.empty()){//非空

        printf("%d ",q.top());//输出堆顶元素

        q.pop();//删除（弹出）堆顶，然后维护

    }

    return ;

}

完结✿ヽ(°▽°)ノ✿

推荐一个呗

巴特西

P1177 【模板】快速排序题解

最新文章

热门文章

巴特西

P1177 【模板】快速排序 题解

最新文章

热门文章

P1177 【模板】快速排序题解