一、說(shuō)明Boost.Heap

Boost.Heap 也可以稱為 Boost.PriorityQueue，因?yàn)樵搸?kù)提供了幾個(gè)優(yōu)先級(jí)隊(duì)列。但是，Boost.Heap 中的優(yōu)先級(jí)隊(duì)列與 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 中定義。一般來(lái)說(shuō)，這個(gè)類的行為類似于 std::priority_queue，除了它允許你迭代元素。迭代中返回的元素順序是隨機(jī)的。

boost::heap::priority_queue 類型的對(duì)象可以相互比較。示例 17.1 中的比較返回 true，因?yàn)?pq 的元素比 pq2 多。如果兩個(gè)隊(duì)列具有相同數(shù)量的元素，則將成對(duì)比較元素。

示例 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 中定義。一般來(lái)說(shuō)，這個(gè)類的行為類似于 std::priority_queue，除了它允許你迭代元素。迭代中返回的元素順序是隨機(jī)的。

boost::heap::priority_queue 類型的對(duì)象可以相互比較。示例 17.1 中的比較返回 true，因?yàn)?pq 的元素比 pq2 多。如果兩個(gè)隊(duì)列具有相同數(shù)量的元素，則將成對(duì)比較元素。

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

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

示例在隊(duì)列 bh 上調(diào)用 merge()。隊(duì)列 bh2 作為參數(shù)傳遞。對(duì) merge() 的調(diào)用將數(shù)字 4 從 bh2 移動(dòng)到 bh。調(diào)用后，bh 包含四個(gè)數(shù)字，bh2 為空。

for 循環(huán)在 bh 上調(diào)用 ordered_begin() 和 ordered_end()。 ordered_begin() 返回一個(gè)從高優(yōu)先級(jí)元素迭代到低優(yōu)先級(jí)元素的迭代器。因此，示例 17.2 將數(shù)字 4、3、2 和 1 寫入標(biāo)準(zhǔn)輸出。

示例 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 允許您在元素添加到隊(duì)列后更改它們。示例 17.3 保存了 push() 返回的句柄，從而可以訪問(wèn)存儲(chǔ)在 bh 中的數(shù)字 2。

update() 是 boost::heap::binomial_heap 的成員函數(shù)，可以調(diào)用它來(lái)更改元素。示例 17.3 調(diào)用成員函數(shù)將 2 替換為 4。然后，使用 top() 獲取具有最高優(yōu)先級(jí)的元素，現(xiàn)在為 4。

除了 update() 之外，boost::heap::binomial_heap 還提供了其他成員函數(shù)來(lái)更改元素。如果您事先知道更改是否會(huì)導(dǎo)致更高或更低的優(yōu)先級(jí)，則可以調(diào)用成員函數(shù) increase() 或 decrease()。在示例 17.3 中，對(duì) update() 的調(diào)用可以替換為對(duì) increase() 的調(diào)用，因?yàn)樵摂?shù)字從 2 增加到 4。

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