Implementing a Binary Heap
In the previous two lessons in this recursion and trees course, we’ve introduced the concept of binary trees and talked about the performance boosts they can offer. In this mission, we are going to prove the power of binary trees.
You may recall the concepts of complete and balanced binary trees from the last lesson. For this lesson, we will be implementing a version of a complete binary tree that’s called a binary heap that will load in an unsorted CSV file and efficiently find the top results.. A binary heap can be a valuable tool for querying large data sets efficiently.
As we work with it, we’ll see how a complete tree can maintain its structure in a list, and how ordering works for maximum and minimum heaps. Finally, we will use the Python implementation of a heap to show how a common use case in analysis is faster using a heap rather than sorting.
Throughout this lesson, as in all the courses on our data engineering track, you’ll be applying each concept hands-on by writing code in our browser as you learn.
1. Introduction to Binary Heaps
2. Heap Inserts
3. Speed Up Insert
4. Get the Max Integer
5. Pop the Root Value
6. Grab the Top N Elements
7. Using Python's Heap
8. Analyzing the Heap
9. Next Steps