✅什么是堆？什么情况下要用堆？

典型回答

这里的堆是指数据结构中的堆，和操作系统内存的堆没有半毛钱关系！

堆一般是一个完全二叉树，所谓的完全二叉树就是指除了叶子节点外，其他节点都是满二叉树，也就是其他节点都是既有左节点，又有右节点的，完全二叉树如下所示：

堆是一种特殊的完全二叉树，一般分为大顶堆（大根堆）和小顶堆（小根堆）。所谓的大根堆，就是指任意节点都大于它所有的子节点，而小根堆则恰恰相反，指的是任意节点都小于它所有的子节点。如下图是一个大根堆所示：

这样的性质有什么作用呢？当我们维护好一个堆之后，我们可以很容易的找到一个集合的最大值或者前K大的值，进一步思考，我们可以通过堆来实现优先队列，毕竟堆中每个元素都是权重的。Java中的优先队列PriorityQueue就是通过堆实现的。

同时，因为堆是可以动态构建的，在一些有动态数据且需要排序的场景下，堆的速度要比快排的速度快很多。譬如，TP99问题就可以通过堆来快速解决。

实现

堆可以用数组或者链表实现，对于数组来说，因为堆一定是一个完全二叉树，所以堆中的每个元素一定会满足以下规律：

• 设当前节点的 cur[index] = x,
• 那么 parent[index] = (x-1)/2,
• 左孩子 left[index] = 2*x + 1,
• 右孩子 right[index] = 2*x + 2

具体的堆化思路和实现可可以参考：https://www.jianshu.com/p/add3aa138f12

知识扩展

什么是TP99问题，如何快速计算？

所谓的TP99，指的是在一个时间段内，统计某个接口（或方法）每次调用所消耗的时间，并将这些时间按从小到大的顺序进行排序，取第99%的那个值作为TP99值。

举个例子， 假设某个方法在5分钟内调用消耗时间的TP99为10ms，那么就说明该接口5分钟内前99%的调用时间都是10ms，看起来接口性能还不错。所以TP99一般是统计性能的一个指标。

计算TP99也需要用到堆，思路如下：

创建一个大顶堆和一个小顶堆，大顶堆的堆顶元素比小顶堆的堆顶元素更小，大顶堆维护 99% 的请求时间，小顶堆维护 1% 的请求时间

每产生一个元素（请求时间），如果它比大顶堆的堆顶元素小，则将其放入到大顶堆中，如果它比小顶堆的堆顶元素大，则将其插入到小顶堆中，插入后当然要堆化以让其符合大小顶堆的要求。

上一步在插入的过程中需要注意一下，可能会导致大顶堆和小顶堆中元素的比例不为 99:1，此时就要做相应的调整，如果在将元素插入大顶堆之后，发现比例大于 99：1，将需将大顶堆的堆顶元素移到小顶堆中，再对两个堆堆化以让其符合大小顶堆的要求，同理，如果发现比例小于99: 1，则需要将小顶堆的堆顶元素移到大顶堆来，再对两者进行堆化。

以上的大小顶堆调整后，则大顶堆的堆顶元素值就是所要求的 TP99值。

用排序也可以解决该问题，但是堆是可以实时获取TP99的，使用排序只能在时间结束后堆所有数据进行排序才可以。