I want to tell you about a daunting, but truly fascinating data structure. At first sight, Fibonacci Heaps can seem intimidating. In this video, I'm going to show you all the necessary steps to invent a really clever data structure.
00:00 Introduction
00:50 Priority Queues and Binary Heaps
05:44 Fibonacci Heaps
08:24 Amortized Analysis
10:28 ExtractMin
16:54 DecreaseKey
22:02 3 Questions
28:16 Final Words
Animations created with Manim
Music: Goldberg Variations, J.S. Bach, Kimiko Ishizaka
Sources:
Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms ‒ Third Edition (the chapter on Fibonacci Heaps is available for free on their website under "Material Removed from 3e")
Fredman, Tarjan: Fibonacci heaps and their uses in improved network optimization algorithms.
Vuillemin: A Data Structure for Manipulating Priority Queues
#SoME2