数据结构 第二部分.ppt

* 二项堆 二项堆支持插入删除和归并操作最坏情况下的时间复杂性是O(logN)但平均的插入时间是一个常量 二项堆表示为一个二项树的集合 * 二项堆树 二项堆树是一棵普通的树不是二叉树 高度为0的二项堆树是单个节点高度为k的二项堆树Bk是将一棵Bk-1加到另一棵Bk-1的根上形成的 二项堆树满足堆的有序性 * B0 B1 B2 B3 * 二项堆里树Bk的特性 Bk有2k个节点 第d层的节点数是二项堆