堆及其应用

理解堆

堆，言简意赅，是一种数据结构，它是一种特殊的树，满足以下两点：

1：堆是一钟完全二叉树；

2：堆中的每一个非叶子节点都必须满足大于等于（或小于等于）它的左右子树节点。

下面来解析一下上面两点：

第一点，堆是一个完全二叉树，即堆，除了最下面一层，其他层都要是满的，最后一层的节点要靠左排列。

第二点，堆中的每一个节点的值都要大于等于或小于等于其左右子节点的值。

堆分为“大顶堆”和“小顶堆”两种。

大顶堆：父节点大于等于其左右子节点；

小顶堆：父节点小于等于其左右子节点。

判断一下哪些不是堆

上图有四个树，可以判断一下，哪些不是堆。

正确的是，4不是堆。1与2是大顶堆，3是小顶堆。

实现一个堆

那么，该怎么实现一个堆呢。我们可以借助数组这种数据结构来实现。为什么呢，首先堆是一种完全二叉树，当我们使用数组来实现时，我们不需要保存左右指针，仅仅通过数组下标就能实现堆父节点或者左右子节点的查找。为什么这么说呢，我们可以看看下面一个图。

实现堆

上图，表现了一个堆和数组的对应关系。使用数组时，我们舍弃第一个存储单元，在下标为1的位置来存储堆顶元素，这样，节点 i 的左儿子节点就是下标为 2i 处的元素，父节点 i 的右儿子节点就是下标为 (2i+1)处的元素，父节点就是数组下标（i/2）处的元素。

因为数组的查询是特别快的，只要常数级，所以我们使用数组来存储堆，实现堆。

在看堆的实现之前，我们先考虑一下，堆这种数据结构有哪些重要的操作。首当其冲的肯定是插入操作，其次是删除操作，这是两个最为重要的操作，为什么这样说，因为不管是插入还是删除，都会对堆的结构造成影响，有可能就破坏了堆，所以在实现这两个操作的时候，我们还必须保证堆性的完整性。

1：插入数据

往堆中插入数据，也必须要保证堆的两种特性，下面看看这个图，插入操作：

堆化

上图是往一个堆中插入一个数据22。

堆化，可以自顶向下，有可以自下向上，我习惯于自下向上，叫做上滤操作，可以看到，上图的堆是一个大顶堆，我们将要插入的数据放到数组0处，然后和要插入的位置的父节点比较，如果比它大，就和他交换，继续和父节点比较，直到满足堆性。综合来看，往堆中插入数据，其实就是一个数组的比较交换的操作。

下面我给出我的代码：

// 插入数据 要保持堆的结构性质和堆序性质

public void insert(AnyType item) {

if (currentSize ==array.length -1) {

ensureCapacity(array.length *2 +1);  // 进行扩容操作

}

int hole =currentSize++;  // 获得要插入数据的数组下标

for (array[0] = item;array[hole /2].compareTo(item) >0; hole = hole /2) {

array[hole] =array[hole /2];

}

array[hole] = item;

}

其实就是一个比较交换的过程。

2：删除数据

对于堆的删除操作，我们都是删除其堆顶元素，那么为了保持堆性的完整，我们就需要对最后一个元素进行操作。因为删除了堆顶元素，堆顶就空了，我们将最后一个元素放到堆顶，然后对它进行下滤。

不做过多说明，看一看代码：

//删除根，从根的子节点选一个替代，

public AnyType deleteMin()throws Exception {

  if (isEmpty())

    throw new Exception();

  AnyType item =array[1];

  array[1] =array[currentSize -1];

  this.percolateDown(1);

  return item;

}

// 下滤操作  可以考虑递归

private void percolateDown(int hole) {

    AnyType temp =array[hole];

    int child;

   for (; hole * 2 < currentSize; hole = child) {

      child = hole *2;

     if (array[child].compareTo(array[child +1]) >0) {

         child++;

      }

    if (array[hole].compareTo(array[child]) >0) {

       array[hole] =array[child];

    }else {

   break;

  }

}

   array[hole] = temp;

}

