配对堆与赋级配对堆（Rank Pairing Heaps）

简要介绍

优先队列一直是一种极为有用的数据结构，可以用来排序（heap_sort），可以用于各种算法（Dijkstra 最短路算法，Prim 最小生成树算法，朱刘/Edmond 最小树形图算法等），因此其实现、复杂度和真实世界速度的优化受到了广泛讨论，各种不同实现、不同功能的数据结构不一而足。本文主要介绍一种简单的优秀实现“配对堆”和一种相对较为复杂但更为优秀的“赋级配对堆”（Rank Pairing Heap）。

注：中文翻译未知时多有原创（以斜体表示），不能很好表达原文意思，请多多谅解。

优先队列的功能

在本文中，优先队列指的是可以实现以下操作的数据结构：

new_heap(t:Elem):Heap ，构建一个单元素的优先队列
merge(p:Heap, q:Heap):Heap ，将两个优先队列合并得到一个新的优先队列
insert(p:Heap, t:Elem):Heap 插入
- insert(p, t) = merge(p, new_heap(t))
top(p:Heap):Elem ，返回优先队列中的最小元素
pop(p:Heap):Heap ，删除优先队列中的最小元素
decrease_key(p:Heap, i:Ref Elem, v:Elem):Heap 表示将优先队列 p 中 i 指向的元素替换为更小的 v
delete_key(p:Heap, i:Ref Elem):Heap 表示将优先队列 p 中 i 指向的元素删除。
- depete_key(p, i) = pop(decrease_key(p, i, -inf))

其中有一些操作实现显然（已经给出），故下文不再赘述。复杂度大部分指均摊时间复杂度。

配对堆

所谓的堆是指每个节点对应于一个元素值、且满足堆性质的树。所谓的堆性质是指：这棵树要么为空，要么其根是其最小元素，且每个孩子都满足堆性质。

一个配对堆是一个堆。在理论介绍部分，可以认为它是一棵可以有任意多叉的树。孩子的顺序无关紧要。

理论介绍

new_heap, top, insert, delete_key 实现省略。
merge 的实现如下：拿到两颗配对堆，比较他们的根元素大小。假设 p 的根较小，那么就把 q 添加到 p 的孩子列表中。这个操作可以被称作“配对”，也是配对堆的得名原因。
decrease_key(p, i, v) 实现如下：先直接进行修改。如果这次修改破坏了堆性质，那么就把 i 及其子树 q 从 q.father 里拿出来，然后直接与堆根 p 进行合并。

pop(p) 是配对堆的实现、分析与优化的核心，当前章节剩下的部分都是讲它。首先我们把根节点拿掉，得到一个孩子列表。我们的任务是把它们重新合并成一棵树。

最平凡的想法就是把他们从左到右 merge 起来。这样做正确性没有问题，但很显然其复杂度是 \(O(n)\) 的。

其次平凡的想法是把他们按二叉树的顺序 merge 起来：进行 \(\lceil\log{n}\rceil\) 轮，每轮在剩下的 \(r\) 个中两两合并 \(\lfloor\frac{r}{2}\rfloor\) 次。这个操作被称作 multi-pass merging，复杂度上可以接受（可以分析到所有操作 \(O(\log n)\) ），但是不仅不是最优的，还比较麻烦。（实现上可以拿一个队列，只要大小大于1就不断地弹出队头两个，合并后加到队尾）

比较精妙简洁优雅的做法是 two-pass merging，也就是先把 \(r\) 个子树两两合并成 \(\lceil \frac r2 \rceil\) 个，然后再按从右往左（顺序不要紧）一次性合并起来。或者说，

pop(p) = two_pass_merge(p.sons)
two_pass_merge([]) = null
two_pass_merge([i]) = i
two_pass_merge([i, j, k...]) = merge(merge(i, j), two_pass_merge([k...]))

这样做的复杂度可以分析到 \(O(\log n)\) pop ，\(o(\log n)\) decrease_key ，\(O(1)\) 合并、插入。

具体实现

实现中可以把配对堆实现为一个左儿子右兄弟的树。因为孩子的顺序无关紧要，所以做任何操作都可以找到最近的位置（比如说，合并插入可以插到第一个孩子）。注意到上述操作都易于实现。为了实现 decrease_key ，需要维护父亲/前驱指针。

（代码待补）

复杂度分析

在此我不准备把复杂而冗长的势能函数分析列举出来，只讲讲怎么把 pop 均摊到 \(O(\log n)\) 。

