Heap

• 堆是一个完全二叉树。
• 树的节点的深度是当前节点到顶点的距离。
• 树的节点的高度是当前节点到下一个叶子节点的最短距离。
• 深度为n的二叉树最多有2^n - 1个节点。
• 深度为n的二叉树最多有2^(n - 1)个叶子节点。

heapify

时间复杂度最坏是O(log n)，因为假设堆有n个节点，最坏需要从上到下走遍完整深度，高度是log n.

从数组构建堆

这是最有意思的，也是最神奇的，如果从一个空数组开始，每次进行一次heapify，显然最后的时间复杂度是O(n log n)，并且空间复杂度也是O(n)。
但是如果直接在数据内进行heapify，只需要对n/2的节点进行heapify，并且部分heapify过程的时间复杂度比log n要快，当然还是有具体数学过程来证明过的，最终从数组内直接构造堆得时间复杂度是O(1).

Heapsort 堆排序

有了上述知识，堆排序就理解起来简单很多，堆排序就是先从一个无序的数组内直接构造一个堆，然后循环，每次把堆得最大值（或者最小值）提取出来（又称Extract Max），最后完成对数组的排序，时间复杂度是O(n log n)。
堆排序在实际应用中还是有比较重要的地位，虽然通常轻快下，没有快排快，但是在最坏情况下，堆排序依然是O(n log n)，而快排最坏是O(n^2)，和冒泡一个级别。另外堆排序和插入排序时间复杂度很像，但是堆排序的空间复杂度是O(1)，也就是在空间内排序，而插入排序空间复杂度是O(n)。