二项堆1978

二项树

二项树递归定义如下：

度数为0的二项树只包含一个节点

度数为k的二项树有一个根节点，根节点下有 k 个子女，每个子女分别是度数分别为 k-1,k-2,...,2,1,0 的二项树的根

度数为k的二项树共有 2^(k) 个节点，高度为 k。在深度d处有 （公式略） （二项式系数）个节点。

度数为k的二项树可以很容易从两颗度数为k-1的二项树合并得到：把一颗度数为k-1的二项树作为另一颗原度数为k-1的二项树的最左子树。这一性质是二项堆用于堆合并的基础。

二项堆

二项堆是指满足以下性质的二项树的集合：

每棵二项树都满足最小堆性质，即节点关键字大于等于其父节点的值

不能有两棵或以上的二项树有相同度数（包括度数为0）。换句话说，具有度数k的二项树有0个或1个。

以上第一个性质保证了二项树的根节点包含了最小的关键字。第二个性质则说明节点数为 n 的二项堆最多只有 log n 棵二项树。实际上，包含n个节点的二项堆的构成情况，由n的二进制表示唯一确定，其中每一位对应于一颗二项树。例如，13的二进制表示为1101, 2³+2²+2⁰, 因此具有13个节点的二项堆由度数为3, 2, 0的三棵二项树组成：

示例：一个含13个节点的二项堆

二项堆的操作

由于并不需要对二项树的根节点进行随机存取，因而这些节点可以存成链表结构。

合并

最基本的为二个分支度相同的二项树的合并。由于二项树根节点包含最小的关键字，因此在二棵树合并时，只需比较二个根节点关键字的大小，其中含小关键字的节点成为结果树的根节点，另一棵树则变成结果树的子树。

• function mergeTree(p, q)
• if p.root <= q.root
• return p.addSubTree(q)
• else
• return q.addSubTree(p)

两个二项堆的合并则可按如下步骤进行：分支度 j 从小取到大，在两个二项堆中如果其中只有一棵树的分支度为 j，即将此树移动到结果堆，而如果只两棵树的分支度都为 j，则根据以上方法合并为一个分支度为 j+1 的二项树。此后这个分支度为 j+1 的树将可能会和其他分支度为 j+1 的二项树进行合并。因此，对于任何分支度j，可能最多需要合并3棵二项树。

此操作的时间复杂度为 O(log n)。

function merge(p, q)

while not (p.end and q.end)

tree = mergeTree(p.currentTree, q.currentTree)

if not heap.currentTree.empty

tree = mergeTree(tree, heap.currentTree)

heap.addTree(tree)

heap.next; p.next; q.next

插入

创建一个只包含要插入元素的二项堆，再将此堆与原先的二项堆进行合并，即可得到插入后的堆。由于需要合并，插入操作需要 O(log n) 的时间。平摊分析的时间复杂度为 O(1)。

查找最小关键字所在节点

由于满足最小堆性质，只需查找二项树的的根节点即可，因为一共有 log n 棵子树，所以用所时间为 O(log n)。

可以保存一个指向最小元素的指针，使得查找最小关键字所在节点需要 O(1) 的时间。在执行其他操作时，需要修改该指针。

删除最小关键字所在节点

先找到最小关键字所在节点，然后将它从其所在的二项树中删除，并获得其子树。将这些子树看作（合并为）一个独立的二项堆，再将此堆合并到原先的堆中即可。由于每棵树最多有 log n 棵子树，创建新堆的时间为 O(log n)。同时合并堆的时间也为 O(log n)，故整个操作所需时间为 O(log n)。

• function deleteMin(heap)
• min = heap.trees.first
• for each current in heap.trees

if current.root < min then min = current

• for each tree in min.subTrees
• tmp.addTree(tree)
• heap.removeTree(min)
• merge(heap, tmp)

减小特定节点(关键字)的值(Decreasing a key)

在减小特定节点（关键字）的值后，可能会不满足最小堆积性质。此时，将其所在节点与父节点交换，如还不满足最小堆性质则再与祖父节点交换......直到最小堆性质得到满足。操作所需时间为 O(log n)。

删除

将需要删除的节点的关键字的值减小到负无穷大（比二项堆中的其他所有关键字的值都小即可），执行“减小关键字的值”算法，使其调整到当前二项树的根节点位置，再删除最小关键字的根节点即可。

运行时间

• 以下对于二项堆操作的运行时间都为 O(log n) （节点数为 n）：
• 在二项堆中插入新节点
• 查找最小关键字所在节点
• 从二项堆中删除最小关键字所在节点
• 减小给定节点关键字的值
• 删除给定节点
• 合并两个二项堆