定义
首先堆必须是一个完全二叉树。
大根堆小根堆
我们可以给堆的每个结点按层序遍历编好号码：这样我们就可以将堆用一维数组的形式来表示。
堆的基本操作
我们给堆定义两个基本操作，叫上滤或者是上浮、下滤或者是下沉
例如有这么个堆：其头结点破坏了堆序性
那么我们将这个头结点与其最大的子结点做交换，直到满足堆序性，我们把这样的一个操作叫下滤或者下沉，时间复杂度O（logN）
而上浮的过程如下，将该结点与其父节点做交换
?
这种情况就对应着我们插入元素到堆的尾部时需要做的操作：
建堆
?两种建堆法：
每次结点加入时都进行调整的操作，时间复杂度O（NlogN）
另外一种优化的方法如下：
先将树放好，然后从堆的第一个非叶子结点开始，对这些结点进行下沉的操作，以大顶堆为例，让其和大的子节点做交换，直到满足有序性。
这种建堆的复杂度看似是O(NlogN)？
错，实际上是O（N）
证明过程如下：
每个节点堆化的时间复杂度是 O(logn)，那 2/n?+1 个节点堆化的总时间复杂度是不是就是 O(nlogn) 呢？这个答案虽然也没错，但是这个值还是不够精确。实际上，堆排序的建堆过程的时间复杂度是 O(n)。我带你推导一下。
因为叶子节点不需要堆化，所以需要堆化的节点从倒数第二层开始。每个节点堆化的过程中，需要比较和交换的节点个数，跟这个节点的高度 k 成正比。
我把每一层的节点个数和对应的高度画了出来，你可以看看。我们只需要将每个节点的高度求和，得出的就是建堆的时间复杂度。
建堆过程如下：
我们将每个非叶子节点的高度求和，就是下面这个公式：
这个公式的求解稍微有点技巧，不过我们高中应该都学过：把公式左右都乘以 2，就得到另一个公式 S2。我们将 S2 错位对齐，并且用 S2 减去 S1，可以得到 S。
S 的中间部分是一个等比数列，所以最后可以用等比数列的求和公式来计算，最终的结果就是下面图中画的这个样子。
因为 h=log2?n，代入公式 S，就能得到 S=O(n)，所以，建堆的时间复杂度就是 O(n)。
?
优先队列
优先队列可以使用堆来实现，此处以小顶堆为例：
弹出元素的操作如下：
直接将根节点弹出?
然后将最后一个元素放到根结点：
?
然后对这个结点让其到根结点：
堆排序
堆排序过程如下：
首先将待排序序列构成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点
如果我们对大根堆做堆排序，那么得到的结果就是正序的。
排序过程如下：将根节点（即最大的结点）与最后一个子结点做交换，
交换完毕后，然后对此时的根节点做下沉的操作。
接下来重复上面的步骤，最终得到的结果就是正序的。
?
?
