MISSION 230

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.

Objectives

  • Learn how to build a binary heap structure.
  • Learn what kind of problems can be solved using a binary heap.
  • Runtime of binary heap algorithms.

Mission Outline

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
10. Takeaways

recursion-and-tree-structures

Course Info:

Advanced

The median completion time for this course is 5.2 hours. View Details

This course requires a premium subscription. This course includes six missions and one guided project.  It is the sixth course in the Data Engineer path.

START LEARNING FREE

Take a Look Inside