堆排序笔记

• 堆排序是一种不稳定的排序算法，平均时间复杂度为O(nlogn）

• 堆的定义：完全二叉树，每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。升序用大顶堆，降序用小顶堆（因为以大顶堆为例把根节点的和最后一个元素（也可以说最后一个节点）交换位置，那么末尾元素此时就是最大元素了）

• 堆排序的整个算法都是围绕着堆的定义进行的，每一步都在维持其满足堆的定义，思路如下

  1. 将打乱的序列自底向上调整为满足堆的定义
  2. 将堆顶元素与末尾元素互换（此时的二叉树不包括末尾元素），自顶向下调整直至满足堆的定义，重复2过程就能得到排好序的序列

• 堆可以按照层次遍历的顺序映射到一个一维数组

参考资料
详细图解堆排序 https://www.cnblogs.com/chengxiao/p/6129630.html
例题：数据流中的中位数，最大堆最小堆解法https://www.cnblogs.com/gzshan/p/10904254.html