堆这种数据结构应用场景很多，最经典的莫过于堆排序。堆排序是一种原地的、时间复杂度为O(nlogn)的排序算法。我们今天就来分析一下堆这种数据结构。

堆是一种特殊的树。只要满足以下两点，就称为堆。

       对于每个节点的值都大于等于其子树中每个节点的值的堆，我们叫做“大顶堆”。对于每个节点的值都小于等于其子树中每个节点的值的堆，我们叫做“小顶堆”。

      首先我们需要知道堆都支持哪些操作以及如何存储一个堆。

      对于一个完全二叉树来说，用数组来存储是非常节省存储空间的。因为我们不需要存储指向左右子节点的指针，单纯的通过数组下标就可以找到一个节点的左右子节点和父节点。如下图所示。

如图所示，数组中下标为i的节点，它的左子节点的下标为2i，它的右子节点下标为2i+1，它的父节点的下标为i/2。下面我们再来看一下堆上有哪些常用的操作。我们以大顶堆为例，来看一下堆的插入操作和删除操作。

      往堆中插入一个新的元素后，我们需要继续满足堆的两个特性。

      如果我们把新插入的元素放到堆的最后，是不符合堆的特性的，所以我们需要调整，以保证其满足堆的特性。调整分为向上调整和向下调整。我们先以向上调整为例。如下图所示。

     这个过程很简单，我们让新插入的节点和其父节点对比大小。如果不      满足子节点小于等于父节点，我们就互换两个节点。一直重复这个过程，直到满足要求。

  接下来我们来看一下删除操作。我们首先把堆的最后一个元素和堆顶元素互换位置，然后删除最后一个元素。剩下的堆元素是不满足堆的要求的，我们需要从堆顶开始从上往下调整，直到父子节点满足大小关系为止。如下图所示。

      我们知道一个包含n个节点的完全二叉树，树的高度不会超过log2n，堆调整的过程是顺着节点所在的路径进行比较交换，所以时间复杂度是和堆的高度成正比的，也就是O(logN)。插入数据和删除堆顶数据的主要逻辑就是堆的调整，所以往堆里插入一个元素和删除堆顶元素的时间复杂度是O(logN)。

       我们上次讲了很多的排序方法，可以点击排序算法去查看。今天我们继续讲一种新的排序算法-堆排序，它的时间复杂度是O(nlogN)，并且是原地排序算法。我们可以把堆排序的过程大致分为两大步骤，分别是建堆和排序。

        我们首先将数组原地建一个堆。“原地”的含义就是不借助另一个数组，就在原数组上操作。我们的实现思路是从后往前处理数据，并且每个数据都是从上向下调整。

        我们看一下下面的建堆分解步骤图。由于叶子节点向下调整只能自己跟自己比较，所以我们直接从最后一个非叶子节点开始，依次向下调整就好了。

      如图所示，我们对下标从n/2开始一直到1的数据进行向下调整，下标是n/2+1到n的节点是叶子节点，所以我们不需要调整。\

       建堆结束后，数组中的数据已经按照大顶堆的特性进行组织了。数组中的第一个元素就是堆顶，也就是最大的元素。我们把它和最后一个元素交换，那最大的元素就放到了下标为n的位置。

       这个过程类似于删除堆顶操作，当堆顶元素移除以后，我们把下标为n的元素放到堆顶，然后再进行向下调整，将剩下的n-1个元素重新构建成堆。调整完成之后，我们再取堆顶元素，放到下标为n-1的位置，一直重复这个过程，直到堆中最后只剩下下标为1的一个元素，排序工作就完成了。

      现在我们来分析一下堆排序的时间复杂度、空间复杂度以及稳定性。整个堆排序的过程中，只需要个别的临时存储空间，所以堆排序是原地排序算法。堆排序包括建堆和排序两个操作，建堆的时间复杂度是O(n)，排序过程时间复杂度是O(nlogN)。所以，堆排序的整个时间复杂度是O(nlogN)。因为在排序的过程中，存在将堆的最后一个节点跟堆顶互换的操作，所以有可能会改变值相同数据的原始相对顺序，所以堆排序不是稳定的排序算法。

下面我们来说一下堆的几个非常重要的应用。

 优先级队列，顾名思义，它首先是一个队列。队列的最大特性就是先进先出。但是，在优先级队列中，出队的顺序不是按照先进先出，而是按照优先级来，优先级高的先出队。     

如何实现一个优先级队列呢？其实有很多方法，不过使用堆来实现是最直接、最高效的。因为堆和优先级队列非常相似。一个堆就可以看做是一个优先级队列。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出最高优先级的元素，就相当于取出堆顶元素。我们来看一下下面这样一个应用场景。

假如我们有100个小文件，每个文件的大小是100MB。每个文件中存储的都是有序的字符串。我们希望将这些小文件合并成一个有序大文件。这里就会用到优先级队列。      我们将从100个小文件中，各取出一个字符串，然后我们建立小顶堆，那堆顶的元素，也就是优先级队列的队首元素，也就是最小的字符串。我们将这个字符串放到大文件中，并将其从堆中删除。然后再从小文件中取出下一个字符串放入堆中。循环此过程，就可以将100个小文件的数据依次放入到大文件中。

我们可以把求topk的问题抽象成2类。一类是针对静态数据集合，也就是说数据集合事先确定，不会再变。另一类是针对动态数据集合，也就是说数据集合事先不确定，有数据动态地加入到集合中。    针对静态数据集合，如何在包含n个数据的数组中，查找前K大数据呢?我们可以维护一个大小为k的小顶堆，顺序遍历数组，从数组中取出数据和堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，我们就不做处理，继续遍历数组。这样等数组中的数据都遍历完成之后，堆中的数据就是前K大数据了。    针对动态数据求得topK，也就是实时topK。怎么理解呢？我举个例子。一个数据集合中有两个操作，一个是添加数据，另一个就是询问当前的前K大数据。     如果每次询问前k大数据时，我们都基于当前的数据重新计算的话，那时间复杂度就是O(nlogN)，n表示当前数据的大小。实际上我们可以一直维护一个k大小的小顶堆，当有数据要添加到集合中时，我们就拿它与堆顶元素做对比。如果比堆顶元素大，我们把堆顶元素删除，并将这个元素插入到堆中；如果比堆顶元素小，我们则不做处理。这样，不论何时需要查询前K大数据，我们都可以立刻返回给它。

      更多硬核知识，请关注公众号“程序员学长”。