1

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.

Sean
  • 4,267
  • 10
  • 36
  • 50

1 Answers1

1

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?

corsiKa
  • 81,495
  • 25
  • 153
  • 204