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
Big Theta
comment" unfortunate for stressing there's a lower bound on time complexity instead of mentioning amortised. LumpingBinomial Heap
withFibonacci Heap
with regard toDecrease Key
ignores the discrepancy in time complexity.) $\endgroup$