堆排序
堆排序描述
堆排序是利用堆这种数据结构所设计的一种排序算法。堆实际上是一个完全二叉树结构。
问：那么什么是完全二叉树呢？答：假设一个二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
我们知道堆是一个完全二叉树了，那么堆又分两种堆：大顶堆 和 小顶堆它们符合一个重要的性质：
- 小顶堆满足：Key[i] <= key[2i + 1] && Key[i] <= key[2i + 2] (父节点小于子节点)
- 大顶堆满足：Key[i] >= key[2i + 1] && Key[i] >= Key[2i + 2] (父节点大于子节点)
大顶堆最大的元素在跟节点，堆的性质决定了大顶堆中节点一定大于等于其子节点，反之，小顶堆的最小元素在根节点。我们来看看大顶堆和小顶堆的示意图:
堆排序基本思想及步骤
堆排序有以下几个核心的步骤：
- 将待排序的数组初始化为大顶堆，该过程即建堆。
- 将堆顶元素与最后一个元素进行交换，除去最后一个元素外可以组建为一个新的大顶堆。（获得当前最大的元素）
- 将第二步堆顶元素跟最后一个元素交换后，新建立的堆不是大顶堆，需要重新建立大顶堆。重复上面的流程，直到堆中仅剩下一个元素。