[洛谷]P3378 【模板】堆

• 最小堆插入

  从新增的最后一个结点的父结点开始，用要插入元素向下过滤上层结点（相当于要插入的元素向上渗透）

  void siftdown(int i) //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始向下调整
  {
  int t,flag=0;//flag用来标记是否需要继续向下调整
  //当i结点有儿子的时候（其实是至少有左儿子的情况下）并且有需要继续调整的时候循环窒执行
  while( i2<=n && flag==0 ) { //首先判断他和他左儿子的关系，并用t记录值较小的结点编号 if( h[ i] > h[ i2] )
  t=i2; else t=i; //如果他有右儿子的情况下，再对右儿子进行讨论 if(i2+1 <= n) { //如果右儿子的值更小，更新较小的结点编号 if(h[ t] > h[ i2+1]) t=i2+1;
  }
  //如果发现最小的结点编号不是自己，说明子结点中有比父结点更小的
  if(t!=i)
  {
  swap(t,i);//交换它们，注意swap函数需要自己来写
  i=t;//更新i为刚才与它交换的儿子结点的编号，便于接下来继续向下调整
  }
  else
  flag=1;//则否说明当前的父结点已经比两个子结点都要小了，不需要在进行调整了
  }
  }

• 最小堆删除

  void siftdown(int i) //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始向下调整
  {
  int t,flag=0;//flag用来标记是否需要继续向下调整
  //当i结点有儿子的时候（其实是至少有左儿子的情况下）并且有需要继续调整的时候循环窒执行
  while( i2<=n && flag==0 ) { //首先判断他和他左儿子的关系，并用t记录值较小的结点编号 if( h[ i] > h[ i2] )
  t=i2; else t=i; //如果他有右儿子的情况下，再对右儿子进行讨论 if(i2+1 <= n) { //如果右儿子的值更小，更新较小的结点编号 if(h[ t] > h[ i2+1]) t=i2+1;
  }
  //如果发现最小的结点编号不是自己，说明子结点中有比父结点更小的
  if(t!=i)
  {
  swap(t,i);//交换它们，注意swap函数需要自己来写
  i=t;//更新i为刚才与它交换的儿子结点的编号，便于接下来继续向下调整
  }
  else
  flag=1;//则否说明当前的父结点已经比两个子结点都要小了，不需要在进行调整了
  }
  }
  //删除最小数
  void del(){
  dui[1]=dui[d];
  d--;
  shitdown(1);
  }

c++优先队列(priority_queue)用法详解

#include<bits/stdc++.h>
using namespace std;
int n,d;
int main(){
    priority_queue<int,vector<int>,greater<int> > dui;
    cin>>n;
    for(int i=1;i<=n;i++){
        int op;
        cin>>op;
        if(op==1){
            int num;
            cin>>num;
            dui.push(num);
        }
        else if(op==2)
            cout<<dui.top()<<endl;
        else if(op==3)
            dui.pop();
    }
    return 0;
}