16 |堆和堆排序

一、堆（Heap）

堆是一种特殊的树，只要满足这两点，它就是一个堆。

1、 堆是一个完全二叉树；
2、 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值；

总结一下是堆的全部子节点>=父节点OR子节点<=父节点，目标节点如果有一个子节点必须是左子节点，子节点左右大小无序。

一.什么是完全二叉树

复习一下

编号2 的二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫做满二叉树。
编号3 的二叉树中，若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边，这种二叉树叫做完全二叉树，如果一棵二叉树是满二叉树, 则它必定是完全二叉树。

二.堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值

堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值。还可以换一种思路，堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。对于每个节点的值都大于等于子树中每个节点值的堆，叫“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，做“小顶堆”。
堆和之前的二叉树在节点值不同之处在于之前二叉树的左子节点小于目标节点，右子节点大于目标节点。
对于堆来讲，要么所有的目标节点都大于等于左右节点，要么所有目标节点都小于等于左右节点。

其中第1 个和第 2 个是大顶堆，第 3 个是小顶堆，第 4 个不是堆。

二、如何实现一个堆

一.实现堆

完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。