可合并堆之左偏树的简介与应用

2020-05-13  本文已影响0人  LittleMagic

前言

在之前的这篇文章里，笔者详细讲解了二叉堆这种简单有效的数据结构，并且讨论了优先队列的实现方式。现在有个新的问题：

给定两个优先队列，请尽量高效地将它们合并成一个优先队列。

很显然，如果我们使用二叉堆实现，只能先出队再入队，而线性复杂度显然不能令人满意。所以我们需要考虑可合并堆（mergeable heap），常见的可合并堆有如下四种：

其中前两者可以实现O(logn)的合并，而后两者更是可以达到O(1)。限于篇幅，本文只讨论左偏树，因为它是可合并堆中最简单的一种，容易编码实现，“性价比”比较高，应用也较广泛。

左偏树

定义与性质

顾名思义，左偏树就是一棵往左偏的树（废话

左偏树是一棵二叉树，但是它的每个节点上除了记录键值之外，还会记录距离值（dist值，又称npl或者s-value）。所谓距离值，就是指树中某个节点与其距离最近的外节点之间的路径长度。而外节点（external node）就是那些没有子节点或者只有1个子节点的节点，特别地，规定外节点的距离值为0，而NULL节点的距离值为-1。

下图来自百度百科，是一个用左偏树表示的最小堆，蓝色数字就是距离值。

以下都以最小堆为例，左偏树具有以下两个性质：

  • 堆性质：每个节点存储的值都小于或等于其子节点存储的值。
  • 左偏性质：每个节点的左子节点的距离值总是不小于右子节点的距离值。

看官可以再观察一下上面的图，以方便理解这两个性质。可见，左偏树的子树也都是左偏树。

注意：左偏树并不一定像二叉堆那样是一棵完全二叉树。并且判断左偏的标准是距离值，所以左子树的深度或者节点数未必大于右子树。

根据左偏性质和距离值的定义，容易得出推论：

左偏树中一个节点的距离值等于它的右子节点距离值加上1。

另外再根据二叉树的性质，容易得出以下推论：

如果一棵左偏树根节点的距离值为d，那么该左偏树最少可以有2d+1-1个节点，此时它才是完全二叉树。
换言之，一棵有n个节点的左偏树，其根节点的距离值最大为⌊log(n+1)⌋-1。

接下来具体看看左偏树最重要的合并操作的流程。

合并操作

合并两棵左偏树A和B之前，先检查它们两个的根节点的值，较小的那个作为合并结果树的根节点。现假设A的根节点较小，那么我们把A的左子树放置不动，把A的右子树递归地与B进行合并。递归返回时，需要更新结果树的根节点距离值。另外，如果结果树不满足左偏性质，就将其左右子树交换，以使其再度满足左偏性质。简单的示意图如下所示。

上图可能不太直观，接下来举一个更实际一些的例子。

由此可见，左偏性质使得我们每次都可以只在右子树上进行合并操作。最后用伪码来表达其流程如下。

function merge(a, b) {
  if (a == null) 
    return b;
  if (b == null) 
    return a;
  if (a.val > b.val)
    swap(a, b);

  a.right = merge(a.right, b);
  
  if (a.left.dist < a.right.dist)
    swap(a.left, a.right);

  if (a.right == null)
    a.dist = 0;
  else
    a.dist = a.right.dist + 1;

  return a;
}

整个合并操作的实现是很简洁的。根据上一节的推论，可以得出合并操作的最坏时间复杂度为O(log|A|+log|B|)。

插入&构造操作

有了合并操作做基础，插入操作实际上就是合并一棵已有的左偏树和一棵单节点的左偏树，即：

function insert(a, x) {
  b = make_leftist_tree(x);
  return merge(a, b);
}

显然，如果我们用插入操作从零开始构造n个节点的左偏树，时间复杂度为O(nlogn)。一种优化方法是采用普通的FIFO队列来辅助构造，每次从队头取出两棵左偏树合并后放入队尾，直到队列中只剩一棵树为止，可以达到O(n)。

取堆顶操作

取堆顶也就是弹出左偏树中的最小元素。将其根节点移除后，剩下的两棵左右子树也都是左偏树，再把它们合并到一起就OK了。

function pop(a) {
  v = a.val;
  a = merge(a.left, a.right);
  return v;
}

说了这么多，看一道简单的例题吧。

例题：HDOJ 1512

传送门在这里。

题目大意：有N只猴子，每只猴子起初互相都不认识。猴子之间经常发生冲突，每次会有两只猴子（a和b）约架，并且a和b各自会邀请自己的朋友中战斗力最强的那只（包括它自己）上场。每打完一场后，上场的两只猴子战斗力减半，并且它们和它们的朋友都会互相成为朋友，成为朋友的猴子就不会再约架。输入猴子总数、战斗力值和每次约架的猴子编号，要求输出每次打完后最高的战斗力值。

显然，判断是否为朋友可以用并查集实现（之前已经讲过），找最大值可以用最大堆实现。但是并查集每次合并之后，堆也要随着更新，普通二叉堆自然是不行的，左偏树就是解决这种问题的利器了。

直接放出AC代码如下。注意并查集的合并和左偏树的合并逻辑一起放在了merge()方法中。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100002;

struct LTNode {
  int left, right, dist, str;
}ltree[MAXN];

int parent[MAXN];
int n, m, a, b;

int find(int x) {
  int r = x;
  while (parent[r] != r) {
    r = parent[r];
  }
  int p = parent[x];
  while (p != r) {
    parent[x] = r;
    x = p;
    p = parent[x];
  }
  return r;
}

int merge(int x, int y) {
  if (x == 0) {
    return y;
  }
  if (y == 0) {
    return x;
  }
  if (ltree[x].str < ltree[y].str) {
    swap(x, y);
  }
  ltree[x].right = merge(ltree[x].right, y);
  parent[ltree[x].right] = x;
  if (ltree[ltree[x].left].dist < ltree[ltree[x].right].dist) {
    swap(ltree[x].left, ltree[x].right);
  }
  ltree[x].dist = ltree[x].right == 0 ? 0 : ltree[ltree[x].right].dist + 1;
  return x;
} 

int pop(int x) {
  int l = ltree[x].left, r = ltree[x].right;
  parent[l] = l;
  parent[r] = r;
  ltree[x].left = ltree[x].right = ltree[x].dist = 0;
  return merge(l, r);
}

int main() {
  while (~scanf("%d", &n)) {
    memset(ltree, 0, sizeof(ltree));
    for (int i = 1; i <= n; i++) {
      scanf("%d", &ltree[i].str);
      parent[i] = i;
    }
    scanf("%d", &m);
    while (m--) {
      scanf("%d%d", &a, &b);
      int ra = find(a), rb = find(b);
      if (ra == rb) {
        printf("-1\n");
        continue;
      } else {
        int pa = pop(ra), pb = pop(rb);
        ltree[ra].str /= 2;
        ltree[rb].str /= 2;
        pa = merge(pa, ra);
        pb = merge(pb, rb);
        printf("%d\n", ltree[merge(pa, pb)].str);
      }
    }
  }
  return 0;
}

民那晚安。

上一篇下一篇

猜你喜欢

热点阅读