标签: pairing-heap

我刚刚实现了配对堆数据结构.配对堆支持插入,查找 - 分钟,合并O(1)摊销时间和删除,删除 - 最小在O(logN)摊销时间.但最显着的操作是reduce-key,它具有复杂度O(log logN).有关配对堆的更多信息,请访问http://en.wikipedia.org/wiki/Pairing_heap.

我已经实现了insert,merge和delete-min操作,但维基百科文章没有说明如何减少给定节点的密钥,所以我无法实现它.有人能告诉我它是如何运作的吗？

这是我的代码:

template< class key_t, class compare_t=std::less< key_t > >
struct pairing_heap {
private:
  struct node { 
    key_t key; std::vector< node* > c;
    node( key_t k=key_t() ) : key( k ), c( std::vector< node* >() ) {}
  };
  node *root;
  compare_t cmp;
  unsigned sz;
public:
  typedef key_t value_type;
  typedef compare_t compare_type;
  typedef pairing_heap< key_t, compare_t > self_type;

  pairing_heap() : root( 0 ) {}
  node* merge( node *x, node *y ) {
    if( …

我正在阅读配对堆.

这很简单,唯一棘手的部分是delete_min操作.

唯一不重要的基本操作是从堆中删除最小元素.标准策略首先从左到右合并子堆(这是赋予此数据结构名称的步骤),然后从右到左合并生成的堆列表:

我不认为我需要在这里复制/粘贴代码,因为它在wiki链接中.

我的问题是

1. 为什么他们这两个合并？

2. 为什么他们首先合并？没有直接合并他们所有？

3. 合并后,为什么从右到左专门合并？