undefined

堆

1. 堆是一个完全二叉树
2. 堆中每个节点的值都必须大于等于（或者小于等于）其子树中每个节点的值

• 往堆中插入元素：从下往上的堆化方法。O(logn) 的时间复杂度

  public class Heap {
    private int[] a; // 数组，从下标1开始存储数据
    private int n;  // 堆可以存储的最大数据个数
    private int count; // 堆中已经存储的数据个数
  
    public Heap(int capacity) {
      a = new int[capacity + 1];
      n = capacity;
      count = 0;
    }
  
    public void insert(int data) {
      if (count >= n) return; // 堆满了
      ++count;
      a[count] = data;
      int i = count;
      while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化
        swap(a, i, i/2); // swap()函数作用：交换下标为i和i/2的两个元素
        i = i/2;
      }
    }
   }

• 删除堆顶元素：我们把最后一个节点放到堆顶，然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。这就是从上往下的堆化方法。O(logn) 的时间复杂度

  public void removeMax() {
    if (count == 0) return -1; // 堆中没有数据
    a[1] = a[count];
    --count;
    heapify(a, count, 1);
  }
  
  private void heapify(int[] a, int n, int i) { // 自上往下堆化
    while (true) {
      int maxPos = i;
      if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
      if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
      if (maxPos == i) break;
      swap(a, i, maxPos);
      i = maxPos;
    }
  }

基于堆实现排序

主要是建堆和排序。

• 建堆：从后往前处理数组，并且每个数据都是从上往下堆化。建堆过程的时间复杂度是 O(n)

private static void buildHeap(int[] a, int n) {
  for (int i = n/2; i >= 1; --i) {
    heapify(a, n, i);
  }
}

private static void heapify(int[] a, int n, int i) {
  while (true) {
    int maxPos = i;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}

我们对下标从 2n 开始到 1 的数据进行堆化，下标是 2n+1 到 n 的节点是叶子节点，我们不需要堆化。实际上，对于完全二叉树来说，下标从 2n+1 到 n 的节点都是叶子节点。

• 排序：数组中的第一个元素就是堆顶，也就是最大的元素。我们把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置。将剩下的 n−1 个元素重新构建成堆，依次类推即可

  // n表示数据的个数，数组a中的数据从下标1到n的位置。
  public static void sort(int[] a, int n) {
    buildHeap(a, n);
    int k = n;
    while (k > 1) {
      swap(a, 1, k);
      --k;
      heapify(a, k, 1);
    }
  }

二、快速排序为什么比堆排序效率高

1. 堆排序数据访问的方式没有快速排序友好，没有利用到 CPU 的缓存
2. 对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。因为堆排序的第一步是建堆，建堆的过程会打乱数据原有的相对先后顺序，导致原数据的有序度降低。比如，对于一组已经有序的数据来说，经过建堆之后，数据反而变得更无序了。

三、应用

1. 优先级队列

往优先级队列中插入元素，相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，相当于取出堆顶元素

• 合并有序小文件：假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件？

  我们将从小文件中取出来的字符串放入到小顶堆中，那堆顶的元素，也就是优先级队列队首的元素，就是最小的字符串。我们将这个字符串放入到大文件中，并将其从堆中删除。然后再从小文件中取出下一个字符串，放入到堆中。循环这个过程，就可以将 100 个小文件中的数据依次放入到大文件中。

  删除堆顶数据和往堆中插入数据的时间复杂度都是 O(logn)，n 表示堆中的数据个数

• 高性能定时器

  我们按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（也就是小顶堆的堆顶）存储的是最先执行的任务。

  这样，定时器就不需要每隔 1 秒就扫描一遍任务列表了。它拿队首任务的执行时间点，与当前时间点相减，得到一个时间间隔 T。这个时间间隔 T 就是，从当前时间开始，需要等待多久，才会有第一个任务需要被执行。这样，定时器就可以设定在 T 秒之后，再来执行任务。从当前时间点到（T-1）秒这段时间里，定时器都不需要做任何事情。当 T 秒时间过去之后，定时器取优先级队列中队首的任务执行。然后再计算新的队首任务的执行时间点与当前时间点的差值，把这个值作为定时器执行下一个任务需要等待的时间。这样就可以不能轮询也不用遍历

2. 利用堆求 TopK

• 对于静态数据，如何在一个包含 n 个数据的数组中，查找前 K 大数据呢？我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。
• 对于动态数据，我们可以一直都维护一个 K 大小的小顶堆，当有数据被添加到集合中时，我们就拿它与堆顶的元素对比。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理。这样，无论任何时候需要查询当前的前 K 大数据，我们都可以立刻返回给他。

3. 利用堆求中位数

• 静态数据：我们需要维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。也就是说，如果有 n 个数据，n 是偶数，我们从小到大排序，那前 n/2 个数据存储在大顶堆中，后 n/2 个数据存储在小顶堆中。这样，大顶堆中的堆顶元素就是我们要找的中位数。如果 n 是奇数，情况是类似的，大顶堆就存储 n/2+1 个数据，小顶堆中就存储 n/2 个数据。

• 动态数据，如果新加入的数据小于等于大顶堆的堆顶元素，我们就将这个新数据插入到大顶堆；否则，我们就将这个新数据插入到小顶堆。因为小顶堆的数据都大于大顶堆中的数据。这个时候，有可能出现两个堆中数据不符合前面约定的情况，我们可以从一个堆中不停的将堆顶元素移动到另一个堆。插入操作涉及堆化，时间复杂度为 O(logn)，求中位数为 O(1)

扩展：中位数会求，那么 99 分位的数也是一样的道理

四、问题

假设现在我们有一个包含 10 亿个搜索关键词的日志文件，如何快速获取到 Top 10 最热门的搜索关键词呢？

使用哈希算法，将10亿个关键词的日志文件，不同的关键词 hash 分到 10 个文件中，保证相同的关键词在同一个文件中。然后在这10个文件中使用哈希表、平衡树或者其他一些快速查找、插入的数据结构，来记录关键词及其出现的次数。然后利用小顶堆，遍历哈希表，求出 TopK。然后把这个 10 个 TopK 放在一块，然后取这 10K 个关键词中，出现次数最多的 10 个关键词，这就是这 10 亿数据中的 Top 10 最频繁的搜索关键词了。