1 优先级队列

优先级队列作为一类独特数据结构的意义恰恰在于，通过转而维护词条集的一个偏序关系。如此， 不仅依然可以支持对最高优先级词条的动态访问，而且可将相应的计算成本控制在足以令人满意的范围之内。

2 堆

2.1 完全二叉堆

首先，其逻辑结构须等同于完全二叉树，此即所谓的“结构性”。
其次，就优先级而言，堆顶以外的每个节点都不高（大）于其父节点，此即所谓的“堆序性” 。

3 左式堆

其基本思路是：在保持堆序性的前提下附加新的条件，使得在堆的合并过程中，只需调整很少量的节点。
左式堆的整体结构呈单侧倾斜状； 依照惯例， 其中节点的分布均偏向左侧。 也就是说，左式堆将不再如完全二叉堆那样满足结构性。
image.png

3.1 空节点路径长度

npl(x)既等于x到外部节点的最近距离（该指标由此得名），同时也等于以x为根的最大满子树（图中以矩形框出） 的高度。
image.png

3.2 左倾性与左式堆

左式堆是处处满足“左倾性” 的二叉堆，即任一内部节点x都满足npl(lc(x)) >= npl(rc(x))。就npl指标而言，任一内部节点的左孩子都不小于其右孩子。
左式堆中任一内节点x都应满足:npl(x) = 1 + npl(rc(x))。也就是说，左式堆中每个节点的npl值， 仅取决于其右孩子。

3.3 合并算法

image.png