基础排序算法四——堆排序

视频：https://youtu.be/MtQL_ll5KhQ

堆（二叉堆）可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。

堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了。

如下图，是一个堆和数组的相互关系

二叉堆一般分为两种：最大堆和最小堆。

最大堆：

最大堆中的最大元素值出现在根结点（堆顶）

堆中每个父节点的元素值都大于等于其孩子结点（如果存在）

最小堆：

最小堆中的最小元素值出现在根结点（堆顶）

堆中每个父节点的元素值都小于等于其孩子结点（如果存在）

代码实现

参考

http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/

https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F#Java