删除操作: 对于Binomial堆中的删除操作,其主要步骤为:找到含有要删除节点的树,并将该树从堆中移除,将该树的子树们合并,最后重新组织堆以满足Binomial堆的性质。
具体实现代码如下:
struct Node* binomialHeap::deleteKey(struct Node* root, int k) { // ... }
增加操作: 对于Binomial堆的关键字增加操作,其主要步骤为:首先找到待修改节点,并将其关键字更新,然后更新堆以满足Binomial堆的性质。
具体实现代码如下:
struct Node* binomialHeap::increaseKey(struct Node* root, int i, int k) { if (root == NULL) return root;
// 找到待修改节点并更新其关键字
if (root->data == i)
{
root->data = k;
// 如果当前节点的关键字比其父节点小,则需要交换这两个节点
while (root->parent && root->data > root->parent->data)
{
swap(root->data, root->parent->data);
root = root->parent;
}
return root;
}
// 递归查找待修改节点
Node* res = increaseKey(root->sibling, i, k);
if (res) return res;
res = increaseKey(root->child, i, k);
if (res) return res;
return NULL;
}
上一篇:binom.pmf只返回零