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

Question

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

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

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

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

可以找到之前的讨论here .

Answer 1

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

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

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

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

通过这种方式进行堆化，我们需要 o(logn) 时间。对于递减，它是常数。