Fibonacci Heap / Binomial Heap - Decrease Key

Question

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?

Thanks

Answer 1

The call takes a specific node because that's what you typically want to do. Since you're given a pointer to the node you're supposed to be changing, you don't need to find it.

Your heap is storing a set of objects ordered by priority, and you're much more likely to want to adjust the priority of a specific object ("Crap, my algorithms homework is due tomorrow – I thought it wasn't until Thursday!") than you are to want to adjust the priority of whatever object has some given priority. In any case, there might be multiple objects with the same priority. Would your version of decrease_key adjust the priority of all of them?

I'm not familiar with Fibonacci heaps but certainly with ordinary heaps, an operation of "adjust the priority of the items that have priority $k$" would, in the worst case, involve a linear search through the whole heap. The ordering of the heap items isn't strong enough to let you do better than that: for example, the largest item in the heap could be at any leaf.

In ordinary heaps, increase_key and set_key aren't a problem: just adjust the key value and then filter up or down as appropriate.