二叉堆

二叉堆是来自一种特殊的堆，二叉堆是完全二元树(二叉树)或者是近似完全二元树(二叉树)。二叉堆有两种:最大堆和360百科最小堆。最大堆行倒请秋尼:父结点的键值总是大于或等于任何一个子著然识娘待经么节点的键值;最小堆:父结点的键值总是小于或等于任何一个子节点的键值。

• 中文名 二叉堆
• 外文名 binary heap
• 作用 增加存储效率
• 分类 最大堆和最小堆

存储

　　二叉堆一般用数组来表示。例如，根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2。因此，第0个位置的子节点在1和2，1的子节点在3和4。以此类推。这种存储方式便於寻找父节点和子节点。

　　如下图的两个堆:

　　1 11

　　/ \ / \

　　2 3 9 10

　　/ \ / \ / \ / \

　　4 5 6 7 5 6 7 8

　　/ \ / \ 顾明击真材黄轻获级孩任/ \ / \

　　8 9 10 兰轮称11 1 2 3 4

　　将这两个堆保存在以1开始的数组中:

　　位置: 1 2 3 4 5 6 7 8 9 10 11

　　左图: 1 2 3 4 5 6 7 8 9 10 11

　　右棉配图: 11 9 10 5 6 7 8 1 2 3 4

基本操作

概述

　　在二叉堆上可以进行插入节点、删除节点、取出值最小的节点、减小节点的值等基本操作。

　　形式上看，它从顶点开始，每个节点有两个子节点，每个子节点又各自有自己的两个子节点;数值上看，每个节点的两个子节点都比它大或和它相等。

要求

　　在二叉堆里我们注以搞般故下要求:

　　* 最小的元素在少顶端(最大的元素在顶端)

　　* 每个元素都比它的父节点小(大)，或者和父节点相等。

　　只要满足这两个条件，其他的元素怎么排都行。如上面的例子，最小的元素10在最顶端，第二小的元素20在10的下面，但是第三小的元素24厂西久款半决高在20的下面，也就是第三层，更大的30反而在第二层。

　　这样一"堆"东西我们在程序中怎么用呢?幸运的是，二叉堆可以用一个简单的一维数组来存储，如下图所示。

　　假设一个元素的位置是n(第一个元素的位置为1，而不是通常数组的第一个丰县基创谈绝种索引0)，那么它两个子节点分别是 n × 2 和 n × 2 + 1 ，父节点是n除以2取整。比如第3个元素(足例中是20)的两个子节点位置是6和7(空)，来自父节点位置是1。

三种操作

　　对于二叉堆我们通常有三种操作:添加、删除和修改元素:

　　* 添加元素

　　首先把360百科要添加的元素加到数组的末尾，然后和它的父节点(位置为当前位置减去1再除以2取整(k-1)/2，比如第4个元素的父节点位置是1，第7个元素的父节点位置是3)比较，如果新元素比父节点元素大则交换这两个元素，然后再和新位置的父节点比较，直天留按准器实行到它的父节点不再比它小，或者已经到达顶端，即第1的位置。

　　* 删除元素

　　删除元素的过程类似，只不过添加元素是"向上冒"，而删除元素是"向下沉":删除位置1的元素，把最后一个元素移到最前面，然后和它的两个子节点比较，如果两个子节点中较小的节点小于该节点，就将它们交换，直到两个子节点都比此顶点大。

　　计算两个子节点的位置的公式:左子节点:2K+1、右子节点:2K+2(注:这里针对的是根节点为零的情况，若根为1，则左右分别为2K与2K+1。

　　比如顶点为0，就序微那么它的左右子节点分别为1和2位置，如果顶点振划她顾鸡为1，那么 1的左右两个子下背属耐重营员节点即为2和3.以此类推

　　* 修改元素

　　席油和添加元素完全一样的"向上冒"过程，只是要注意铁诉坐客样杀被修改的元素在二叉堆中的位置。

　　可以看出，使用二叉堆只需待场境具轴东很少的几步就可以完成排序，很大程度上提高了寻试着工病字责合久刑属似路速度。

具体实现

　　在C++的STL中提供了优先队列，定义方式为pr来自iority_queuepriq;默认为每一次急草伟事本怎弹出队列中最大的元素，与二叉堆性质相似，很多时候可以直接当作二叉堆使用。

　　当然，也可360百科以直接自己写一个C++的类模板，以下是完整代码: