Heaps are used to maintain a maximum or minimum value in a dataset. Our examples use numbers since this is a straight-forward value, but heaps have many practical applications.
Imagine you have a demanding boss (hopefully this is theoretical!). They always want the most important thing done. Of course, once you finish the most important task, another one takes its place.
You can manage this problem using a priority queue to ensure you’re always working on the most pressing assignment and heaps are commonly used to create a priority queue.
Heaps tracking the maximum or minimum value are max-heaps or min-heaps. We will focus on min-heaps, but the concepts for a max-heap are nearly identical.
Think of the min-heap as a binary tree with two qualities:
- The root is the minimum value of the dataset.
- Every child’s value is greater than or equal to its parent.
These two properties are the defining characteristics of the min-heap. By maintaining these two properties, we can efficiently retrieve and update the minimum value.
Your favorite store is having a sale, but you don’t have much money to spend. You’d like to be certain you’re getting the greatest number of items possible with your limited funds…
How can a min-heap help?