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.

Edit:

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

有帮助吗?

解决方案

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?

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top