CODEWITHSUNDEEP
algorithmdata-structuresheapfibonacci-heap
Snjór
Snjór

Reputation: 61

Original design of DecreaseKey of Fibonacci heaps in Fredman and Tarjan's paper

I am now implementing the Fibonacci heap according to the original Paper of Fredman and Tarjan. If I understand it correctly, according to the paper, to perform the DecreseKey operation of a node x, we simply cut it from its parent. But if the key after decreasing is still larger than its parent, it would be inefficient (I think). Also, I see many designs that cut a node only when its key becomes smaller than its parent, like in CLRS.

So I am a bit confused about the original design of it. Why didn't they apply a more efficient way to do DecreaseKey. Or maybe it makes the amortised analysis easier? Any response is appreciated. Thanks in advance.

Upvotes: 1

Views: 57

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

I can't speak for Fredman and Tarjan (though I audited one of Tarjan's classes once), but presumably they were focused on the worst-case amortized complexity of DecreaseKey, on which that optimization has no effect.

Upvotes: 1

Related Questions