關於堆的一切

前置知識

首先給出堆的定義：
堆是一顆樹，滿足堆的性質，即：
對於一個節點，它的權值大於（或小於）它的各個兒子的權值

有這個性質，顯然
堆的根節點權值是整個堆中最大或最小的
由此可分為小根堆和大根堆

二叉堆

最常見的堆就是二叉堆
二叉堆是一顆滿足堆的性質的完全二叉樹
顯然，二叉堆的子樹也是二叉堆

接下來，我們以小根堆為例：

當一個節點權值小於其父親時，我們嘗試不斷將這個節點與父親交換，直到其滿足堆的性質
這就是向上調整

同理，
當一個節點權值大於其父親時，我們嘗試不斷將這個節點與其兩個兒子中權值較小的一個交換，直到其滿足堆的性質
這就是向下調整

為什麼這裡要與權值較小的一個交換呢？
因為我們要使交換後滿足堆的性質
所以新的父節點權值應小於它的兩個兒子

由於堆的高度為 \(\log{n}\)
所以以上兩個操作複雜度顯然為 \(\mathcal {O}(\log{n})\)

那麼有了這兩個操作我們就可以完成：
插入（新建節點然後向上調整）
查詢最大（最小）值（根節點權值）
刪除最大（最小）值（與末尾節點交換，再向下調整）
刪除任意節點（與末尾交換，再向上或向下調整，見代碼）
修改任意節點權值（向上或向下調整）

Luogu （模板）堆

#include<bits/stdc++.h>

using namespace std;

static constexpr int AwA = 1e6 + 10;

inline static int Read() {
    int res = 0;
    bool flag = false;
    int c = getchar();
    while ((c < '0' || c > '9') && ~c) {
        flag |= c == '-';
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        res = (res << 1) + (res << 3) + (c ^ 48);
        c = getchar();
    }
    return flag ? -res : res;
}

//這裡我們認為一個節點的父親是u<<1，左兒子為u>>1，右兒子為u>>1|1
//根為1
//由堆為完全二叉樹的性質可得只需開一倍數組
int val[AwA];
//儲存總節點數
int len;

inline void MoveUp(int u) {
    while (u >> 1) {
        int fa = u >> 1;
        if (val[fa] <= val[u]) break;
        swap(val[fa], val[u]);
        u = fa;
    }
}

inline void MoveDown(int u) {
    while (u << 1 <= len) {
        int son = u << 1;
        if (son < len && val[son | 1] < val[son]) son |= 1;
        if (val[u] <= val[son]) break;
        swap(val[u], val[son]);
        u = son;
    }
}

inline int GetTop() { return val[1]; }

inline void Pop() {
    swap(val[1], val[len]);
    len--;
    MoveDown(1);
}

inline void Push(int _val) {
    val[++len] = _val;
    MoveUp(len);
}

//刪除任意已知節點
inline void Delete(int u) {
    swap(val[u], val[len]);
    len--;
    if (val[u << 1] <= val[u]) MoveDown(u);
    else MoveUp(u);
}

//每次對於根進行向下調整，來合併左右兒子代表的兩個堆
//OIwiki上有證明，這種建樹是O(n)的
inline void Build(int _len, const int *a) {
    len = _len;
    memcpy(val + 1, a + 1, sizeof(int) * len);
    //葉子節點不調整，減小常數
    for (int i = (len >> 1) - 1; i; i--) MoveDown(i);
}

int main() {
    int n = Read();
    while (n--) {
        int op = Read();
        if (op == 1) Push(Read());
        else if (op == 2) printf("%d\n", GetTop());
        else Pop();
    }
    return 0;
}

此外，對於這段代碼，我們來仔細討論一下：

inline void Build(int _len, const int *a) {
    len = _len;
    memcpy(val + 1, a + 1, sizeof(int) * len);
    for (int i = (len >> 1) - 1; i; i--) MoveDown(i);
}

這段代碼可以在 \(\mathcal {O}(n)\) 時間內建堆
我們按照節點bfs序倒序向下調整
每當調整到一個節點時
該節點的左右兒子所在子樹已然是二叉堆
這時再把根節點向下調整滿足堆的性質
可視為左右兒子代表的二叉堆的合併

證明：
待補充

可並堆

待補充

其他堆

待補充