Learning to Love Heaps

Vaidehi Joshi
Jul 3, 2017 · 14 min read
Learning to love heaps!

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?

Heaps: a defintion
The two rules of heaping: shape + order.
Min heaps vs. max heaps

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.

Growing a heap: adding an element.
Shrinking a heap: removing an element
Shrinking a heap, continued: removing an element

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.

Representing a heap as an array structure
Transforming heaps into arrays [EDIT: please notice that the number 4 is missing! I should have drawn it in (oops). It should be the right child of 19!]
Determining a node’s index in an array
Priority queues are queue data structures with additional properties.
Binary heaps are efficient ways of implementing priority queues!

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

basecs

Exploring the basics of computer science, every Monday, for a year.

Vaidehi Joshi

Written by

Writing words, writing code. Sometimes doing both at once.

basecs

basecs

Exploring the basics of computer science, every Monday, for a year.