在二项式堆中实现递减密钥 [英] implement decreasing key in binomial heap

问题描述

在二项式堆结构中，我们只知道指向最小节点的指针，但是如何减少任意节点的键?在这种情况下，首先，我应该找到该节点，然后以O(lgN)时间执行交换.

in the binomial heap structure, we know only the pointer that points to the min node, but how can I decrease the key of arbitrary node? in this case, first of all, I should find this node and then perform swapping with O(lgN) time.

我在线搜索，很多人指出了如何减少节点，但没有提到如何访问要减少的节点.

I search online and many points out how to decrease node but does not mention how to access this node to be decreased.

我应该使用指向堆中每个节点的指针.

I should use pointers that point to each node of the heap.

推荐答案

也许我在这里遗漏了一些东西，但是如果您拥有任意节点"的密钥，就不能只使用O(lg n)时间查找找到它，然后使用您在网上找到的算法将其减少?

Maybe I'm missing something here, but if you have the key to your 'arbitrary node' couldn't you just use an O(lg n) time lookup to find it, and then decrease it using the algorithm you found online?

这篇关于在二项式堆中实现递减密钥的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！