作为三大经典排序算法的堆排序，借助了堆这种精巧的数据结构，实现了排序. 理解了堆结构，再理解堆排序就不难了.

堆排序中三点要重点掌握：

• 怎样通过下标找到节点的父节点及子节点
• 建堆算法
• 堆调整算法

什么是堆

堆是一种数据结构，能够支持高效的操作.堆得一种经典实现是使用完全二叉树，这种实现也被称为完全二叉堆.事实上，堆的树结构只是它的一种逻辑结构，也就是画在纸的，在我们脑海中想象出来的，实际内存中的物理结构，常常是使用数组. 有时候堆也被称为优先级队列，这是它的逻辑上的名字，别人用起来就好像是这种结构具有某种优先级.一般来说，堆分两种: 大根堆和小根堆.作为一种数据结构，考察堆的增删改查操作.修改在堆中并不常见，忽略. 查找操作也只限定在查找最大值/最小值上. 增加操作通常加在堆的最后，删除操作通常删除根节点.

堆与数组的转化

堆结构和数组具有很好的对应，即给定一个规模为n的二叉堆，给堆得层序遍历序列对应的就是一个数组，大小同样为n. 从而，有了一个数组，就能把这个数组当成堆来用.使用三个公式即可找到任意节点i的父节点，左节点和右节点（如果有的话）. 假设大小为n的数组arr，下标记为$i = 0, 1, \cdots, n - 1$, 则其左节点的下标为 $2 \cdot i + 1$, 其右节点（如果有）的下标为 $2 \cdot i + 2$, 对于下标为j的节点，其父节点的下标为 $(j - 1) / 2$, 注意当$j = 0$ 时 其父节点时自身，$(0 - 1) / 2 = 0$ 不会越界.

建堆与维护堆

堆中，最重要的两种操作是：建堆和维护堆.建堆是指给定一组数据，比如就是一个数组，通过某种算法将其调整为一个堆（调整操作也就是调整数组中元素的位置）；维护堆是指当增删后的堆不再是一个堆时，用某种算法将其再次调整为一个合法的堆.一个合法的堆是指该堆满足堆序性，对于大根堆，堆序性是指根节点是堆中最大值，对于小根堆，定义类似.

已知对于一棵高度为h的满二叉树，其规模$n = 2^{(h + 1)}- 1$, 即 $h = O(\log n)$，

下面讨论建堆算法和堆调整算法.

建堆

最开始的思路

任意给定一个大小为n的数组，从零位置的元素出发，即从空堆出发，不断将新元素加入堆中，堆的增加操作复杂度为O(logn), 从而要建立一个大小为n的堆，复杂度为：

$$\log 1 + \log 2 + … + \log n = O(n\log n)$$

更细致的复杂度分析，假定一个规模为n的堆高度是h, 则该堆中第i层的节点个数是2^i, 其中 0 <= i < h, 建堆需要每一个元素i都上溯，则复杂度：

$$1 \cdot 2^1 + 2 \cdot 2^2 + … + h \cdot 2^h = O(n \log n)$$

Floyd算法

算法一过于复杂，建堆就需要O(nlogn)，还不如使用快排或归排.我们需要一个更高效的算法. 从相反的思路考虑，假设堆已经建好了，我们需要做的是调整堆，即下沉操作.时间复杂度：

$$(h - 1) \cdot 2^1 + (h - 2) \cdot 2^2 + … + (h - h) \cdot 2^h = O(n)$$

Done!

维护堆

堆的维护发生在增加或删除操作之后.

对于增加操作，新元素被添加至树的最后一层，最坏情况下该元素需要O(logn)次操作上溯至根节点的位置，才能保证对的合法性；对于删除操作，根节点被删除，堆的最后一个节点被移至根节点的位置，最多需要O(logn)次操作下沉至最后一层，才能保证新堆的合法性.

综上，堆的调整算法复杂度是O(logn).

堆排序

有了堆结构，排序就变得很简单了.只需O(1)的辅助空间，O(nlogn)的时间就能实排序.给定一个无序数组，该数组被看作是 [堆(无序区) | 有序区]， 堆排序的过程就是不断交换无序区中的首尾元素（等效于弹出最大值，然后用末元素顶替根元素）， 由此堆不再合法，调用调整算法使其重新称为一个合法堆， 此番操作后有序区扩大，无序区收缩，反复这个过程，遇到空堆时算法终止·

复杂度分析: 堆中n个元素都历经交换和堆调整算法，耗时O(logn)，从而最终复杂度为 O(nlogn).