如何将最大堆、堆排序和优先队列应用于长尾词排序？

本文共计3354个文字，预计阅读时间需要14分钟。

基本概念：堆、树、最大堆关于堆和树的描述，堆的本质是一个完全N叉树，以数组作为元素的存储载体。这里需要注意堆内存的概念与堆的概念区分。一个二叉堆的结构如下：

基本概念：堆、树、最大堆 关于堆和树

由《算法导论》的描述，堆的本质是一个完全N叉树，它以数组作为元素的存储载体。这里注意和“堆内存”的概念做区分。

一个二叉堆的结构如下图所示。包括堆的逻辑结构(A)和存储结构(B)：

树通常以指针来构建节点间的连接关系，而堆是利用数组的下标关系来构建树状结构。下标为i的元素，它的左右孩子分别是下标为2*i+1和2*i+2的元素(如果下标从0开始)。这也使得构建出的树是一个完全二叉树。

本文针对它的逻辑结构(完全N叉树)进行研究，对树和堆同样适用。

关于最大堆

如果一个堆的所有节点的值都大于等于其孩子(如果有的话)，则称之为最大堆或大根堆。或者说，如果堆的所有“父子三元组”中父节点都是最大者，则此堆为最大堆。如下图所示：

显然，整个堆的最大值就是其根元素。最小堆的原理类似。

最大堆的相关操作

堆维护了一个元素的集合。一个集合常见的操作包括：“增删改查建”。我们按难易程度分别做表述。