堆(heap)与堆排序
堆,也被称为优先队列，是一种特殊的完全二叉树。常见应用是堆排序和Topk问题（找出最大的或最小的k个元素）。
队列中允许的操作是先进先出，在队尾插入元素，在队头取出元素。而堆也是一样，在堆尾插入元素，在堆顶取出元素，但是，堆中元素的排列顺序不是像队列一样按照到来的先后顺序，而是按照一定的优先顺序。这个优先顺序，可以按照元素的大小或者其它规则。
下面这棵树就是按照元素大小排列的。不难发现这棵二叉树有一个特点，所有父节点都比子节点大（注意圆圈里的是值，圆圈上面的是节点的编号）。符合这样特点的完全二叉树我们就称之为大根堆。反之，父节点比孩子节点小的，称之为小根堆。当然，你也可以按照其他规则进行排列。
比较有趣的是，因为堆是完全二叉树，所以使用数组来进行存储最合适不过了，而不是链表。因为这样更加节省空间，并且可以快速访问某个节点。不难发现，某个元素的下标为i，那么它的左右孩子下标分别是2*i+1和2*i+2（如果有左右孩子的话）。
上面的堆映射到数组中便是下图的样子。
堆的建立
堆的建立分为自上而下和自下而上两种方式建立。
自下而上构建堆
这里的“下”不是指最后一个元素，而是指最后一个有孩子的父节点，即n/2-1,n为堆元素个数，也就是第一幅图中的5号节点。以父节点为线索，逐渐调整该节点的子节点。
下面有一棵树，如何将其构建为大根堆呢？
先找到最后一个父节点，也就是5号元素，将其和它的孩子进行比较，左孩子比父节点大，那么进行交换，调整结束。见图二
接下来对4号父节点开始调整，不过，两个孩子都没有父节点大，所以无需调整，调整结束。
接下来对3号父节点开始调整，需要和比它大的8号节点进行交换，交换后调整结束。
接下来对2号父节点开始调整，两个孩子都比父节点大，将最大的和父节点进行交换，交换后调整结束。
接下来对1号父节点开始调整，它的左孩子比父节点大，那么进行交换，交换后的结果见图五。
此时和之前有一些不同，之前调整的父节点（3、4、5号父节点），它的孩子就是叶子结点，所以不需要再次进行调整。但现在和1号父节点的孩子不是叶子节点，它也有孩子。比较大的孩子和比较小的父节点交换后，孩子就变小了，如果这个孩子也拥有自己的孩子，那么可能会破坏堆的性质。
如上图，3号父节点已经不满足堆的性质了，虽然我们之前调整过3号节点，但因为1号节点的调整，导致它被破坏了。所以我们需要对和父节点交换的孩子再次进行调整直至孩子是叶子节点。
3号节点调整后如下图，它的孩子是叶子结点了，所以调整可以结束了。
接下来对0号根节点进行调整。父节点需要与左孩子进行交换。
然后我们需要对和父节点进行交换的1号节点继续调整，如下图。
继续对3号节点进行调整，如下图。
3号节点的孩子已经是叶子节点了，所以不需要再次调整，此时0号节点也调整完毕，那么堆也构建完成了。图八就是我们最终的结果。
自上而下构建堆
自上到下很好理解，首先假设当前数组arr的前i个元素已经满足堆性质（arr[0]只有一个元素肯定满足）；然后每次在数组之后添加一个元素A[i]，调整当前节点i使其满足堆化，使得新的数组A[0~i]满足堆化性质。直到i为n时，调整完毕，即堆化完毕。
可以分为三个步骤
- 将新元素增加到堆的末尾
- 按照优先顺序，将新元素与其父节点比较，如果新元素小于父节点则将两者交换位置。
- 不断进行第2步操作，直到不需要交换新元素和父节点，或者达到堆顶。
最后就会得到我们想要的堆。
那么，我们还是以图一的那棵树进行详细的演示。
首先对0号节点调整，额，没啥调整的，结束。
然后对1号节点调整，它比父节点大，和父节点交换后，调整结束。
然后对2号节点进行调整，13比19小，无需调整，调整结束。
然后对3号节点进行调整，3号比其父节点大，进行交换。
交换后的结果如上图，由于3号节点的父节点不是堆顶，那么我们还需要对1号节点再次调整，不难发现0号节点的堆性质已经被破坏了。对1号节点调整后如下，1号节点的父节点已经是堆顶，所以无需再次调整。
然后对4号节点进行调整，其父节点比它大，所以无需调整。
5号节点同上，无需调整。
然后对6号节点进行调整，它需要和父节点进行交换，交换后如下图。然后对2号节点进行调整，发现2号节点比父节点小，不需要调整。6号节点调整结束。
然后对7号节点进行调整，需要交换，调整后如下图。然后对7的父节点进行调整，发现无需调整。7号节点调整完毕。
然后对8号节点进行调整，需要和父节点交换。30这个数还是蛮大的，它会一直上浮。文字描述重复苍白，看图。
9号和10号无需调整。
然后对最后一个节点——11号节点进行调整，交换一次后，结束。
图十五就是我们调整的最终结果。
两种建立方式的区别
自上而下的方式，也叫做插入建堆，适合动态的增加堆元素，时间复杂度为O(nlgn)。
所以，我们应当根据情况选择合适的建堆方式。
堆排序
可以分为三个步骤
- 1.将数组堆化
- 2.将堆顶元素和最后一个元素交换
- 3.将剩余的n-1个节点重新进行堆化直到堆元素数量为1
重复步骤2、3就会得到一个有序的序列。
既然是排序，那么一般排序的元素都已经确定好了，所以堆排序构建堆的方式常用自下而上的方式。
代码实现
void createHeapTop2Buttom(int arr[], int len)
{
for (int i = 1; i < len; i++)
{
int c = i;
int p = (c - 1) / 2; //i父亲的下标
while (arr[p] < arr[c])
{
//如果父亲比此节点小，则更换
int tmp = arr[p];
arr[p] = arr[c];
arr[c] = tmp;
//将当前节点更新为父节点继续调整
c = p;
p = (c - 1) / 2;
}
//满足大根堆，直接调整完毕
}
}自下到上构造大根堆， 时间复杂度为O(n)
void createHeapButtom2Top(int arr[], int len)
{
for (int p = len / 2 - 1; p >= 0; p--)
{
//int p = p;
int maxid = p;
while (1)
{
//有孩子节点比父节点大
if (p * 2 + 1 < len &&arr[maxid] < arr[p * 2 + 1])
{
maxid = p * 2 + 1;
}
if(p * 2 + 2 < len && arr[maxid] < arr[p * 2 + 2])
{
maxid = p * 2 + 2;
}
if (p == maxid)
{
break;
}
int tmp = arr[maxid];
arr[maxid] = arr[p];
arr[p] = tmp;
p = maxid;
}
}
}堆排序
void heapSort(int arr[], int len)
{
while (len > 1)
{
createHeapButtom2Top(arr, len);
int tmp = arr[0];
arr[0] = arr[len - 1];
arr[len - 1] = tmp;
len--;
}
}