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 ;
}

完结✿ヽ(°▽°)ノ✿

推荐一个呗

上一篇:Oracle数据库web维护客户端管理工具软件


下一篇:JS数组操作中的经典算法