堆¶

数据结构的堆，不是内存管理的堆。

堆是一种完全二叉树

完全二叉树
从根开始所有的子节点都是满的就是完全二叉树。
完全二叉树没有空洞，可以把数组完全利用起来，使用数组做最合适。
不完全二叉树
不完全的二叉树有空洞，用数组难处理空洞，最好用链表来做。

完全二叉树按照顺序，从上到下从左到右，一层一层的依次排下来。

完全二叉树的根放在数组的下标0里，左儿子放在数组下标1里，右儿子放在数组下标2里，一层一层的按顺序把二叉树放在数组里。完全二叉树刚好用数组处理。

堆有两种：¶

堆不分左右，左右儿子的大小不区分。

1、大顶堆¶

根节点数据最大，儿子都比根小，孙子小于儿子。

2、小顶堆¶

最小的在上面，儿子比老子大，孙子比儿子大。

堆的两个重要操作¶

1、插入新节点¶

算法：向上渗透

以大顶堆为例：

先把新节点插入到最后，然后向上渗透，和它的父节点比较，比父节点大就和父节点交换，一直向上比较，直到比父节点小则停止，新节点就放在此处。

2、删除根节点¶

算法：向下渗透

以大顶堆为例：

删除根节点，根节点为空，把最后一个节点放到根这里，作为新根。但是它放到这里可能不对，因为根要是最大的，然后向下渗透，和两个儿子比较，和大的交换，然后再比较两个孙子，和大的交换。一直继续比较。直到最后。

堆实现¶

成员变量
因为要用数组，用一个指针动态创建数组。
指定数组最大的大小。
当前的大小
构造函数
析构函数
是否是空堆
push 往堆里增加数据
pop 把根删除
top 获取根数据

析构函数¶

和new对应的delete

插入节点到堆里push¶

先检查堆是否满了，满了就不能载插入了，抛出异常。也可以利用动态数组，扩大容量。

新插入的节点都放入到最后一个位置。

然后向上渗透。也叫向上冒泡。

找到合适位置，然后插入，size++。

子节点序号和父节点序号的关系¶

子节点的序号减去1再除以2 取整就是父节点的序号。

判断子节点和父节点的大小，然后交换。

循环一层一层的向上。子节点变为父节点，父父节点，循环向上。

当节点序号等于0就到根节点了。序号大于0，并且大于父节点。一直不断向上循环比较。

循环过程中，比较小的父节点要下来，放到子节点位置。父节点的空位留下来，放新的插入的节点。

循环结束之后就找到了合适的位置。

top¶

查看堆堆根节点。大顶堆最大的数或者最小的数（小顶堆）。

pop¶

删除根

向下渗透¶

把根节点去除，根节点变成最后一个子节点
然后向下一层一层的找，先把这个节点空起来，然后找它的子节点中值大的节点比较，如果比值大的节点小，则该节点和子节点交换。
每个节点都有一个左儿子一个右儿子，左儿子是节点序号乘以2再加1，右儿子序号比左儿子大1。
判断左右儿子大小。可能只有左儿子，没有右儿子。找到值大的儿子，
利用循环向下渗透：继续该节点和子节点中大的节点比较，交换。循环直到最后一层或者该节点比子节点不小则停止。

堆排序¶

堆是常见的数据结构，堆可以做堆优先队列，也可以做堆排序。堆有很多用途。

堆排序算法：

把未排序的数据一个一个放入堆里，然后再一个一个取出来，排序就完成了。

例大顶堆：

根最大，把堆顶取出来，堆自动的把第二大的节点变成新的堆顶。每次取数据都是最大的，把所有的数据取出来之后就是排好的数据。

利用堆进行排序非常方便，先放后取就完成了。