• 6.5210/18.415: Advanced Algorithms
  • PSets
  • Calendar
  • Materials
  • Information
  • Fibonacci Heaps

    David Karger

    Shortest path/MST motivation. Discuss Prim/Dijkstra algorithm.

    Note: lots more decrease-key than delete.

    Response: balancing


    Fibonacci Heaps

    Fredman-Tarjan, JACM 34(3) 1987.


    Key principles:

    Lazy approach:


    Solution: Use your work to simplify

    Benefit: on delete-min, new min is child of current root

    Can we be lazy and simultaneously prepare for future laziness?


    induction: if only link heaps of same degree, than any degree-\(d\) heap has \(2^{d}\) nodes.

    Consolidation algorithm for list of arbitrary HOTS

    For delete min

    Combine with lazy insert

    Heap ordered trees implementation

    Insert solution idea: adversary has to do many insertions to make consolidation expensive.

    Result: \(O(1)\) amortized insert, \(O(\log n)\) amortized delete

    What about decrease-key?

    “saving private ryan”

    Analysis: must show

    Second potential function: number of mark bits.

    Analysis of tree size:


    Cannot beat these bounds, since can use to sort.

    Minimum Spanning Tree

    minimum spanning tree (and shortest path) easy in \(O(m+n\log n)\).

    More sophisticated MST: