跳转至

二叉堆

結構

從二叉堆的結構説起，它是一棵二叉樹，並且是完全二叉樹，每個結點中存有一個元素（或者説，有個權值）。

堆性質：父親的權值不小於兒子的權值（大根堆）。同樣的，我們可以定義小根堆。本文以大根堆為例。

由堆性質，樹根存的是最大值（getmax 操作就解決了）。

過程

插入操作

插入操作是指向二叉堆中插入一個元素，要保證插入後也是一棵完全二叉樹。

最簡單的方法就是，最下一層最右邊的葉子之後插入。

如果最下一層已滿，就新增一層。

插入之後可能會不滿足堆性質？

向上調整：如果這個結點的權值大於它父親的權值，就交換，重複此過程直到不滿足或者到根。

可以證明，插入之後向上調整後，沒有其他結點會不滿足堆性質。

向上調整的時間複雜度是 \(O(\log n)\) 的。

二叉堆的插入操作

刪除操作

刪除操作指刪除堆中最大的元素，即刪除根結點。

但是如果直接刪除，則變成了兩個堆，難以處理。

所以不妨考慮插入操作的逆過程，設法將根結點移到最後一個結點，然後直接刪掉。

然而實際上不好做，我們通常採用的方法是，把根結點和最後一個結點直接交換。

於是直接刪掉（在最後一個結點處的）根結點，但是新的根結點可能不滿足堆性質……

向下調整：在該結點的兒子中，找一個最大的，與該結點交換，重複此過程直到底層。

可以證明，刪除並向下調整後，沒有其他結點不滿足堆性質。

時間複雜度 \(O(\log n)\)。

增加某個點的權值

很顯然，直接修改後，向上調整一次即可，時間複雜度為 \(O(\log n)\)。

實現

我們發現，上面介紹的幾種操作主要依賴於兩個核心：向上調整和向下調整。

考慮使用一個序列 \(h\) 來表示堆。\(h_i\) 的兩個兒子分別是 \(h_{2i}\) 和 \(h_{2i+1}\)，\(1\) 是根結點：

h 的堆結構

參考代碼：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void up(int x) {
  while (x > 1 && h[x] > h[x / 2]) {
    swap(h[x], h[x / 2]);
    x /= 2;
  }
}

void down(int x) {
  while (x * 2 <= n) {
    t = x * 2;
    if (t + 1 <= n && h[t + 1] > h[t]) t++;
    if (h[t] <= h[x]) break;
    std::swap(h[x], h[t]);
    x = t;
  }
}

建堆

考慮這麼一個問題，從一個空的堆開始，插入 \(n\) 個元素，不在乎順序。

直接一個一個插入需要 \(O(n \log n)\) 的時間，有沒有更好的方法？

方法一：使用 decreasekey（即，向上調整）

從根開始，按 BFS 序進行。

1
2
3
void build_heap_1() {
  for (i = 1; i <= n; i++) up(i);
}

為啥這麼做：對於第 \(k\) 層的結點，向上調整的複雜度為 \(O(k)\) 而不是 \(O(\log n)\)。

總複雜度：\(\log 1 + \log 2 + \cdots + \log n = \Theta(n \log n)\)。

（在「基於比較的排序」中證明過）

方法二：使用向下調整

這時換一種思路，從葉子開始，逐個向下調整

1
2
3
void build_heap_2() {
  for (i = n; i >= 1; i--) down(i);
}

換一種理解方法，每次「合併」兩個已經調整好的堆，這説明了正確性。

注意到向下調整的複雜度，為 \(O(\log n - k)\)，另外注意到葉節點無需調整，因此可從序列約 \(n/2\) 的位置開始調整，可減少部分常數但不影響複雜度。

證明
\[ \begin{aligned} \text{總複雜度} & = n \log n - \log 1 - \log 2 - \cdots - \log n \\ & \leq n \log n - 0 \times 2^0 - 1 \times 2^1 -\cdots - (\log n - 1) \times \frac{n}{2} \\\ & = n \log n - (n-1) - (n-2) - (n-4) - \cdots - (n-\frac{n}{2}) \\ & = n \log n - n \log n + 1 + 2 + 4 + \cdots + \frac{n}{2} \\ & = n - 1 \\ & = O(n) \end{aligned} \]

之所以能 \(O(n)\) 建堆，是因為堆性質很弱，二叉堆並不是唯一的。

要是像排序那樣的強條件就難説了。

應用

對頂堆

SPOJ RMID2 - Running Median Again

維護一個序列，支持兩種操作：

  1. 向序列中插入一個元素
  2. 輸出並刪除當前序列的中位數（若序列長度為偶數，則輸出較小的中位數）

這個問題可以被進一步抽象成：動態維護一個序列上第 \(k\) 大的數，\(k\) 值可能會發生變化。

對於此類問題，我們可以使用 對頂堆 這一技巧予以解決（可以避免寫權值線段樹或 BST 帶來的繁瑣）。

對頂堆由一個大根堆與一個小根堆組成，小根堆維護大值即前 \(k\) 大的值（包含第 k 個），大根堆維護小值即比第 \(k\) 大數小的其他數。

這兩個堆構成的數據結構支持以下操作：

  • 維護：當小根堆的大小小於 \(k\) 時，不斷將大根堆堆頂元素取出並插入小根堆，直到小根堆的大小等於 \(k\)；當小根堆的大小大於 \(k\) 時，不斷將小根堆堆頂元素取出並插入大根堆，直到小根堆的大小等於 \(k\)；
  • 插入元素：若插入的元素大於等於小根堆堆頂元素，則將其插入小根堆，否則將其插入大根堆，然後維護對頂堆；
  • 查詢第 \(k\) 大元素：小根堆堆頂元素即為所求；
  • 刪除第 \(k\) 大元素：刪除小根堆堆頂元素，然後維護對頂堆；
  • \(k\) 值 \(+1/-1\)：根據新的 \(k\) 值直接維護對頂堆。

顯然，查詢第 \(k\) 大元素的時間複雜度是 \(O(1)\) 的。由於插入、刪除或調整 \(k\) 值後，小根堆的大小與期望的 \(k\) 值最多相差 \(1\)，故每次維護最多隻需對大根堆與小根堆中的元素進行一次調整，因此，這些操作的時間複雜度都是 \(O(\log n)\) 的。

參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;

int main() {
  int t, x;
  scanf("%d", &t);
  while (t--) {
    // 大根堆，维护前一半元素（存小值）
    priority_queue<int, vector<int>, less<int> > a;
    // 小根堆，维护后一半元素（存大值）
    priority_queue<int, vector<int>, greater<int> > b;
    while (scanf("%d", &x) && x) {
      // 若为查询并删除操作，输出并删除大根堆堆顶元素
      // 因为这题要求输出中位数中较小者（偶数个数字会存在两个中位数候选）
      // 这个和上面的第k大讲解有稍许出入，但如果理解了上面的，这个稍微变通下便可理清
      if (x == -1) {
        printf("%d\n", a.top());
        a.pop();
      }
      // 若为插入操作，根据大根堆堆顶的元素值，选择合适的堆进行插入
      else {
        if (a.empty() || x <= a.top())
          a.push(x);
        else
          b.push(x);
      }
      // 对对顶堆进行调整
      if (a.size() > (a.size() + b.size() + 1) / 2) {
        b.push(a.top());
        a.pop();
      } else if (a.size() < (a.size() + b.size() + 1) / 2) {
        a.push(b.top());
        b.pop();
      }
    }
  }
  return 0;
}

習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：HeRaNO, Xeonacid, AzurIce
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用