algorithm - 如何使二项式堆中的减少键以对数时间运行

Question

二项式堆递减键的《算法导论》一书提供的接口是：BINOMIAL-HEAP-DECREASE-KEY (H,x,k)，其中H是指向树的第一个根的指针，x是节点的“索引”，其键将减少到 k。时间复杂度为 O(logn)

但是，我们通常使用链表来实现二项式堆，其中不执行搜索就无法直接访问 x，通常为 O(n)。

解决此问题的一种方法是为二项式堆中的每个节点保留一个指针，然后直接访问 O(1) 中的每个节点，但空间复杂度为 O(n)。

有人知道更好的解决方案吗？谢谢！

可以在此处找到先前的讨论。

Answer 1

如果我们将堆存储在一个数组中，我们可以很容易地做到这一点。

如果根元素在索引 i 处，则左孩子在 2i 处，右孩子在 2i+1 处。

在一个数组中，我们存储索引为 1 的元素。

如果我们像这样存储堆元素，我们可以直接减少索引 x 处的元素并从 x 开始堆化。

这种 heapify 的方式需要 o(logn) 时间。对于递减它是恒定的。