经典算法系（9）-二叉堆&二项树&二项堆&斐波那契堆（Binary Heap&Binomial Tree&Binomial Heap&Fibonacci Heap）

10. 二叉堆（Binary Heap）

 二叉堆是完全二叉树（或者近似完全二叉树）；其满足堆的特性：父节点的值>=(<=)任何一个子节点的键值，并且每个左子树或者右子树都是一个二叉堆（最小堆或者最大堆）；一般使用数组构建二叉堆，对于array[i]而言，其左子节点为array[2*i]，其右子节点为array[2*i+1]；二叉堆支持插入，删除，查找最大（最小）键值的操作，但是合并二叉堆的复杂度较高，时间复杂度为O(N)；但是二项堆或者斐波那契堆则仅需要O(logN)；

11. 二项树（Binomial Tree）
 定义度数为二项树根节点的直接子节点个数；如果一棵二项树的度数为0，则其只包含一个根节点；如果一棵二项树（包括子树）的度数为K，则其根节点包含K个子节点，并且其子节点分别为度数是K-1,K-2,K-3,…,1,0的子树的根；
 

 从上图可知，
 每当一棵二项树的度数从k-1变成k，则其所有子节点的个数增加2k-1。因此度数为K的二项树的所有子节点个数为1+2+…+2k-1=2k。
 二项树的高度由其增加的度数锁带来的子树的高度确定（度数每增加1，相当于二项树根节点增加一个其自身大小的子树，所以其高度和节点数都变成2N或者2H），所以其高度为H=k
 在深度为h的层（从0开始记），节点个数为C(k, h)，也就是从k个数中选h个数的选择方法数；C(k, h)=k!/(h!*(k-h)!)

12. 二项堆（Binomial Heap）

Read full article from 经典算法系（9）-二叉堆&二项树&二项堆&斐波那契堆（Binary Heap&Binomial Tree&Binomial Heap&Fibonacci Heap）