纸上谈兵: 左倾堆 (leftist heap)

我们之前讲解了堆(heap)的概念。堆是一个优先队列。每次从堆中取出的元素都是堆中优先级最高的元素。

在之前的文章中，我们基于完全二叉树(complete binary tree)实现了堆，这样的堆叫做二叉堆(binary heap)。binary heap有一个基本要求:每个节点的优先级大于两个子节点的优先级。在这一要求下，堆的根节点始终是堆的元素中优先级最高的元素。此外，我们实现了delete_min()操作，从堆中取出元素;insert()操作，向堆中插入元素。

现在，我们考虑下面的问题: 如何合并(merge)两个堆呢? 一个方案是从第一个堆中不断取出一个元素，并插入到第二个堆中。这样，我们需要量级为n的操作。我们下面要实现更有效率的合并。

左倾堆 (Leftist Heap)

左倾堆基于二叉树(binary tree)。左倾堆的节点满足堆的基本要求，即(要求1)每个节点的优先级大于子节点的优先级。与二叉堆不同，左倾堆并不是完全二叉树。二叉堆是非常平衡的树结构，它的每一层都被填满(除了最下面一层)。左倾堆则是维持一种不平衡的结构: 它的左子树节点往往比右子树有更多的节点。