Java数据结构与算法（树）——堆（完全二叉树）
注意：这里的堆和 Java，C++ 等编程语言在内存中的“堆”是不一样的，这里的堆是一种树结构。
一、堆的定义
（1）它是完全二叉树
完全二叉树——对于一棵具有 n 个节点的二叉树按层序编号，如果编号为 i 的节点与同样深度的满二叉树中编号为 i 的节点在二叉树中的位置完全相同，则这棵树称为完全二叉树。
（2）通常用数组来实现
用数组实现二叉树。假设某个节点的索引为 index，则
- 该节点的左子节点的索引是 ；
- 该节点的右子节点的索引是 ；
- 该节点的父节点的索引是 。
（3）堆中每个节点的关键字都大于其子节点的关键字
注意堆与二叉搜索树的区别：
- 对于二叉搜索树，每个节点的关键字都大于其子节点的关键字，并且，每个节点的左子节点的关键字都小于右子节点的关键字，通过中序遍历就可实现升序遍历；
- 对于堆，只要求每个节点的关键字都大于其子节点的关键字，而每个节点的左、右子节点没有确定的大小关系。只有沿着从根节点到叶节点的每一条路径上是降序排列的。因此，相比于二叉搜索树，堆是弱序的。
二、堆的主要操作
优先级队列提供了删除最大（或最小）数据项和插入数据项的方法，可以用有序数组来实现。这种实现方式删除操作的时间复杂度为 O(1)，但是插入操作的时间复杂度还是O(N)，因为每次插入平均需要移动一半的数据项，来保证插入后的数组依然有序。
用堆实现优先级队列时，其插入和删除的时间复杂度都为 O(logN)，删除的时间变慢，但是提高了插入的时间。所以当有很多插入操作时，可以选择用堆来实现优先级队列。
1、遍历和查找
由于堆是弱序的，所以在遍历和查找的过程中，没有足够的信息来确定选择两个子节点的哪一个来走向下一层，因此，堆是不支持查找和遍历的。堆的主要作用就是快速删除最大（最小）节点和快速插入数据。
2、删除
堆的删除操作是指删除关键字最大的节点，即根节点。根节点移除后，还需将这个空的节点填上。
两种方法：
（1）所有数据项向前移动一个单元，但很费时；
（2）把最后一个节点放到根节点的位置，再向下筛选，使得该节点位于一个大于它的节点之下，小于它的节点之上（向下筛选时，将目标节点和其子节点比较，哪个子节点大就和哪个交换位置）。过程图示如下：
3、插入
插入节点时，先将节点插入数组最后一个数据的后一个位置，然后向上筛选，将该节点放在合适的位置（向上筛选，和其父节点比较，放到比其父节点小的位置即可）。