# Learning to Love Heaps

Jul 3, 2017 · 14 min read

# Rules before you heap

I mentioned earlier that we’re finally at the point in this series where we’ve covered enough important, core concepts to learn about heaps as a data structure. The main reason that I’ve been holding off on exploring heaps is because in order to really understand heaps and their value, we need to be familiar with a few different topics already, including queues, trees, binary search, and Big O notation, to name just a few. (Eventually, heaps tie back into sorting algorithms, too!)

Heaps are a great example of many core computer science concepts working together in order to form one very large abstraction, which is made up of smaller parts that we’re already familiar with!

So, let’s build up our concept of a heap bit by bit: like building blocks! We’ll start by answering something fairly simple to start: what is a heap?

# Growing and shrinking a heap

Now that we know what a heap is, exactly, we can finally start exploring how to go about using them. Let’s start by figuring out how to add things to our heap, since the whole point of a data structure is being able to add stuff to it!

We must always maintain the shape and structure of a heap — otherwise, we’re violating one of its two properties!

When growing a heap, we can only ever add a node to the left-most available spot in the tree; that is to say, the left most available node, at the lowest possible level.

Just as we percolated a node up to its correct location in the heap when we added an element, we will bubble down a node to an appropriate spot when we delete an element from the heap.

Eventually, we “bubble down” a node until we are no longer violating the heap-order property — that is to say, until all the parent nodes are greater than or equal to their child nodes (for a max heap) or less than or equal to their child nodes (for a min heap). This method of swapping allows us to easily maintain the structure of our heap so that all we need to worry about is the ordering of the nodes themselves.

# Queuing up heaps on heaps

By now we’re (hopefully) pretty comfortable with how heaps work, and the two rules that they must always follow. But there’s something still left to discuss: how do we go about implementing heaps, and why should we use them? As it turns out, the answers to both of these questions are rather intertwined.

When it comes to heaps, form truly does follow function.

Let’s answer the how first, and then we’ll get to the why.

# Resources

The heap data structure is sometimes left out of many tutorial videos and technical interview prep articles. However, they’re really worth learning since they tend to come up in computer science courses and are used for fundamental things like CPU scheduling. If you want to dig deeper into priority queues and heaps, I recommend starting out by choosing from this plethora of resources!

1. Introduction to a Heap, Paul Programming
2. Binary Heaps, Professor Victor S.Adamchik
3. Priority Queues (Heaps), Professor Ananth Kalyanaraman
4. Priority Queues, Professor Mary K. Vernon
5. Priority Queue, GeeksforGeeks

Written by