第三章 - 优先队列（堆）

约 563 个字 预计阅读时间 2 分钟

在数据结构基础 - 第四章 - 优先队列（堆）中，我们已经较为详细地讨论了「堆」这一数据结构。

但是我们也留下了一个问题，即一般的堆是难以合并的。以二叉堆为例，一个可行的合并方式是先将两个堆的数组拼接，然后采用线性建堆的方式，即从树的倒数第二层开始，对每一层的每一个节点执行下滤操作完成合并。容易直到这样操作的复杂度是线性的，这不够高效。

为了解决这个问题，我们将介绍几种高级的堆数据结构，来解决这一问题。

左式堆

左式堆 (leftist heap) 也是满足堆序性的二叉树。但是相较一般的二叉堆，左式堆不仅不趋向理想平衡 (perfectly balanced)，而且实际上的趋向于非常不平衡的。在具体构建这一数据结构前，我们需要引入一些概念。

左式堆的性质

我们将任意节点 \(X\) 的零路径长 (Null Path Length, NPL) \(\texttt{Npl} (X)\) 定义为从 \(X\) 到一个没有两个子节点的节点的最短路径长。

因此，具有 0 个或 1 个子节点的节点的 \(\texttt{Npl}\) 为 \(0\)，\(\texttt{Npl}(\texttt{NULL}) = -1\)。同时一个重要的性质是，任意节点的零路径长比其所有子节点的零路径长的最小值多 \(1\)。

左式堆的性质是：对于堆中的每一个节点 \(X\)，左子节点的零路径长不小于右子节点的零路径长。显然这一性质会使得树偏向于向左增加深度，这也是其得名的由来。

进一步地，在右路径上有 \(r\) 个节点的左式树必然至少有 \(2^{r} - 1\) 个节点。换言之，有 \(N\) 个节点的左式树有一条有路径最多含有 \(\lceil \log (N + 1) \rceil\) 个节点。因此对左式堆操作的一般思路是将所有工作放到有路径上进行。于是我们关注的是，如何在对右路径进行插入和合并操作后回复左式堆的性质。