数据结构-堆

手写堆

堆排序

问题描述：

输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。

解决思路：

与上面的写的思路一样实现对应的代码即可

代码：

#include<iostream>
using namespace std;
const int N=1e5+10;
int h[N];
int n,m;
int cnt;
void down(int u){
    int t=u;
    if(u*2<=cnt&&h[t]>h[2*u]) t=u*2;
    if(u*2+1<=cnt&&h[t]>h[2*u+1]) t=2*u+1;
    if(u!=t){
        swap(h[u],h[t]);
        down(t);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);
    cnt=n;
    for(int i=n/2;i;i--) down(i);
    while(m--){
        printf("%d ",h[1]);
        h[1]=h[cnt];
        cnt--;
        down(1);
    }
    return 0;
}

堆的简单实现

C++中的优先队列是 由二叉堆 实现的。 默认是使用 大根堆 实现。

优先队列的 基本操作 ：

    empty()   如果队列为空返回真

    pop()       删除队顶元素

    push()     入队一个元素

    size()      返回优先队列中拥有的元素个数

    top()        返回优先队列队顶元素

priority_queue<int> 
   是默认的大根堆实现，top()是当前优先队列的最大值。
priority_queue<int,vector<int>,greater<int>>
    是 最小值的优先队列
priority_queue<int,vector<int>,less<int>>
    是 最大值的优先队列