堆

---

二叉堆的手写代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int heap[N], len=0;      //len记录当前二叉树的长度
void push(int x) {       //上浮，插入新元素
  heap[++len] = x;       //插入到堆底
  int i = len;
  while (i > 1 && heap[i] < heap[i/2]){    //与父节点比较，直到父节点小于新元素或新元素到堆顶
    swap(heap[i], heap[i/2]);              //交换当前节点与父节点的值
    i = i/2;                               //更新当前节点
  }
}
void pop() {                 //下沉，删除堆头，调整堆
  heap[1] = heap[len--];     //根结点替换为最后一个结点，然后结点数量减1
  int i = 1;                 
  while ( 2*i <= len) {      //判断有无左儿子
    int son = 2*i;           //定义左儿子
    if (son < len && heap[son + 1] < heap[son])    //son<len表示有右儿子，选儿子中较小的
      son++; 
    if (heap[son] < heap[i]){     //与儿子比较
      swap(heap[son], heap[i]);   //与小的儿子交换
      i = son;                    //下沉到儿子处
    }
    else break;                   //如果不比儿子小，就停止下沉
  }
}
int main() {
  int n; scanf("%d",&n);                              //输入操作次数
  while(n--){
    int op; scanf("%d",&op);
    if (op == 1) { int x; scanf("%d",&x); push(x); } //加入堆 
    else if (op == 2) printf("%d\n", heap[1]);       //打印堆头
    else pop();                                      //删除堆头
  }
  return 0;
}

笔记：二叉堆是完全二叉树的数组形态，当进行进堆或者出堆的操作时，为了不影响堆型，元素优先级上升的就会上浮，反之优先级下降的就会下沉

priority_queue

#include<bits/stdc++.h>
using namespace std;
priority_queue<int ,vector<int>,greater<int> >q;  //升序队列，小堆顶
int main(){
  int n;  scanf("%d",&n);
  while(n--) {
    int op;   scanf("%d",&op);
    if(op==1) { int x;   scanf("%d",&x);  q.push(x); }
    else if(op==2)   printf("%d\n",q.top());
    else  q.pop();
  }
  return 0;
}

笔记：使用STL的priority_queue就不需要自己管理堆，会让代码少很大一部分