大顶堆构建、排序过程

一、堆的定义
堆是一种非线性结构，可以把堆看作一棵二叉树，也可以看作一个数组，
即:堆就是利用完全二叉树的结构来维护的一维数组。
堆可以分为大顶堆和小顶堆。
堆通常是一个可以被看做一棵树的数组对象，其任一非叶节点满足以下性质:
1)堆中每一个节点的值总是不大于或不小于其父节点的值:
大顶堆:每个结点的值都大于或等于其左右孩子结点的值。
即: arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]。
小顶堆:每个结点的值都小于或等于其左右孩子结点的值。
即: arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]。
2）堆总是一棵完全二叉树。
注:上述公式，根节点从0开始。如果根节点从1开始，则左右子节点分别是2i和2i+1。
如果是排序，求升序用大顶堆，求降序用小顶堆。
—般我们说topK问题，就可以用大顶堆或小顶堆来实现，
最大的K个:小顶堆
最小的K个:大顶堆

二、大顶堆的构建过程
大顶堆的构建过程就是从最后一个非叶子结点开始从下往上调整。
最后一个非叶子节点怎么找?这里我们用数组表示待排序序列，则最后一个非叶子结点的位置是:数组长度/2-1。
假如数组长度为9，则最后一个非叶子结点位置是8/2-1=3。
比较当前结点的值和左子树的值，如果当前节点小于左子树的值，就交换当前节点和左子树;
交换完后要检查左子树是否满足大顶堆的性质，不满足则重新调整子树结构;
再比较当前结点的值和右子树的值，如果当前节点小于右子树的值，就交换当前节点和右子树;
交换完后要检查右子树是否满足大顶堆的性质，不满足则重新调整子树结构;
无需交换调整的时候，则大顶堆构建完成。
画个图理解下，以[2、8、7 、1 、3 、5 、6 、4]为例:

画个图理解下，以[3,7，16,10,21,23]为例:

三、大顶堆的排序过程
将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，
这样会得到n个元素的次小值，如此反复执行，便能得到一个有序序列了。
是不是对上面这一大段文字很头疼?
其实排序过程用下面4步就能概括:
第1步:先n个元素的无序序列，构建成大顶堆
第2步:将根节点与最后一个元素交换位置，(将最大元素"沉"到数组末端)
第3步:交换过后可能不再满足大顶堆的条件，所以需要将剩下的n-1个元素重新构建成大顶堆
第4步:重复第2步、第3步直到整个数组排序完成。