跳转至

堆

__gnu_pbds :: priority_queue

附：官方文檔地址——複雜度及常數測試

1
2
3
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
__gnu_pbds ::priority_queue<T, Compare, Tag, Allocator>

模板形參

  • T: 儲存的元素類型
  • Compare: 提供嚴格的弱序比較類型
  • Tag: 是 __gnu_pbds 提供的不同的五種堆，Tag 參數默認是 pairing_heap_tag 五種分別是：
    • pairing_heap_tag：配對堆 官方文檔認為在非原生元素（如自定義結構體/std :: string/pair）中，配對堆表現最好
    • binary_heap_tag：二叉堆 官方文檔認為在原生元素中二叉堆表現最好，不過筆者測試的表現並沒有那麼好
    • binomial_heap_tag：二項堆 二項堆在合併操作的表現要優於二叉堆，但是其取堆頂元素操作的複雜度比二叉堆高
    • rc_binomial_heap_tag：冗餘計數二項堆
    • thin_heap_tag：除了合併的複雜度都和 Fibonacci 堆一樣的一個 tag
  • Allocator：空間配置器，由於 OI 中很少出現，故這裏不做講解

由於本篇文章只是提供給學習算法競賽的同學們，故對於後四個 tag 只會簡單的介紹複雜度，第一個會介紹成員函數和使用方法。

經作者本機 Core i5 @3.1 GHz On macOS 測試堆的基礎操作，結合 GNU 官方的複雜度測試，Dijkstra 測試，都表明： 至少對於 OIer 來講，除了配對堆的其他四個 tag 都是雞肋，要麼沒用，要麼常數大到不如 std 的，且有可能造成 MLE，故這裏只推薦用默認的配對堆。同樣，配對堆也優於 algorithm 庫中的 make_heap()。

構造方式

要註明命名空間因為和 std 的類名稱重複。

1
2
3
4
5
__gnu_pbds ::priority_queue<int> __gnu_pbds::priority_queue<int, greater<int> >
__gnu_pbds ::priority_queue<int, greater<int>, pairing_heap_tag>
__gnu_pbds ::priority_queue<int>::point_iterator id; // 點類型迭代器
// 在 modify 和 push 的時候都會返回一個 point_iterator，下文會詳細的講使用方法
id = q.push(1);

成員函數

  • push(): 向堆中壓入一個元素，返回該元素位置的迭代器。
  • pop(): 將堆頂元素彈出。
  • top(): 返回堆頂元素。
  • size() 返回元素個數。
  • empty() 返回是否非空。
  • modify(point_iterator, const key): 把迭代器位置的 key 修改為傳入的 key，並對底層儲存結構進行排序。
  • erase(point_iterator): 把迭代器位置的鍵值從堆中擦除。
  • join(__gnu_pbds :: priority_queue &other): 把 other 合併到 *this 並把 other 清空。

使用的 tag 決定了每個操作的時間複雜度：

