1
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You might want to improve your title to shortly ask your core question. $\endgroup$ – Raphael♦ Oct 17 '17 at 9:25
  • $\begingroup$ (I deem "the Big Theta comment" unfortunate for stressing there's a lower bound on time complexity instead of mentioning amortised. Lumping Binomial Heap with Fibonacci Heap with regard to Decrease Key ignores the discrepancy in time complexity.) $\endgroup$ – greybeard Apr 15 '18 at 17:09
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. This is what I don't understand. Before you can adjust the key value, you need to find it in the heap first. That takes a linear search surely? $\endgroup$ – Hatefiend Oct 17 '17 at 9:32
  • $\begingroup$ @Hatefiend No -- you're given the a pointer to the node as an argument! $\endgroup$ – David Richerby Oct 17 '17 at 10:52
  • $\begingroup$ And how was the pointer to that node obtained? It needed to be located in the tree via a linear search? correct? $\endgroup$ – Hatefiend Oct 17 '17 at 11:13
  • 2
    $\begingroup$ @Hatefiend Who knows. Perhaps it was remembered at the point when it was inserted. The interface to the function specifies that it receives a pointer, so the function itself doesn't have to spend any time searching. Where the pointer came from is of no concern to the function that uses it. $\endgroup$ – David Richerby Oct 17 '17 at 11:16
  • $\begingroup$ Fibonacci heaps are a structs-and-pointers-type data structure, unlike (say) array-based heaps. As with binary search trees, entries don't move around in memory, only the pointer structure does. So when you add an entry, you can just remember its pointer. $\endgroup$ – Pseudonym Aug 14 '18 at 1:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.