上述就是对堆进行删除操作，可以看到，其中有一部分，是判断左右子节点哪一个更大，这个要注意。

3：建堆

最后就是一个建堆操作

public void buildHeap() {

for (int i =currentSize /2; i >0; i--) {//从中间开始下滤

        percolateDown(i);

}

}

这就是一个针对数据进行下滤的一个操作，只不过我们从最后一个非叶子节点开始，向上的一个个进行下滤。

明白了堆的一些操作，我们就来看看堆的一些具体应用：

堆的应用一：优先级队列

1. 合并有序小文件

2. 高性能定时器

堆的应用二：利用堆求 Top K

堆的应用三：利用堆求中位数

最后给出一个比较厉害的应用场景。

如何快速获取到 Top 10 最热门的搜索关键词呢？

处理这个问题，有很多高级的解决方法，比如使用 MapReduce 等。但是，如果我们将处理的场景限定为单机，可以使用的内存为 1GB。那这个问题该如何解决呢？因为用户搜索的关键词，有很多可能都是重复的，所以我们首先要统计每个搜索关键词出现的频率。我们可以通过散列表、平衡二叉查找树或者其他一些支持快速查找、插入的数据结构，来记录关键词及其出现的次数。

假设我们选用散列表。我们就顺序扫描这 10 亿个搜索关键词。当扫描到某个关键词时，我们去散列表中查询。如果存在，我们就将对应的次数加一；如果不存在，我们就将它插入到散列表，并记录次数为 1。以此类推，等遍历完这 10 亿个搜索关键词之后，散列表中就存储了不重复的搜索关键词以及出现的次数。

然后，我们再根据前面讲的用堆求 Top K 的方法，建立一个大小为 10 的小顶堆，遍历散列表，依次取出每个搜索关键词及对应出现的次数，然后与堆顶的搜索关键词对比。如果出现次数比堆顶搜索关键词的次数多，那就删除堆顶的关键词，将这个出现次数更多的关键词加入到堆中。以此类推，当遍历完整个散列表中的搜索关键词之后，堆中的搜索关键词就是出现次数最多的 Top 10 搜索关键词了。

不知道你发现了没有，上面的解决思路其实存在漏洞。10 亿的关键词还是很多的。我们假设 10 亿条搜索关键词中不重复的有 1 亿条，如果每个搜索关键词的平均长度是 50 个字节，那存储 1 亿个关键词起码需要 5GB 的内存空间，而散列表因为要避免频繁冲突，不会选择太大的装载因子，所以消耗的内存空间就更多了。而我们的机器只有 1GB 的可用内存空间，所以我们无法一次性将所有的搜索关键词加入到内存中。这个时候该怎么办呢？

我们在哈希算法那一节讲过，相同数据经过哈希算法得到的哈希值是一样的。我们可以根据哈希算法的这个特点，将 10 亿条搜索关键词先通过哈希算法分片到 10 个文件中。

具体可以这样做：我们创建 10 个空文件 00，01，02，……，09。我们遍历这 10 亿个关键词，并且通过某个哈希算法对其求哈希值，然后哈希值同 10 取模，得到的结果就是这个搜索关键词应该被分到的文件编号。

对这 10 亿个关键词分片之后，每个文件都只有 1 亿的关键词，去除掉重复的，可能就只有 1000 万个，每个关键词平均 50 个字节， 所以总的大小就是 500MB。1GB 的内存完全可以放得下。

我们针对每个包含 1 亿条搜索关键词的文件，利用散列表和堆，分别求出 Top 10，然后把这个 10 个 Top 10 放在一块，然后取这 100 个关键词中，出现次数最多的 10 个关键词，这就是这 10 亿数据中的 Top 10 最频繁的搜索关键词了。