堆这种数据结构应用场景很多，最经典的莫过于堆排序。堆排序是一种原地的、时间复杂度为O(nlogn)的排序算法。我们今天就来分析一下堆这种数据结构。
一、什么是堆堆是一种特殊的树。只要满足以下两点，就称为堆。
堆是一个完全二叉树。
堆的每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
对于每个节点的值都大于等于其子树中每个节点的值的堆，我们叫做“大顶堆”。对于每个节点的值都小于等于其子树中每个节点的值的堆，我们叫做“小顶堆”。
首先我们需要知道堆都支持哪些操作以及如何存储一个堆。
对于一个完全二叉树来说，用数组来存储是非常节省存储空间的。因为我们不需要存储指向左右子节点的指针，单纯的通过数组下标就可以找到一个节点的左右子节点和父节点。如下图所示。
如图所示，数组中下标为i的节点，它的左子节点的下标为2i，它的右子节点下标为2i+1，它的父节点的下标为i/2。下面我们再来看一下堆上有哪些常用的操作。我们以大顶堆为例，来看一下堆的插入操作和删除操作。
1.往堆中插入元素往堆中插入一个新的元素后，我们需要继续满足堆的两个特性。
如果我们把新插入的元素放到堆的最后，是不符合堆的特性的，所以我们需要调整，以保证其满足堆的特性。调整分为向上调整和向下调整。我们先以向上调整为例。如下图所示。
这个过程很简单，我们让新插入的节点和其父节点对比大小。如果不 满足子节点小于等于父节点，我们就互换两个节点。一直重复这个过程，直到满足要求。
2.删除堆顶元素接下来我们来看一下删除操作。我们首先把堆的最后一个元素和堆顶元素互换位置，然后删除最后一个元素。剩下的堆元素是不满足堆的要求的，我们需要从堆顶开始从上往下调整，直到父子节点满足大小关系为止。如下图所示。
我们知道一个包含n个节点的完全二叉树，树的高度不会超过log2n，堆调整的过程是顺着节点所在的路径进行比较交换，所以时间复杂度是和堆的高度成正比的，也就是O(logN)。插入数据和删除堆顶数据的主要逻辑就是堆的调整，所以往堆里插入一个元素和删除堆顶元素的时间复杂度是O(logN)。
三、堆排序我们上次讲了很多的排序方法，可以点击去查看。今天我们继续讲一种新的排序算法-堆排序，它的时间复杂度是O(nlogN)，并且是原地排序算法。我们可以把堆排序的过程大致分为两大步骤，分别是建堆和排序。
1.建堆我们首先将数组原地建一个堆。“原地”的含义就是不借助另一个数组，就在原数组上操作。我们的实现思路是从后往前处理数据，并且每个数据都是从上向下调整。
我们看一下下面的建堆分解步骤图。由于叶子节点向下调整只能自己跟自己比较，所以我们直接从最后一个非叶子节点开始，依次向下调整就好了。
如图所示，我们对下标从n/2开始一直到1的数据进行向下调整，下标是n/2+1到n的节点是叶子节点，所以我们不需要调整。\
2.排序建堆结束后，数组中的数据已经按照大顶堆的特性进行组织了。数组中的第一个元素就是堆顶，也就是最大的元素。我们把它和最后一个元素交换，那最大的元素就放到了下标为n的位置。
这个过程类似于删除堆顶操作，当堆顶元素移除以后，我们把下标为n的元素放到堆顶，然后再进行向下调整，将剩下的n-1个元素重新构建成堆。调整完成之后，我们再取堆顶元素，放到下标为n-1的位置，一直重复这个过程，直到堆中最后只剩下下标为1的一个元素，排序工作就完成了。