Learn

Heaps: Conceptual

Introduction to Heaps

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 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?