排序（三）选择类排序②
第二类选择类排序：堆排序
（这里是师从王道）
什么是堆：一颗完全二叉树，如果每个结点的值都大于等于其左右孩子的结点值，则为大顶堆；如果每个结点的值都小于等于其左右孩子的结点值，则为小顶堆；
完全二叉树，拿一张图来解释吧
什么是堆排序？
将无序序列调整成一个堆，选择堆顶元素加入有序序列中（堆顶元素即max或min），再把无序序列调成堆，直到所有关键字加入有序序列。
如何把无序序列调成堆？
（以大顶堆为例）
1.建立堆
从下到上，从右到左找到第一个非叶子结点，检查是否满足大顶堆的要求。
2.调堆
时间复杂度：O(nlogn)
空间复杂度：O(1)
稳定性：观察建立堆和调整堆过程中，元素在树的不同层次间交换，相同的两个数改变了次序，所以不稳定！