Heap

###完全二叉树
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

堆

堆（heap）也被称为优先队列（priority queue）。堆中元素的排列不是按照到来的先后顺序，而是按照一定的优先顺序排列的，这个优先顺序可以是元素的大小或者其他规则。如图一所示就是一个堆，堆优先顺序就是大的元素排在前面，小的元素排在后面，这样得到的堆称为最大堆。最大堆中堆顶的元素是整个堆中最大的，并且每一个分支也可以看成一个最大堆。

堆的存储

堆可以看成一个二叉树，所以可以考虑使用二叉树的表示方法来表示堆。但是因为堆中元素按照一定的优先顺序排列，因此可以使用更简单的方法——数组——来表示，这样可以节省子节点指针空间，并且可以快速访问每个节点。堆的数组表示其实就是堆层级遍历的结果。

插入

堆还可以看成一个完全二叉树，每次总是先填满上一层，再在下一层从左往右依次插入。堆的插入步骤：

1. 将新元素增加到堆的末尾
2. 按照优先顺序，将新元素与其父节点比较，如果新元素小于父节点则将两者交换位置。
3. 不断进行第2步操作，直到不需要交换新元素和父节点，或者达到堆顶

4. 最后通过得到一个最小堆

   删除

   堆的删除操作与插入操作相反，插入操作从下往上调整堆，而删除操作则从上往下调整堆。

5. 删除堆顶元素（通常是将堆顶元素放置在数组的末尾）

6. 比较左右子节点，将小的元素上调。
7. 不断进行步骤2，直到不需要调整或者调整到堆底。