堆

如何手写一个堆？

1. 插入一个数
   1. heap[++size] = x; up(x);
2. 求集合当中的最小值
   1. heap[1]
3. 删除最小值
   1. heap[1] = heap[size--]; down(1)
4. 删除任意一个元素
   1. heap[k] = heap[size--]; down(k); up(k);
5. 修改任意一个元素
   1. heap[k] = x; down(k); up(k);

堆是完全二叉树

存储方式：一维数组

操作

down(int x){
    与小儿子交换
}

up(int x){
    与父节点交换
}

堆排序

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int h[N];
int n, m, sz;

void down(int u){
    int t = u;          //用于临时存储
    if(2 * u <= sz && h[2 * u] < h[t]) t = 2 * u;           //特别注意u与t的区别
    if(2 * u + 1 <= sz && h[2 * u + 1] < h[t]) 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++) cin >> h[i];

    sz = n;

    for(int i = n / 2;i;i--) down(i);

    while(m--){
        cout << h[1] << " ";
        h[1] = h[sz --];
        down(1);
    }

    return 0;
}

模拟堆

• 这里的swap操作需要重写，应为替换或删除的是第k个插入的数，而不是堆中的第k个数，删除操作会导致第k个插入并不等价于第k个数
• 这里使用hp[]数组存储堆中的下标与第i个插入(heap to position)
• 使用ph[]数组存储第i个插入的数在堆中对应的下标(position to heap)
• 注意：
  • 传入函数的参数是第k个插入
  • 在进行swap操作时候，对hp和ph也要进行相应的交换操作
  • 交换hp操作：具体是通过ph获取第k个插入的数在堆中的下标i,j，再通过ph获得下标i, j对应的第k个插入，并进行交换
  • 交换ph操作：直接交换ph[a]与ph[b]

    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int N  = 1e5 + 10;
    int n;
    int h[N], hp[N], ph[N], sz, cnt;
    //hp数组记录插入的是第几个
    //ph数组记录第几个插入
    
    void heap_swap(int a, int b){
        swap(h[a], h[b]);           //交换堆中的值
        swap(hp[a], hp[b]);         //交换堆中对应的下标
        swap(ph[hp[a]], ph[hp[b]]); //交换下标对应的插入数
    }
    
    void down(int k){
        int t = k;
        if(k * 2 <= sz && h[k * 2] < h[t]) t = k * 2;
        if(k * 2 + 1 <= sz && h[k * 2 + 1] < h[t]) t = k * 2 + 1;
        if(t != k) {
            heap_swap(t, k);
            down(t);
        }
    }
    
    void up(int k){
        while(k / 2 && h[k / 2] > h[k]){
            heap_swap(k/2, k);
            k = k >> 1;
        }
    }
    
    
    int main(){
        cin >> n;
        char op[5];
        int a, b;
        while(n--){
            scanf("%s", op);
            if(!strcmp(op, "I")){          //插入
                scanf("%d", &a);
                sz ++;
                cnt ++;
                h[sz] = a;
                ph[cnt] = sz;
                hp[sz] = cnt;
                up(sz);
            }
            else if(!strcmp(op, "PM"))     //输出最小值
            {
                cout << h[1] << endl;
            }
            else if(!strcmp(op, "DM")){    //删除最小值
                heap_swap(1, sz);
                sz--;
                down(1);
            }
            else if(!strcmp(op, "D")){     //删除第k个插入的数
                scanf("%d", &a);
                a = ph[a];
                heap_swap(a, sz);
                sz --;
                down(a);
                up(a);
            }
            else{                   //修改第k个插入的数
                scanf("%d%d", &a, &b);
                a = ph[a];
                h[a] = b;
                down(a);
                up(a);
    
            }
        }
    
        return 0;
    }