push pop modify erase Join
pairing_heap_tag \(O(1)\) 最壞 \(\Theta(n)\) 均攤 \(\Theta(\log(n))\) 最壞 \(\Theta(n)\) 均攤 \(\Theta(\log(n))\) 最壞 \(\Theta(n)\) 均攤 \(\Theta(\log(n))\) \(O(1)\)
binary_heap_tag 最壞 \(\Theta(n)\) 均攤 \(\Theta(\log(n))\) 最壞 \(\Theta(n)\) 均攤 \(\Theta(\log(n))\) \(\Theta(n)\) \(\Theta(n)\) \(\Theta(n)\)
binomial_heap_tag 最壞 \(\Theta(\log(n))\) 均攤 \(O(1)\) \(\Theta(\log(n))\) \(\Theta(\log(n))\) \(\Theta(\log(n))\) \(\Theta(\log(n))\)
rc_binomial_heap_tag \(O(1)\) \(\Theta(\log(n))\) \(\Theta(\log(n))\) \(\Theta(\log(n))\) \(\Theta(\log(n))\)
thin_heap_tag \(O(1)\) 最壞 \(\Theta(n)\) 均攤 \(\Theta(\log(n))\) 最壞 \(\Theta(\log(n))\) 均攤 \(O(1)\) 最壞 \(\Theta(n)\) 均攤 \(\Theta(\log(n))\) \(\Theta(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
#include <algorithm>
#include <cstdio>
#include <ext/pb_ds/priority_queue.hpp>
#include <iostream>
using namespace __gnu_pbds;
// 由於面向OIer, 本文以常用堆 : pairing_heap_tag作為範例
// 為了更好的閲讀體驗，定義宏如下 ：
#define pair_heap __gnu_pbds ::priority_queue<int>
pair_heap q1;  // 大根堆, 配對堆
pair_heap q2;
pair_heap ::point_iterator id;  // 一個迭代器

int main() {
  id = q1.push(1);
  // 堆中元素 ： [1];
  for (int i = 2; i <= 5; i++) q1.push(i);
  // 堆中元素 :  [1, 2, 3, 4, 5];
  std ::cout << q1.top() << std ::endl;
  // 輸出結果 : 5;
  q1.pop();
  // 堆中元素 : [1, 2, 3, 4];
  id = q1.push(10);
  // 堆中元素 : [1, 2, 3, 4, 10];
  q1.modify(id, 1);
  // 堆中元素 :  [1, 1, 2, 3, 4];
  std ::cout << q1.top() << std ::endl;
  // 輸出結果 : 4;
  q1.pop();
  // 堆中元素 : [1, 1, 2, 3];
  id = q1.push(7);
  // 堆中元素 : [1, 1, 2, 3, 7];
  q1.erase(id);
  // 堆中元素 : [1, 1, 2, 3];
  q2.push(1), q2.push(3), q2.push(5);
  // q1中元素 : [1, 1, 2, 3], q2中元素 : [1, 3, 5];
  q2.join(q1);
  // q1中無元素，q2中元素 ：[1, 1, 1, 2, 3, 3, 5];
}

__gnu_pbds 迭代器的失效保證（invalidation_guarantee）

在上述示例以及一些實踐中（如使用本章的 pb-ds 堆來編寫單源最短路等算法），常常需要保存並使用堆的迭代器（如 __gnu_pbds::priority_queue<int>::point_iterator 等）。

可是例如對於 __gnu_pbds::priority_queue 中不同的 Tag 參數，其底層實現並不相同，迭代器的失效條件也不一樣，根據__gnu_pbds 庫的設計，以下三種由上至下派生的情況：

  1. 基本失效保證（basic_invalidation_guarantee）：即不修改容器時，點類型迭代器（point_iterator）、指針和引用（key/value）保持 有效。

  2. 點失效保證（point_invalidation_guarantee）：即 修改 容器後，點類型迭代器（point_iterator）、指針和引用（key/value）只要對應在容器中沒被刪除 保持 有效。

  3. 範圍失效保證（range_invalidation_guarantee）：即 修改 容器後，除（2）的特性以外，任何範圍類型的迭代器（包括 begin() 和 end() 的返回值）是正確的，具有範圍失效保證的 Tag 有 rb_tree_tag 和 適用於 __gnu_pbds::tree 的 splay_tree_tag，以及 適用於 __gnu_pbds::trie 的 pat_trie_tag。

從運行下述代碼中看出，除了 binary_heap_tag 為 basic_invalidation_guarantee 在修改後迭代器會失效，其餘的均為 point_invalidation_guarantee 可以實現修改後點類型迭代器 (point_iterator) 不失效的需求。

 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
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
#include <cxxabi.h>

template <typename T>
void print_invalidation_guarantee() {
  typedef typename __gnu_pbds::container_traits<T>::invalidation_guarantee gute;
  cout << abi::__cxa_demangle(typeid(gute).name(), 0, 0, 0) << endl;
}

int main() {
  typedef
      typename __gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag>
          pairing;
  typedef
      typename __gnu_pbds::priority_queue<int, greater<int>, binary_heap_tag>
          binary;
  typedef
      typename __gnu_pbds::priority_queue<int, greater<int>, binomial_heap_tag>
          binomial;
  typedef typename __gnu_pbds::priority_queue<int, greater<int>,
                                              rc_binomial_heap_tag>
      rc_binomial;
  typedef typename __gnu_pbds::priority_queue<int, greater<int>, thin_heap_tag>
      thin;
  print_invalidation_guarantee<pairing>();
  print_invalidation_guarantee<binary>();
  print_invalidation_guarantee<binomial>();
  print_invalidation_guarantee<rc_binomial>();
  print_invalidation_guarantee<thin>();
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Xeonacid, ouuan, Ir1d, WAAutoMaton, Chrogeek, abc1763613206, Planet6174, i-Yirannn, opsiff, GoodCoder666
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用