在左儿子右兄弟实现中，一次 pop 相当于把根节点一直往右的链上不断进行了合并相邻的操作。每次走两步、把这两步的节点较大的设置为较小的的左孩子，把较小的的原来的左孩子给较大的当右孩子——如果读者读到这里自己画个图出来，可以发现这玩意像极了 Splay Tree 中的 Zig-zag 操作。因此，可以用 Splay 的势能分析来分析 two-pass 配对堆。众所周知 Splay 是 \(O(\log n)\) 。

想知道更多的可以阅读 arXiv:1110.4428 [cs.DS] 。

Rank Pairing Heap

中译暂无，试译赋级配对堆。

该数据结构可以做到 \(O(\log n)\) pop ，\(O(1)\) 其他操作，也就是 Fibonacci 堆复杂度。实践上比 Fibonacci 堆要优越。

背景介绍

相信大家对二项堆都很熟悉，在此就不对二项堆进行介绍了。不过给出定义如下：

一个级别（Rank）为0的二项树是一个单节点。
一个级别为 \(r>0\) 的二项树是一个根节点与其 \(r\) 个儿子所组成的满足堆性质的树，这些孩子的级别分别为 \(r-1,\,r-2,\cdots,0\) 。

考虑一个级别为 \(r\) 的二项树的左儿子右兄弟表示。可以发现根节点只有左儿子，根节点的左子树是高度为 \(r\) 的满二叉树，且每个 \(i\) 级节点的孩子都是 \(i-1\) 级的。我们把这样的一个结构称作半树（Half-tree）。

一个（原始的）二项堆是由一串级别两两不同的二项树组成的。这一串树由一个循环链表来维护。两个级别相同的二项树可以简单地合并为一个级别 \(+1\) 的二项树，因此（decrease_key 以外的）所有操作的维护很简单。其复杂度的正确保证来源于：每个操作的复杂度皆为 \(O(r)\) ，而一颗级别为 \(r\) 的二项树拥有 \(2^r\) 个结点。

主要过程

首先我们需要让合并、插入变成（最坏、均摊） \(O(1)\) 的。这里我们先把二项堆的在做了什么操作之后都合并一下这个过程去掉，改为“在除了 pop 之外的所有操作，都什么都不管”。在 pop 之后会拆出 \(r\) 颗新树加入那一串半树当中，在这个时候进行一轮配对。一轮配对是指，把所有半树拿出来，对于每个固定的等级（假设等级 \(r\) 有 \(t\) 颗半树），将其两两配对进行合并，得到 \(\lceil\frac t2\rceil\) 颗新的半树，所有等级的所有这些半树放到一起得到新的半树集合。可以证明这样的均摊复杂度是对的。

为了实现 decrease_key 以及优秀的复杂度。RP-Heap 的主要思想是放松（破坏）上述【每个 \(i\) 级节点的孩子都是 \(i-1\) 级的】性质。定义一个 \(k\)-孩子是“和自己的等级差距为 \(k\) 的孩子”。一个 \(i,j\)-节点是有一个 \(i\)-孩子和一个 \(j\)-孩子的节点。

甲类（Type-1）RP-Heap允许存在 1,1-节点以及 0,?-节点，其中 ? 可以是任意正数。注意到，这种情况并不会破坏“一个级别为 \(r\) 的节点或一颗级别为 \(r\) 的半树，至少拥有 \(2^r\) 个结点”这一结论；因此可以保证其复杂度的正确。

可以发现所有其他操作都与“甲类条件”不冲突。因此只考虑 decrease_key 。在一次 decrease_key(p, i, v) 过程中，将 \(i\) 的父亲指针和右孩子指针切掉，将右孩子替代到父亲原来 \(i\) 所处的位置。这一步可能会破坏父亲的甲类条件，因此尝试将父亲的等级向下调整（改小，直到最大可能值）到满足甲类条件。如果父亲的等级改变了，那么不断向上重复这一过程。

同理，有甲类还有乙类（Type-2）RP-Heap，允许 1,1-、1,2-、0,?-节点的存在。注意此时 \(r\) 级树至少拥有 \(\mathrm{Fib}_r\) 个节点。这样能使常数稍微更小一点。

