堆

一：基本原理

初始化堆的时候，如果按照插入的原理，时间复杂度是nlogn，但是通过
for (int i = n / 2; i; i—) down(i)的方式，可以把时间复杂度降到O(n)的级别，分析方法如下，从n/2 往下，最小层是0，因此倒数第二层是第二层，往下操作就是n/4 1，也就是下图的计算，算出时间复杂度会小于n。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int h[N];
int si;
int n, m;
void down(int u) {
    int t = u;
    if (u * 2 <= si && h[u * 2] < h[u]) t = u * 2;
    if (u * 2 + 1 <= si && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t) {
        swap(h[u], h[t]);
        down(t);
    }
}
//补充
void up(int u) {
    while (u / 2 && h[u / 2] > h[u]) {
        swap(h[u / 2], h[u]);
        u = u / 2;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    si = n;
    for (int i = n / 2; i; i--) down(i);
    while (m--) {
        cout << h[1] << " ";
        h[1] = h[si--];
        down(1);
    }
    return 0;
}

二：堆的全部操作

一般的堆的情况下就是前面的down和up操作就可以了，但是Dijkistra算法是需要用到这种复杂的方式的。

第五个操作修改第k个插入的数字，就需要维护两个数，用两个数组维护第k个插入的数的位置。

• ph[k] = i,第k个点的下标是i
• hp[i] = k，下标为i的点是第k个点。

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], ph[N], hp[N];
int si;
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 <= si && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= si && 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 && h[u / 2] > h[u])
    {
        heap_swap(u / 2, u);
        u /= 2;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    while (n--) {
        char op[4];
        cin >> op;
        int k,  x;
        if (!strcmp(op, "I"))
        {
            cin >> x;
            m++;
            si++;
            ph[m] = si;
            hp[si] = m;
            h[si] = x;
            up(si);
        } else if (!strcmp(op, "PM"))
        {
            cout << h[1] << endl;
        } else if (!strcmp(op, "DM"))
        {
            heap_swap(1, si);
            si--;
            down(1);
        } else if (!strcmp(op, "D"))
        {
            cin >> k;
            k = ph[k];
            heap_swap(k, si);
            si--;
            up(k), down(k);
        } else
        {
            cin >> k >> x;
            k = ph[k];
            h[k] =x;
            up(k), down(k);
        }
    }
    return 0;
}