I've been implementing a Fibonacci Heap in C this past week and today I just hit a mental roadblock that I can't figure out.
Decrease Key is a function that almost all min heaps have (vice versa with increase key with max heaps). However all of the decrease key functions declarations look like this:
// Big Theta 1 performance. void decrease_key(Node n);
That's great, but what about
Node find_node(Object data);?
Before you can decrease the key of the node, you have to locate it first. So the call of
decrease_key(52,17) first needs to search for
52, then update it to
17, and then restructure the tree (unless structure is lazy, such as fib tree). Doesn't that absolutely murder the complexity of that call? Locating an element in the tree cannot be fast. You'd approach
n very quickly, only skipping Node roots that are greater than the element you are looking for (since their children are even larger).
None of the documents online which feature Fibonacci heaps or binomial heaps talk AT ALL about locating a node inside the tree. I assume that I just loop over each node, and perform the following logic?
for every node n in the list int c = compare(n, data) if (c > 0) call logic recursively on his child if (c == 0) decrease_key(n, data) otherwise error cannot compare greater
Furthermore, why is there a
decrease_key but not a
increase_key, or frankly a
set? I suppose
increase_key is a much harder problem to solve?