// https://loj.ac/submission/503481
// Type 1 fix rule
unsigned int fixrule(unsigned int u, unsigned int v)
{
  if (u == v) return v + 1;
  return u < v ? v : u;
}
// Type 2 fix rule
unsigned int fixrule_(unsigned int u, unsigned int v)
{
  int dis = u > v ? u - v : v - u;
  if (dis <= 1) return std::max(u, v) + 1;
  return std::max(u, v);
}
template<typename T> struct rp_heap
{
  struct node
  {
    node *l, *r, *f;
    unsigned int rank;
    T val;
  };
  using pnode = node *;
  static pnode new_node(const T &val)
  {
    auto ans = new node{0, 0, 0, 0, val};
    ans->r = ans;
    return ans;
  }
  // Must be "free" pnode's
  static pnode pairing(pnode x, pnode y)
  {
    assert(x->rank == y->rank);
    if (x->val < y->val) {
      std::swap(x, y);
    }
    y->rank++;
    x->r = y->l;
    if (x->r) x->r->f = x;
    y->l = x;
    x->f = y;
    return y;
  }
  static pnode merge(pnode a, pnode b)
  {
    if (b == nullptr) return a;
    if (a == nullptr) return b;
    if (a->val > b->val) {
      std::swap(a, b);
    }
    pnode z = a->r;
    a->r = b->r;
    b->r = z;
    return a;
  }
  static pnode pop(pnode a)
  {
    if (a == nullptr) return a;
    static pnode bucket[233];
    static int prev[100], next[100];
    prev[99] = next[99] = 99;
    pnode output = nullptr;
    // insert single tree, one pass bucketing
    auto work = [&](pnode i) {
      auto r = i->rank;
      if (bucket[r] != nullptr) {
        auto j = bucket[r];
        bucket[r] = nullptr;
        // pair & insert into output list
        i = pairing(i, j);
        i->r = output;
        output = i;
        // lose track of bucket[r]
        prev[next[r]] = prev[r]; next[prev[r]] = next[r];
        prev[r] = next[r] = 99;
      } else {
        // keep track of bucket[r]
        bucket[r] = i;
        prev[r] = 99; next[r] = next[99];
        next[prev[r]] = r; prev[next[r]] = r;
      }
    };
    // put the rest of the list into work()
    for (pnode z = a->r; z != a; ) {
      pnode zz = z->r;
      z->r = nullptr;
      work(z);
      z = zz;
    }
    {
      // put the rest of the first tree into work()
      pnode k = a->l; delete a; a = nullptr;
      for (; k != nullptr; k = a) {
        k->f = nullptr;
        a = k->r;
        k->r = nullptr;
        work(k);
      }
    }
    while (next[99] != 99) {
      int r = next[99];
      bucket[r]->r = output;
      output = bucket[r];
      bucket[r] = nullptr;
      prev[next[r]] = prev[r]; next[prev[r]] = next[r];
      prev[r] = next[r] = 99;
    }
    {
      // the head should be min
      if (output == nullptr) return output;
      auto minimal = output;
      auto i = output;
      for (; ; i = i->r) {
        if (i->val < minimal->val) {
          minimal = i;
        }
        if (i->r == nullptr) break;
      }
      i->r = output;
      return minimal;
    }
  }
  static pnode decrease_key(pnode a, pnode x, const T &nv)
  {
    if (nv >= x->val) return a;
    x->val = nv;
    if (x->f != nullptr) {
      pnode f = x->f; x->f = nullptr;
      if (f->l == x) f->l = x->r;
      else f->r = x->r;
      if (x->r != nullptr) {
        x->r->f = f;
        x->r = nullptr;
      }
      while (true) {
        if (f->f == nullptr) {
          f->rank = (f->l == nullptr) ? 0 : (f->l->rank + 1);
          break;
        }
        auto k = fixrule(f->l != nullptr ? f->l->rank : -1,
          f->r != nullptr ? f->r->rank : -1);
        if (k >= f->rank) break;
        f->rank = k;
        f = f->f;
      }
      x->r = a->r;
      a->r = x;
    }
    if (x->val < a->val) {
      return x;
    } else {
      return a;
    }
  }

  pnode fst;
  rp_heap() : fst(nullptr)
  {
  }
  rp_heap(const T &val) : fst(new_node(val))
  {
  }
  const T &top()
  {
    assert(fst != nullptr);
    return fst->val;
  }
  pnode insert(const T &val)
  {
    auto ans = new_node(val);
    fst = merge(fst, ans);
    return ans;
  }
  bool empty()
  {
    return fst == nullptr;
  }
  void pop()
  {
    fst = pop(fst);
  }
  void decrease_key(pnode p, const T &nv)
  {
    fst = decrease_key(fst, p, nv);
  }
};

EtaoinWu