前置知識

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

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

二叉堆

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

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

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

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

為什么這里要與權值較小的一個交換呢？
因為我們要使交換后滿足堆的性質
所以新的父節(jié)點權值應小于它的兩個兒子

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

那么有了這兩個操作我們就可以完成：
插入（新建節(jié)點然后向上調整）
查詢最大（最?。┲担ǜ?jié)點權值）
刪除最大（最?。┲担ㄅc末尾節(jié)點交換，再向下調整）
刪除任意節(jié)點（與末尾交換，再向上或向下調整，見代碼）
修改任意節(jié)點權值（向上或向下調整）

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;
}

//這里我們認為一個節(jié)點的父親是u<<1，左兒子為u>>1，右兒子為u>>1|1
//根為1
//由堆為完全二叉樹的性質可得只需開一倍數組
int val[AwA];
//儲存總節(jié)點數
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);
}

//刪除任意已知節(jié)點
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);
    //葉子節(jié)點不調整，減小常數
    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)\) 時間內建堆
我們按照節(jié)點bfs序倒序向下調整
每當調整到一個節(jié)點時
該節(jié)點的左右兒子所在子樹已然是二叉堆
這時再把根節(jié)點向下調整滿足堆的性質
可視為左右兒子代表的二叉堆的合并

證明：
待補充

可并堆

待補充文章來源地址http://www.zghlxwxcb.cn/news/detail-839335.html

其他堆

待補充

到了這里，關于關于堆的一切的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！