1。什么是堆1.1堆的定义堆是一棵完全二叉树；堆中每个节点的值必须大于或等于（大顶堆）或小于或等于（小顶堆）在其每个子树中的节点的值；1.2堆上的操作堆的存储前面学习二叉树我们知道，完整二叉树最理想的存储方式是数组，它节省了左右节点的指针空间，不会造成a很多浪费。比如节点位置是i，那么它的左子树存放在2i，右子树存放在2i+1，父节点在i/2，上下索引很快。插入元素，我们一般将要插入的数据作为一个节点放在当前堆的末尾，然后从下往上进行堆操作。在堆尾插入一个节点，从下往上堆化，删除堆顶元素。堆一般删除堆顶元素，因为堆顶要么是最大值，要么是最小值。一般不删除非堆顶元素，这是由堆的数据结构特点决定的。我们先将堆中的最后一个元素赋值给堆顶元素，然后删除最后一个元素，最后进行一次自上而下的堆操作。删除堆顶元素的堆操作在上面的插入和删除堆顶元素的操作中，主要耗时在堆的过程中，堆操作需要的比较和交换的次数会最多不超过树的高度，而我们前面说过，一棵完全二叉树的高度是2的对数，所以在堆顶插入和删除元素的时间复杂度是O(logn)。2.堆排序给定一个数组，里面的元素是无序的，杂乱的，我们如何对它进行堆排序呢？2.1建堆首先，我们需要把数组建成一个大顶堆（smalltopheap）。建堆通常有两种方法：从上到下，使用下标为1的元素作为原堆，然后从下标2开始，一直到n，依次插入到前一个堆中，就像上面提到的插入元素的操作，继续堆，然后形成一个大的顶堆；它的时间复杂度是O(nlogn)，这还不够好。从下往上，我们注意到，在一棵完全二叉树中，将最后一个元素的下标除以2，可以得到最后一个非叶子节点元素的下标n/2。单独的叶子节点是不能堆的，所以我们从n/2开始不断堆，直到下标为1，就形成了一个大的顶堆；这个过程类似于删除堆顶元素后的堆过程；它的时间复杂度是O(n)，比第一个好。建堆时从下往上堆的过程2.2排序经过上一步的建堆操作，我们得到了一个大顶堆，但是数组中的数据看起来还是乱序的，需要根据这个大topheap将数组按顺序排序。先从堆顶取出元素，这个元素一定是最大的，和数组的最后一个元素交换，放到n位，然后把堆中剩余的元素不断堆起来，一直取堆顶元素，并依次放在n-1、n-2、n-3位置，当堆中只剩下最后一个元素时，数组现在是一个有序序列。堆排序的过程可以看出，在堆排序的过程中，我们需要对n个元素进行堆操作。每次堆操作的时间复杂度取决于完全二叉树的高度，所以最终堆排序的时间复杂度为O(nlogn)。堆排序不需要大量额外的存储空间，属于就地排序；堆排序过程中相同值的位置可能会发生变化，因此不是稳定的排序算法；2.3堆排序和快速排序的比较虽然堆排序和快速排序排序时间的时间复杂度是O(nlogn)，但是一般认为堆排序的性能不如快速排序。堆排序堆过程中，比较交换元素时，读取到的数据不是局部有序的；快速排序是按本地顺序；所以快速排序对CPU缓存更友好并且具有相对更好的性能；对于相同的序列数，堆排序的数据交换次数要多于快排；3.堆排序的应用3.1堆排序上面已经解释过了。3.2优先级队列在优先级队列中，数据的出队不是按照入队的先后顺序来决定的，而是按照优先级来决定的。具有高（低）优先级的将首先出队。优先队列的实现方式有很多种，但是堆是实现它最快最高效的方式。比如Java中的PriorityQueue。场景一：合并有序的小文件假设我们有n个小文件，每个大小为100MB，每个文件存储有序的字符串。这n个小文件中的字符串怎么排序呢？将它们全部合并到一个大文件中怎么样？这里有两种方法：根据归并排序中的归并思想，设置n个指针指向每个文件的第一个字符串，装入一个大小为n的数组；然后遍历数组找到最小的元素，时间复杂度为O(n)；并从数组中取出最小的元素放入大文件中，删除数组中的元素；将元素所在小文件中的指针移动到下一位，取出元素放入array，重复第二步；使用小顶堆设置n个指针指向每个文件的第一个字符串，加载到小顶堆中，最初是一个建堆的过程；取出堆将堆顶元素放入大文件，删除小顶堆堆顶元素，小顶堆自动入堆；将元素所在小文件中的指针移动到下一位，取出元素插入小顶堆，小顶堆自动入堆，然后重复第二步；我们可以看出这两种方式的区别在于前者每次都需要遍历数组寻找最小值，而后者有两个删除和插入堆的过程。堆过程的时间复杂度为O(logn)，明显优于遍历数组的O(n)，所以第二种方法效率更高。场景二：实现高性能定时器假设我们使用定时器设置了很多要执行的任务，如何定时触发这些预先设置好的任务呢？下面介绍三种方法：程序每隔一段时间（比如1秒）扫描任务，找到最近的任务执行。这个方法其实就是每隔1秒找一次最小值。每次的时间复杂度都是O(n)。而且，假设最新的任务计划在2小时内执行，那么在2小时内，扫描程序就白执行了，浪费了资源。不推荐使用此方法。维护一个有序列表，比如使用快速排序，只需要记住最小值的执行时间，等到时间点执行程序，这样扫描程序就不用一直扫描了。使用小顶堆来维护任务列表，记住堆顶任务的执行时间，等到那个时间点再执行程序，这样扫描程序就不用一直扫描了。方法2和方法3其实很相似，关键在于用什么样的数据结构和算法来获取最小值。如果有中途插入或取消任务，对于方法2，向有序列表中插入一个元素和从有序列表中删除给定元素的时间复杂度是多少？假设我们使用最高效的二分查找，那么就是O(logn)，但是插入和删除元素需要移动元素，这次是O(n)，所以总共是O(n)；如果使用方法3，那么不管是插入还是删除元素，都是一个堆的过程，时间复杂度是O(logn)，所以使用方法3中的堆效率更高。3.3求解Top-k问题假设股票数据量为n，需要从n中找出Top-k元素，对于不断增加的数据，必须获取最新的Top-k元素。应该如何处理这个问题？羊毛布？先从n中取出前k个元素，组成一个小顶堆。此时堆顶元素最小。我们从K+1个元素开始，与堆顶元素进行比较。如果小于堆顶元素，则不做处理，继续下一个；如果大于堆顶元素，则删除堆顶元素，插入第k+1个元素；等到n个元素都遍历完，则小顶堆中的k个元素的Top-k数据都没有了；对于从外部不断添加的数据，这个想法其实是一样的。将其作为数据源，不断与堆顶元素进行比较，重复上述步骤。时间主要花在最开始k个元素的初始堆O(logk)，以及删除堆顶元素和插入新元素时的堆O(logk)；因此，总的时间复杂度应该是O(logk)nlogk)，这比使用排序得到Top-kO(nlogn)效率更高。3.4求中位数对于一个无序数列，如何求它的中位数？这取决于数组是静态的还是动态的。如果是静态序列，那么我们先对它进行排序，比如快速排序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)；largetopheap和smalltopheap堆之间元素个数的调整不会有很多元素，所以也算作常量；因此，总时间复杂度为O(logn)。既然用堆来求解动态序列的中位数比较好，那为什么不用堆来求解静态序列的中位数，而是排序呢？静态数组也可以使用上面的堆方案来求解中位数，但是时间复杂度是O(nlogn)，和排序一样，但是排序明显更简单，所以推荐使用排序方案。3.5求解百分位数求解中位数的问题实际上是求解百分位数问题的一个特例。中位数可以理解为百分位数是50%，所以如果中位数问题是泛化的，那么就是找任意百分位数的问题。思路和上面百分位数的解法是一样的。比如我们要求解90%的百分位数，那么90%的数据需要存放在大顶堆，10%的数据应该存放在小顶堆。动态增加时，需要依次与大顶堆和小顶堆的堆顶元素进行比较，确定插入到哪个堆；如果插入或删除后，小顶堆的数据占比低于10%，则需要与大顶堆进行数据交互，保证小顶堆的数据占比，从而保证顶大顶堆的元素是我们需要的百分位数据。
