C++ Boost Heap使用实例详解

一、说明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 上的文档提供了一个表格，其中概述了各种类和函数的运行时复杂性。