Fibonacci Heaps

From Dahuawiki

Fibonacci heaps offer an elegant and efficient approach for priority queue implementation.

Contents 1 Background 1.1 Basic Concepts 1.2 Shortest Paths and Minimum Spanning Trees 1.3 Amortized Analysis 2 Fibonacci Heap

Background

Basic Concepts

• Priority Queue
• Heap
  • Binary Heap
  • Binomial Heap
• Good slides on heaps (from Princeton)

Shortest Paths and Minimum Spanning Trees

• Dijkstra's algorithm on shortest paths (SP)
• Prim's algorithm on minimum spanning tree (MST)

Amortized Analysis

• Slides on Amortized Analysis of MIT algorithm course
• Amortized Analysis (Wikipedia)
  • Accounting Method
  • Potential Method

Fibonacci Heap

• Fibonacci Heap (OCW Lecture Materials) The materials found in previous courses published in OCW.
• Introduction to Fibonacci heaps A clear presentation to Fibonacci heaps, with all necessary materials. More easy to follow.
• Good slides on Fibonacci heaps (from Princeton) It uses an example to illustrate the procedures clearly.
• Fibonacci heap (Wikipedia)
• Fibonacci number (Wikipedia) It has all stuff for the related proofs.