一、說明Boost.Heap

Boost.Heap 也可以稱為 Boost.PriorityQueue，因為該庫提供了幾個優先級隊列。但是，Boost.Heap 中的優先級隊列與 std::priority_queue 不同，它支持更多功能。

二、功能示例

示例 17.1。使用 boost::heap::priority_queue

#include <boost/heap/priority_queue.hpp>
#include <iostream>
using namespace boost::heap;
int main()
{
  priority_queue<int> pq;
  pq.push(2);
  pq.push(3);
  pq.push(1);
  for (int i : pq)
    std::cout << i << '\n';
  priority_queue<int> pq2;
  pq2.push(4);
  std::cout << std::boolalpha << (pq > pq2) << '\n';
}

Example17.1

示例 17.1 使用了 boost::heap::priority_queue 類，該類在 boost/heap/priority_queue.hpp 中定義。一般來說，這個類的行為類似于 std::priority_queue，除了它允許你迭代元素。迭代中返回的元素順序是隨機的。

boost::heap::priority_queue 類型的對象可以相互比較。示例 17.1 中的比較返回 true，因為 pq 的元素比 pq2 多。如果兩個隊列具有相同數量的元素，則將成對比較元素。

示例 17.2。使用 boost::heap::binomial_heap

#include <boost/heap/binomial_heap.hpp>
#include <iostream>
using namespace boost::heap;
int main()
{
  binomial_heap<int> bh;
  bh.push(2);
  bh.push(3);
  bh.push(1);
  binomial_heap<int> bh2;
  bh2.push(4);
  bh.merge(bh2);
  for (auto it = bh.ordered_begin(); it != bh.ordered_end(); ++it)
    std::cout << *it << '\n';
  std::cout << std::boolalpha << bh2.empty() << '\n';
}

Example17.2

示例 17.1 使用了 boost::heap::priority_queue 類，該類在 boost/heap/priority_queue.hpp 中定義。一般來說，這個類的行為類似于 std::priority_queue，除了它允許你迭代元素。迭代中返回的元素順序是隨機的。

boost::heap::priority_queue 類型的對象可以相互比較。示例 17.1 中的比較返回 true，因為 pq 的元素比 pq2 多。如果兩個隊列具有相同數量的元素，則將成對比較元素。

示例 17.2。使用 boost::heap::binomial_heap

示例 17.2 引入了類 boost::heap::binomial_heap。除了允許您按優先級順序迭代元素之外，它還允許您合并優先級隊列。一個隊列中的元素可以添加到另一個隊列。

示例在隊列 bh 上調用 merge()。隊列 bh2 作為參數傳遞。對 merge() 的調用將數字 4 從 bh2 移動到 bh。調用后，bh 包含四個數字，bh2 為空。

for 循環在 bh 上調用 ordered_begin() 和 ordered_end()。 ordered_begin() 返回一個從高優先級元素迭代到低優先級元素的迭代器。因此，示例 17.2 將數字 4、3、2 和 1 寫入標準輸出。

示例 17.3。更改 boost::heap::binomial_heap 中的元素

#include <boost/heap/binomial_heap.hpp>
#include <iostream>
using namespace boost::heap;
int main()
{
  binomial_heap<int> bh;
  auto handle = bh.push(2);
  bh.push(3);
  bh.push(1);
  bh.update(handle, 4);
  std::cout << bh.top() << '\n';
}

boost::heap::binomial_heap 允許您在元素添加到隊列后更改它們。示例 17.3 保存了 push() 返回的句柄，從而可以訪問存儲在 bh 中的數字 2。

update() 是 boost::heap::binomial_heap 的成員函數，可以調用它來更改元素。示例 17.3 調用成員函數將 2 替換為 4。然后，使用 top() 獲取具有最高優先級的元素，現在為 4。

除了 update() 之外，boost::heap::binomial_heap 還提供了其他成員函數來更改元素。如果您事先知道更改是否會導致更高或更低的優先級，則可以調用成員函數 increase() 或 decrease()。在示例 17.3 中，對 update() 的調用可以替換為對 increase() 的調用，因為該數字從 2 增加到 4。

Boost.Heap 提供了額外的優先級隊列，其成員函數的主要區別在于它們的運行時復雜度。例如，如果您希望成員函數 push() 具有恒定的運行時復雜度，則可以使用類 boost::heap::fibonacci_heap。 Boost.Heap 上的文檔提供了一個表格，其中概述了各種類和函數的運行時復雜性。