什么是堆？有哪些使用场景？

堆是一个完全二叉树；,堆中的每一个节点的值都必须大于等于（大顶堆）or小于等于（小顶堆）其子树中的每个节点的值；,,在堆的最后面插入一个节点,,自下而上进行堆化,,删除堆顶元素的堆化操作,在如上插入和删除堆顶元素的操作中，主要的时间消耗都在堆化这个过程中，堆化操作需要比较和交换的次数最大不会超过树的高度，而前面我们说过，完全二叉树的高度是2的对数，因此插入和删除堆顶元素操作的时间复杂度是O(logn)。,给定一个数组，其中的元素都是无序杂乱的，我们怎么对它进行堆排序呢？,首先，我们需要将该数组建立为一个大顶堆（小顶堆），通常有以下两种建堆的方法：,,建堆时自下而上进行堆化的过程,经过上一步的建堆操作，我们得到了一个大顶堆，但是数组中的数据看上去仍然是无序的，我们需要基于这个大顶堆把数组排下序。,首先从堆顶取出元素，这个元素肯定是最大的，把它和数组最后一个元素进行交换，放到位置n，然后堆中剩下的元素不断地进行堆化，并始终取堆顶元素依次放到n-1,n-2,n-3的位置上，当堆中只剩最后一个元素的时候，此时数组就是一个有序数列了。,,堆排序的过程示意,堆排序的过程中，我们需要对n个元素进行堆化操作，每次堆化操作时间复杂度取决于完全二叉树的高度，所以最终得到堆排序的时间复杂度为O(nlogn)。,堆排序不需要借助很多的额外存储空间，因此它属于原地排序；,堆排序过程中会可能改变相同值的位置，所以不是稳定的排序算法；,虽然堆排序和快速排序时间的时间复杂度都是O(nlogn)，但通常都认为堆排序的性能是比不上快速排序的。,如上已经讲解过了。,优先级队列中，数据的出队不是按照入队先后来决定的，而是按照优先级来的，优先级高（低）的就先出队，实现优先级队列的方法有很多，但是其中使用堆来实现是最为快捷高效的。比如Java中的PriorityQueue。,场景一：合并有序小文件,假设我们有n个小文件，每个大小为100MB，每个文件中存放的都是有序的字符串，我们如何把这n个小文件中的字符串有序地全都合并到一个大文件中呢？,这里有两个方法：,场景二：实现高性能定时器,假设我们使用定时器设置了很多个待执行的任务，那么如何实现定时触发这些提前设定好的任务呢？,这里说三个方法：,假设存量数据量为n，我们需要从n中找到Top-k的元素，并且针对不断添加进来的数据，我们都要获取最新的Top-k元素，这种问题应该怎么处理呢？,时间主要耗费在一开始k个元素的初始建堆O(logk)上，还有删除堆顶元素和插入新元素时的堆化O(logk)上；所以，总的时间复杂度应该为O(nlogk)，比使用排序来获取Top-k的O(nlogn)还是要高效的。,对于一个无序的数列，怎么求出它的中位数呢？这要看数列是静态的还是动态的。,如果是静态的数列，那么我们先进行排序，比如快速排序O(nlogn)，然后如果总数是奇数，那么中位数就在n/2+1的位置上；如果总数是偶数，那么中位数有两个，在n/2和n/2+1的位置上，随便取一个即可。总的时间复杂度就是排序算法的时间复杂度O(nlogn)。,那如果是动态数列呢，我们需要维护数列的有序性，那么势必要对新插入或者需要删除的数据进行查找，时间复杂度为O(n)，还有数据搬移的O(n)，所以就会变得很低效，我们需要使用堆来解决这个问题。,我们先将已有数据排序，然后维护一个大顶堆和一个小顶堆，其中小顶堆存放最大的n/2个数据，堆顶元素是这n/2中最小的，大顶堆存放剩下的元素，堆顶元素是最大的。此时，中位数就是大顶堆的堆顶元素。,当动态数据添加进来时，我们将待添加元素和大顶堆的堆顶元素进行比较，如果小于等于，那么就插入大顶堆中；否则就和小顶堆的堆顶元素比较，如果大于等于，就插入小顶堆中。此时，如果小顶堆中的个数超过了n/2，就需要不断地取出堆顶元素插入到大顶堆中，直至个数为n/2；如果小顶堆中的个数小于n/2，就需要不断地取出大顶堆的堆顶元素插入到小顶堆中，直至小顶堆个数为n/2；,,动态数列使用堆求解中位数过程示意,通过如上的过程，我们每次从大顶堆堆顶取出来的元素就是整个数列的中位数。整个过程的时间复杂度是多少呢？一开始初始化时的排序和建堆，由于数据比较少，可以算作常量；后续动态数据的插入或者删除，就是一个堆化的过程，时间复杂度为O(logn)；大顶堆和小顶堆之间元素个数的调整不会有很多元素，所以也算作常数；因此，总的时间复杂度就是O(logn)。,既然动态数列求解中位数使用堆比较好，为什么静态数列求解中位数不使用堆，而是排序呢？静态数列也可以使用如上堆的方案进行求解中位数，但是时间复杂度也是O(nlogn)，和排序是一样的，但是排序明显更加地简单，因此推荐使用排序的方案。,求解中位数的问题其实就是求解百分位数问题的一种特殊情况， 中位数可以理解为百分位为50%，所以把中位数问题一般化的话，那么问题就是求解任意百分位数的问题。,思路和上述求解百分位是一样的，比如我们要求解90%百分位的数，那么大顶堆中需要存放90%的数据，小顶堆中存放10%的数据，当动态地增加时需要依次和大顶堆、小顶堆的堆顶元素进行比较以决定插入到哪个堆中；如果插入或者删除后，小顶堆中的数据占比不是10%了，就需要和大顶堆进行数据的交互以保证小顶堆数据的占比，如此才能保证大顶堆的堆顶元素就是我们需要的百分位数据。​