浅谈堆结构

首先，堆是一个树的结构
然后，堆还是一种二叉树
不仅如此，堆还是一个完全二叉树
除此之外，堆还是一个满足每一个父节点都大于其儿子节点的完全二叉树

STL中的priority_queue其实就是一种堆结构

因为是完全二叉树，所以可以零浪费地用数组来模拟！

模拟思路为：节点i的儿子节点分别是i2和i2+1，而节点i的父亲为i/2
注意：根结点为1而不是0!

堆的建立：
从无节点开始：

添加第一个，作为根，记录数的大小+1

添加第二个，到数组尾部，和其父亲比较，如果大于其父亲
就和它父亲互换，并且继续和其父亲比较，直到小于其父亲或者到达根结点（递归）

堆的排序：
堆排序后的堆的层序遍历将会是一个有序的数组，我们这么实现：

1，把根结点和最后一个结点互换

2，设置堆的大小减一（因为要不动最后一个，也就是原来的根）

3，追踪现在的梗，和两儿子比较，让三者中最大的作为根，如果根被换走，追踪根继续这一操作直到无儿子或者大于儿子

重复以上操作，直到堆的大小为0（表面）

那么现在得到的堆就是一个层序遍历为有序数组的堆了！

但是，请注意，小根堆在堆排之后将会是降序数组
大根堆堆排之后将会是升序数组

初级的堆就是这里了
等我变强了再更新吧！

Over~！