C++STL中默认的优先队列是大根堆，即父结点总是比子结点大。

那么priority_queue<int> PQ即声明一个int型大根堆

如果想要声明一个小根堆则需要这么声明priority_queue<int, vector<int>, greater<int> > pq。

我们知道堆的模型就是完全二叉树（定义看不懂的自行补课）

（完全二叉树：如果二叉树的深度为k，则除第k层外其余所有层节点的度都为2，且叶子节点从左到右依次存在。也即是，将满二叉树的最后一层从左到右依次删除若干节点就得到完全二叉树。满二叉树是一棵特殊的完全二叉树，但完全二叉树不一定是满二叉树。）

 

这里我们以小根堆为例，即父结点一定小于等于它的所有子结点

手动模拟堆分主要实现这几个操作，1.堆中特有的交换  2.down操作  3.up操作

1.down操作是指当父结点比子结点大的时候，我们的小根堆中大的元素都是往下存储的，即往更为子结点的方向，因此从树的模型上来看是向下压的。

2.up操作正好与down操作相反，但是实现时更为简单，因为up操作只需要与其父结点比较即可，往上交换直至满足父小子大。

3.而堆中特有的交换正是与他们的up操作和down操作有关，由于up和down都会导致元素在完全二叉树中的位置改变。举个例子：
Acwing 839 : https://www.acwing.com/problem/content/841/

这个题中就要求求出插入的第k个数，以及最小值中插入的最早的。

 

图解关键点：

1.

2.

 

 

 

 

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;
int h[N], ph[N], hp[N]; //ph[k]代表第k个元素在堆中的位置，hp[k]代表堆中第k个位置的数是第几个插入的数
int size, ord;
int n;


//先找到树中两个元素的插入顺序，再交换他们在堆中的位置。
//再交换两者的插入顺序，注意这里是因为两者在堆中的位置的改变，因此要改变插入顺序的指向
//最后交换两个元素的值
void heap_swap(int a, int b){
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u){
    int t = u;
    if(u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t){
        heap_swap(u, t);
        down(t);
    }
}

void up(int u){
    while(u / 2 >= 1 && h[u / 2] > h[u]){
        heap_swap(u / 2, u);
        u /= 2;
    }
}

int main()
{
    scanf("%d", &n);
    
    while(n--){
        char op[5];
        int k, x;
        
        scanf("%s", op);
        if(strlen(op) == 2){
            if(op[0] == 'P')
                printf("%d\n", h[1]);
            else if(op[0] == 'D'){
                heap_swap(size, 1);
                size--;
                down(1);
            }
        }
        
        else{
            
            if(op[0] == 'I'){
                scanf("%d", &x);
                size++;
                ord++;
                ph[ord] = size;
                hp[size] = ord;
                h[size] = x;
                up(size);
            }
            
            else if(op[0] == 'D'){
                scanf("%d", &k);
                k = ph[k];
                heap_swap(k, size);
                size--;
                down(k);
                up(k);
            }
            
            else if(op[0] == 'C'){
                scanf("%d%d", &k, &x);
                k = ph[k];
                h[k] = x;
                down(k);
                up(k);
            }
        }
    }
    
    return 0;
}