- 8
- 443 103
SithDev
Registrace 12. 01. 2017
Fibonacci Heaps or "How to invent an extremely clever data structure"
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
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
zhlédnutí: 406 530
Video
Sorting Values with Selection and Bubble sort
zhlédnutí 4,2KPřed rokem
The next videos will be about sorting. In this video we will learn about two simple sorting algorithms. We will try to figure out, how they work, and how efficient they are. 00:00 Introduction 01:07 Selection sort: idea and implementation 02:12 Selection sort: running time 04:23 Bubble sort: idea and implementation 05:35 Bubble sort: running time 06:03 Bubble sort: a simple optimization 07:18 R...
Order and Conquer: Binary Search
zhlédnutí 3,1KPřed 2 lety
Today, we will look at a first simple but very useful algorithm: Binary Search. We will understand how it works, why it is so fast and what things we can do with it. 00:00 Prologue: Can we find the maximum or duplicates any faster? 02:52 How does Binary Search work? 05:02 Implementation 06:28 Worst case running time: intuition 07:49 Running time analysis 11:15 Extension: Which element is the cl...
Big O Strikes Back
zhlédnutí 9KPřed 2 lety
In this video, we are trying to get a better intuition for what it means if some algorithm has particular time or space requirements in big O notation. In doing so, we will learn what time complexity means, look at typical running times of algorithms and consider if there might be alternative to big O notation. 00:00 What is time or space complexity? 01:11 Typical time/space complexities: 01:41...
Comparing Algorithms: Big O Notation
zhlédnutí 6KPřed 2 lety
In this video we look at to how to compare ressource requirements of algorithms, independently from hardware, implementation etc. In doing so we will come across a useful, but infamous tool from the field of algorithms: big O notation 00:00 Ressource requirements and the scalability of algorithms 02:18 Worst case, average case and best case analysis 04:06 How to compare ressource requirements, ...
All About Algorithms: Introduction
zhlédnutí 3KPřed 2 lety
In this video series, I will give you a visual introduction into the world of algorithms. Throughout the following videos, we will look at various different topics such as sorting algorithms, data structures or graph algorithms. I will also cover important, theoretical concepts like amortized analysis by looking at concrete examples. We don't just want to look at how certain algorithms work but...
Why RSA encryption actually works (no prior knowledge required)
zhlédnutí 3,9KPřed 2 lety
In this video, I am going to show you why RSA encryption works. I will prove the correctness of RSA from scratch, so no prior knowledge will be required. All results from number theory needed to understand why RSA works will be proven along the way. 00:00 1. Introduction, outline and disclaimer 02:08 2. Recap: How RSA works 02:12 2.1. Key generation 04:49 2.2. Why RSA is secure 05:56 2.3. Encry...
Nice video, exactly what i was looking for. Everyone shows how it works, but not why it works
this was amazing, and so helpful, thank you so much!
27:35 THIS MEANS FIBONACCI HEAPS ARE A JOJO'S REFERENCEEE!? 🏇🏇🏇
where is the code!
great video, even better music choice
The main thing that came to mind when explaining why the FIbonacci Heap isn't more commonly used was entirely the amortized complexity thing - if you're running a server, life is great until your clients start doing a bunch of debt-accruing actions (inserts, decreases) and then calling extract min. Whoever called extract min won't be happy. It's great in a world where you're only crunching numbers and waiting for a single final result after a lot of heap operations (which is why people listed a lot of scientific applications), but most of the computation in a normal day is business logic, which serve lots of individual requests, and therefore much prefer consistency over raw speed.
Babe wake up, the best data structure yt channel first reel just dropped
very beautiful thank you
Ever since I first learned of red-black trees, I've been interested in the various ways trees can be used/maintained to keep data organized. This is an interesting approach.
Next Leonardo heaps?
Great video, convinced me to sub.
Great video, thank you very much❤
That was a rollercoaster. I couldn't repeat back any of that but that really helped to clear it up.
so sad that this channel has not posted anything since last year. such a high quality content, i wish i could see more from this channel. I hope the admin is fine
I was struggling to understand this concept and you saved me! Tons of thanks
This data structure is my absolute favorite, and has been for years. Second place to Red Black Trees or Circular arrays (vectors). I remember when I first saw the algorithm for how trees are merged, I exclaimed that it's absolutely genius how it works.
ooh, so fibonacci heaps are one of those glacial algorithms that I've always heard about, where n must be MASSIVE before it starts outperforming other algorithms with worse big O time complexity but better time complexity on average in all real life use cases.
Do I have permission to use your animations for my research?
For presenting my methodology easier
This is such an amazing Video, thank you very much!
Where are you? We need more videos 😢
Gorgeous video and amazing production and explanation. Congrats!
Hey! Just wanna tell you! You are way much better than our professor speaking 3hours but still got me confusing!!!!!!!!! You literally killed it !!!
This is an incredibly intuitive way to explain these concepts, great video!
gem :) or an entire fkin treasure ,,,,how can someone be soo clear and precise with their approach of explanation
Very nice video! Good explanation and no over-the-top animations. But... Why the background music? I like Bach and have the Golberg Variations on CD (Glenn Gould) Why not start the video with a recommendation of background music and leave it to the viewer to start a CD or Spotify? My mind keeps switching between listening to the music and the narration. And is not that the background music makes it difficult to follow the narration.
Great explanation; I'll need to rewatch it again several times to really understand it. Superb Work 👍👍🙏🙏
Why does the animation look similar to 3b1b?
Now that is what i want from a teacher. Explaining the why instead of just going with the how and what.
Fascinating! I like the controlled laziness approach. What other cool but unusual fatties should I know about?
There's a balance between performance and memory size, you can't optimize both. Faster algorithm is general means using more memory.
nice video! Thanks for making it
This is great!
This is the best made, most clear video on the topic I have ever seen. Amazing!
08:26 On what rule we sort the nodes in those subtrees? for example we can put all nodes of the second tree in the first one in some kind of ascending order according to original node of the first tree, so if we can why we separate those nodes in another tree?!
I like unbalanced binary trees where each node is the minimum of its right subtree (no constraints on the left subtree). Very easy to implement using list sorting, constant insert, constant delete, constant merge and amortized log min
I miss you, I wish you make more videos when you have the time , literally the most elegant algo channel (even with so low number of videos)
Anyone else notice the prime number pattern?
Um only issue I have is brain explosion wtf
Phenomenal explanation
could you do a video on Fenwick Tree aka the BIT?
Best explanation about the fibonacci heap. It is incredible!
Underrated
This is one of the most amazing video on algorithm
Write operating system don't show these uninteresting videos !
12:00 The Piano came in a little distracting here tbh.
I don't often use videos for learning about computer science, but I randomly got this recommended, and the animations were really helpful! Great work!
My favorite structure is PART (Parallelized Adaptive Radix Tree). Worst case for most operations is O(n).
what the fuck?
Please write amortized time as O*(1), otherwise it looks confusing: it seems as though constant GetMin O(1) and amortized Insert O*(1) are similar, which is not the case.
Thank you so much for this video. I've just spent a beautiful half hour, laid in my bed, my brain in constant and calm concentration.