boost 的 heap

学习过 Introduction to Algorithms 的筒子应该对 heap 这个概念有比较明确的认识,前面我们也简单的提了一下 GCC 自己带的一些 heap 实现,这次 boost.heap 又为我们带来了什么?设计上 boost.heap 关注了 heap 本身下面几个特点,

  • mutability,即元素是否会变化;
  • iterators,是否提供 iterator 用来遍历;
  • mergable,我们知道 N-ary heap 的最大缺点就是 merge 的 cost 很高;
  • stability,使用 heap sort 的时候是否保证了 sort 是 stable 的;
  • comparison,两个 heap 是否可以比较(这是个比较奇怪的需求)

我们知道 heap 最直接的应用就是 priority queue,boost.heap 定义了满足 priority queue 这个 concept 应该 typedef 或者定义的函数接口,这基本上和 STL 的容器类似。另外给出了 mergable priority queue 的定义,增加了一个 merge 方法(另外有一个 heap_merge 算法,但是这个对所有 heap 有效,只是有的实现的更有效一些),对 mutable priority queue 给出了定义,增加了 increase/decrease 和 update 几个方法,这样能够修改这些成员的优先级。实现 stability 依赖于一个 boost::heap::stable 的 policy。

boost.heap 提供了以下几种 heap/priority_queue 的实现,

  • priority_queue 和 STL 的类似(但支持后面的一些 template parameter)
  • d_ary_heap 是对 binary heap 的简单推广
  • binomial_heap,支持 merge
  • fibonacci_heap,前面讨论过,原先放在 pending 里面的,现在应该解放了吧
  • pairing_heap,见这里
  • skew_heap,见这里

这些模板类可以用下面的一些类似 boost.parameter 的方式来进行配置,

  • compare 配置优先级比较;
  • allocator 和 STL 的 allocator 一样;
  • stable 是否要求是 stable 的;
  • mutable_ 是否提供 mutable 的接口;
  • stability_counter_type 配置 stable 使用的 counter 类型;
  • constant_time_size 是否记录大小;
  • arity 配置 d_ary_heap 的 d;
  • store_parent_pointer 是否在 skew_heap 中记录 parent 的 pointer;

下面是一个简单的例子,

#include <boost/heap/pairing_heap.hpp>
#include <boost/random.hpp>
#include <iostream>
#include <iomanip>
#include <ctime>

typedef boost::random::uniform_int_distribution<> unif_int ;
typedef boost::random::bernoulli_distribution<> bernoulli ;
typedef boost::heap::pairing_heap<
  int,
  boost::heap::constant_time_size<true>
> HeapType ;

int
main (int, char**) {
  boost::random::mt19937 rng (time (0));
  unif_int u (0, 100) ;
  bernoulli b ;
  HeapType h ;
  int op = 0 ;
  do {
    bernoulli::param_type p (std::min(op/100.0, 1.0)) ;
    b.param (p) ;
    if (b (rng) == 0) { // get on into the queue
      int t = u (rng) ;
      h.push (t) ;
      std::cout << std::setw (3) << op << ": push "
                << t << std::endl ;
    } else {
      std::cout << std::setw (3) << op << ": pop  "
                << h.top () << std::endl ;
      h.pop () ;
    }
    ++ op ;
  } while (h.size () != 0) ;

  return 0 ;
}

——————-
And he said, I will certainly return to you according to the time of life; and, see, Sarah your wife shall have a son. And Sarah heard it in the tent door, which was behind him.

Advertisements
boost 的 heap

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s