拜托，别再问我什么是堆了!

• 生产中的常见问题
• 堆的定义
• 堆的基本操作
• 堆排序
• 堆在生产中应用

1. 优先级队列的应用场景很广，它是如何实现的呢
2. 如何求 Top K 问题
3. TP99 是生产中的一个非常重要的指标，如何快速计算

堆的定义

1. 堆是一颗完全二叉树，这样实现的堆也被称为二叉堆
2. 堆中节点的值都大于等于（或小于等于）其子节点的值，堆中如果节点的值都大于等于其子节点的值，我们把它称为大顶堆，如果都小于等于其子节点的值，我们将其称为小顶堆。

堆的基本操作

• 往堆中插入元素

public?class?Heap?{
????private?int[]?arr;???????//?堆是完全二叉树，底层用数组存储
????private?int?capacity;????//?堆中能存储的最大元素数量
????private?int?n;??????????//?当前堆中元素数量

????public?Heap(int?count)?{
????????capacity?=?count;
????????arr?=?new?int[capacity+1];
????????n?=?0;
????}

????public?void?insert(int?value)?{
????????if?(n?>=?capacity)?{
????????????//?超过堆大小了，不能再插入元素
????????????return;
????????}
????????n++;
????????//?先将元素插入到队尾中
????????arr[n]?=?value;

????????int?i?=?n;
????????//?由于我们构建的是一个大顶堆，所以需要不断调整以让其满足大顶堆的条件
????????while?(i/2?>?0?&&?arr[i]?>?arr[i/2])?{
????????????swap(arr,?i,?i/2);
????????????i?=?i?/?2;
????????}
????}
}

• 删除堆顶元素

/**
?*?移除堆顶元素
?*/
public?void?removeTopElement()?{
????if?(n?==?0)?{
????????//?堆中如果没有元素，也就是不存在移除堆顶元素的情况了
????????return;
????}
????int?count?=?n;
????arr[1]?=?arr[count];
????--count;
????heapify(1,?count);
}

/**
?*?自上而下堆化以满足大顶堆的条件
?*/
public?void?heapify(int?index,?int?n)?{

????while?(true)?{
????????int?maxValueIndex?=?index;
????????if?(2?*?index?<=?n?&&?arr[index]?<?arr[2?*?index])?{
????????????//?左节点比其父节点大
????????????maxValueIndex?=?2?*?index;
????????}

????????if?(2?*?index?+?1?<=?n?&&?arr[maxValueIndex]?<?arr[2?*?index?+?1])?{
????????????//?右节点比左节点或父节点大
????????????maxValueIndex?=?2?*?index?+?1;
????????}

????????if?(maxValueIndex?==?index)?{
????????????//?说明当前节点值为最大值，无需再往下迭代了
????????????break;
????????}
????????swap(arr,?index,?maxValueIndex);
????????index?=?maxValueIndex;
????}
}

/**
?*?交换数组第?i?和第?j?个元素
?*/
public?static?void?swap(int[]?arr,?int?i,?int?j)
{
????int?temp?=?arr[i];
????arr[i]?=?arr[j];
????arr[j]?=?temp;
}

堆排序

/**
*?对?1?妻?n/2?的非叶子节点自上而下进行堆化，以构建大顶堆
?*/
public?void?buildHeap()?{
????for?(int?i?=?n/2;?i?>?0;?i--)?{
????????heapify(i);
????}
}

/**
?*?堆排序
?*/
public?void?heapsort()?{
????//?建堆
????buildHeap();
????int?i?=?n;
????while?(true)?{
????????if?(i?<=?1)?{
????????????break;
????????}

????????//?将堆顶元素放到第?i?个位置
????????swap(arr,?1,?i);
????????i--;
????????//?重新对?1?到?i?的元素进行堆化，以让其符合大顶堆的条件
????????heapify(1,?i);
????}
}

堆在生产中应用

1. 取 n 个元素的前 K 个元素构建一个小顶堆
2. 遍历第 K + 1 到 ?n 之间的元素，每一个元素都与小顶堆的堆顶元素进行比较，如果小于堆顶元素，不做任何操作，如果大于堆顶元素，则将堆顶元素替换成当前遍历的元素，再堆化以让其满足小顶的要求，这样遍历完成后此小顶堆的所有元素就是我们要求的 TopK。

1. 创建一个大顶堆和一个小顶堆，大顶堆的堆顶元素比小顶堆的堆顶元素更小，大顶堆维护 99% 的请求时间，小顶堆维护 1% 的请求时间
2. 每产生一个元素（请求时间），如果它比大顶堆的堆顶元素小，则将其放入到大顶堆中，如果它比小顶堆的堆顶元素大，则将其插入到小顶堆中，插入后当然要堆化以让其符合大小顶堆的要求。
3. 上一步在插入的过程中需要注意一下，可能会导致大顶堆和小顶堆中元素的比例不为 99:1，此时就要做相应的调整，如果在将元素插入大顶堆之后，发现比例大于 99：1，将需将大顶堆的堆顶元素移到小顶堆中，再对两个堆堆化以让其符合大小顶堆的要求，同理，如果发现比例小于 99: 1，则需要将小顶堆的堆顶元素移到大顶堆来，再对两者进行堆化。

总结

• https://time.geekbang.org/column/article/69913 ?堆和堆排序：为什么说堆排序没有快速排序快？
• https://time.geekbang.org/column/article/70187 ?堆的应用：如何快速获取到Top 10最热门的搜索关键词？
• https://www.jianshu.com/p/6b526aa481b1