# Learning to Love Heaps

### Vaidehi Joshi ăť14 min read

Today marks the halfway point of this seriesĂ˘âŹĹ âĂ˘âŹĹ weâve officially made it through the first half of basecs! This is, of course, cause for celebration. Trust me, Iâm just as surprised as you that weâve not only covered so many topics together this year, but also that youâre still reading this series and arenât bored out of your mind yet.

One of the concepts that weâve spent a lot of time learning about recently in has been sorting; in particular, weâve been diving into sorting algorithms, and the many different methods of ordering a collection of items. But today, Iâm very pleased to share that weâre *not* going to talk about sorting at all in this post at all (feel free to breath in a sigh of relief!). Instead, weâre going to play with my favorite new data structure: a ** heap**.

As it turns out, weâve already got the toolsĂ˘âŹĹ âĂ˘âŹĹ or rather, the core conceptsĂ˘âŹĹ âĂ˘âŹĹ to learn about this data structure. Iâve been waiting to share the joy of heaps until now because they actually have a lot to do with *sorting algorithms*. However, theyâre a bit more complex, so it helps to have a few sorting algorithms under our belt before we dive into how heaps can be efficient ways to sort.

Hang onĂ˘âŹĹ âĂ˘âŹĹ I promised you no sorting at all this week. So, weâll save that for now. Rather, letâs stick with the basics to start. For example, what even *is* a heap? Where did they come from? Who even uses them? And should *we* be using them? If any (or all) of these questions are popping into your head, fear not: youâll have all the answers very shortly. But first: we must learn 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!)

If this looks like a lot of stuff to know, donât worryĂ˘âŹĹ âĂ˘âŹĹ I have good news! If youâve been reading this series in order, from the very beginning, youâre all set to learn everything there is to know about heaps! I often say that everything in computer science (and software, for that matter) is building blocks, one on top of another, of small abstractions.

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?

A ** heap** is really nothing more than a binary tree with some additional rules that it has to follow. These two rules are the two properties that define what differentiates a heap structure from any other tree structure.

Earlier in this series, we learned about trees, which always have a root node, and can have many child nodes. We also discovered the curious binary tree, which is a subset of a tree structure, with itâs own set of rules to follow. We can recall that a binary treeâs nodes can only ever have two children: a left child, and right child.

A heap is basically just one of these binary trees; it just has even *more* rules that it must follow! Heaps were invented fairly recently in 1964 by John Williams, and when most people talk about heaps, theyâre referring to binary heaps, which are shaped exactly like binary trees. Heaps are effectively binary trees with more specifications and properties.

So, what are the two properties of a heap? Well, it all boils down to the **shape** of the tree, and the **order** of the treeâs nodes. If we can remember these two aspects, it will be easy for us to identify a heap from any other binary tree.

Letâs talk about **shape** first. In order for a binary tree to qualify as a heap, it must be *complete* tree; in other words, every single level of the tree must be completely filledĂ˘âŹĹ âĂ˘âŹĹ with the last level being the only exception. Additionally, the last level of the tree must always have the left-most nodes filled first.

Another way of thinking about this is that one entire level of nodes must all have children added to them before they can have grandchildren nodes.

In the example shown here, the tree on the left has two children nodes at the root; however, the left child node has a grandchild, while the right child node doesnât even have children! This makes the tree *non-complete*, which means that it cannot be considered to be a heap.

In comparison, the tree on the right has a root node with two children. We can see that both of the children nodes donât have children of their ownĂ˘âŹĹ âĂ˘âŹĹ only the left child has a single child node of its own. However, this is still a heap because the nodes of the last level are filled up starting from the left side. But, if instead of the left child, the right child had a node, this would no longer be a heap, since it would be violating the shape-order property of heap data structures.

What about the **order** of a heapĂ˘âŹĹ âĂ˘âŹĹ what are the rules for that?

The basic rule for the order property of a heap is this: a parent nodes (including the root node) of a heap must *either* be greater than or equal to the value of its children nodes, *or* less than or equal to the value of its children nodes. Either of these two formats is acceptable for a heap and, based on the ordering of the parent-child nodes, we can classify heaps based on their ordering.

A **min heap** is a heap where every single parent node, including the root, is less than or equal to the value of its children nodes. In the example shown here, the pink heap is a min heap, since the parent nodes, 5 and 12, are less than or equal to the value of their children nodes. The most important property of a min heap is that the node with the smallest, or *minimum value*, will always be the root node.

A **max heap** is effectively the converse of a min heap; in this format, every parent node, including the root, is greater than or equal to the value of its children nodes. In the red heap illustrated here, the parent nodes are 58, 40, and 50, and they are all greater than or equal in size to their child nodes. The important characteristic of a max heap is that the node with the largest, or *maximum value* will always be at the root node.

There are two important things to note here, which we might have already picked up on based on the examples we just looked at. First, we can always have duplicate values in a heapĂ˘âŹĹ âĂ˘âŹĹ thereâs no restriction against that. Second, a heap doesnât follow the rules of a binary search tree; unlike binary search trees, the left node does *not* have to be smaller than the right node! In fact, in both of the trees shown above, the left node is often larger than the right! The ordering of the child nodes isnât important for a heap; the only ordering that matters is the **heap-order property** , or the ordering of parent nodes compared to their children.

### 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!

The crucial thing to always keep in mind when growing or shrinking a heap is how we are manipulating or changing its structure in the process.

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.

In the illustration shown here, we have a max heap with 73 as the root node, and five nodes in total. We want to add an element to this heap: 43. In order to do so, we have to find the lowest level, and add this element to the left-most available spot.

We can add it as the left child of the node 35. Great! Well, *almost*. Our heap follows the shape property, but now weâre violating the order property, since the parent node, 35, is less than its child node, 43.

How can we solve this so that weâre following both the rules of shape *and* order?

Well, the solution is fairly simple: we can just swap the two nodes that are out of order! If we swap the child node 43 for the parent node, 35, we no longer violate our max heapâs ordering rule! And now, our heap is both structured correctly, as well as ordered correctly. Not too terrible, right?

Okay, so what about removing an element from our heap? Remember: we canât break our rules of shape and order while doing this, so we need to be a little clever here. Since we did some swapping magic while growing our heap, you might already have an idea in your head about *how* to go about doing this while shrinking our heap!

In the example show below, weâre still dealing with the same max heap as before; itâs grown a bit, and now we have 9 nodes in total, including the root node. When deleting or removing an element, most heaps are usually concerned with removing the root node, since the root will always be either the largest value element or the smallest value element, depending upon whether the heap is a max heap or min heap.

So, letâs say that weâre removing the root node, 71, which is our largest value element.

CoolĂ˘âŹĹ âĂ˘âŹĹ we can remove it without any problems. ExceptâŚnow our tree doesnât have a root node, which means that weâre totally messing up our heapsâ structure! Weâll need to move some things around so that our heap actually looks like the binary tree itâs supposed to look like.

Okay, we know that we canât start removing nodes at random, since we need to keep all of our levels filled up. However, we *can* remove the right-most node at the lowest level. In this case, that node has the value 2; we can remove this node, and stick it in our root nodeâs position, so that our tree still looks like a heap. Great! Now our heap is shaped correctly, but the order is totally wrong: 2 is definitely less than its child nodes, 19 and 43. We know that itâs violating our heap-order property in this location.

So, letâs try using our clever swapping trick again! We can compare the two child nodes of our out-of-order root node. In this case, those two nodes are 19 and 43. Since they are *both* bigger than 2, we can take the larger of the two child nodes, and swap it with the out-of-order root node. Since 43 is larger than 19, itâs the larger of the two children; we can swap it with 2, and now 43 becomes our root node, and 2 becomes its child node!

Now, while 2 isnât the root node any more, itâs still a parent node of two elements that are larger than it: 35 and 20. So, weâre not *quite* done with this node just yet!

The good news is that we can basically continue doing this compare-and-swap trick until the element we replaced our root node with, the node 2, is located in an acceptable place.

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*.

While itâs totally possible to implement a heap as a linked list, the way that we implemented trees earlier in this series, thereâs a far more interesting way of representing a heap: *an array*.

We might have already noticed that heaps are *partially sorted* data structures; there is an element of âorderingâ to them, but theyâre also not completely sorted in the way that a binary search tree would be. However, the most import aspect of a heap is that the maximum or minimum value element is *always* the root node.

Because we can always depend on this fact to be true, we can always represent the root node of a heap as the *first element* of an array. In other words, the root node is always located at index 0 of an array.

Whatâs super interesting is that, if we know the index of the root node, we can manipulate that index in order to determine where its child nodes would be located within that same array representation of the heap.

There are some helpful algorithms/formulas to help us figure out the location of a child element. For example, if a parent nodeâs index is represented by index i in an array, then itâs left child will always be located at 2i + 1. Similarly, if a parent nodeâs index is represented by index i in an array, then itâs right child will always be located at 2i + 2.

Letâs look at an example of a heap translated to an array, and these algorithms will start to become a lot more clear and obvious to see.

In the illustration shown here, we have a heap with eight nodes in it, including the root. We can use the parent-child relationships and array indexes to transform this array into a heap, and vice versa.

For starters, we know that our root node, 43, is at an index of 0. If we know that i = 0, then we can use our left child and right child formulas to determine the index of the first two children, 19 and 35. If we substitute the index of our root node, 0, for i, then we can pretty quickly figure out that the node 19 should live at the index of 1, since (2Ăâ0)+1 is equal to 1.

Iâve illustrated how this works for each of the child nodes and grandchildren nodes. Notice that, with each level we move down in the heap, the index of of the parent node, i, changes accordingly.

We can also determine the index of a nodeâs parent by subtracting 1 from the current nodeâs index, n, dividing it by 2, and finding the floor of that number. If youâve never seen the floor shorthand before, donât worryĂ˘âŹĹ âĂ˘âŹĹ all it means is rounding down a decimal to its closest integer (i.e. 2.9 would round down to 2). For example, we can determine the index of the node 2âs parent by finding the floor of (5â1) divided by 2. This gives us the index of its parent, 2, which is the node 35.

These two formulas are effectively how heaps are built and created, as well as the logic for determining which nodes live at what index in their corresponding array structures! We can see how the parent-child relationships are maintained using these formulas, even while the heap is represented in an array format.

Okay, so now that we know *how* to represent a heap, the question yet to be answered is, of course, *why* we need to represent them as arrays at all! Well, guess what? You already know the answer. Itâs because of *queues*!

We might remember that queues are data structures that follow the first-in, first-out (FIFO) principle, and are used in tons of places: managing requests, jobs, CPU scheduling, are just a few examples. Heaps are often implemented as arrays because they are super efficient ways of representing ** priority queues**.

A priority queue is a queue data structure with some additional properties. Every it in a priority queue has a âpriorityâ associated with (usually a numerical value). An item with a high priority is dequeued before an item with a lower priority. If two items have the same priority, theyâre dequeued based on their order in the queue; in other words, theyâre removed according to their location in the array.

Binary heaps are super efficient for implementing priority queues because itâs very easy to know and retrieve/remove the element with the highest priority: it will always be the root node!

This one specific characteristic of heaps that weâve been referencing repeatedly is *exactly* what makes heaps the data structure of choice when it comes to priority queues! Finding the maximum of minimum value element takes a constant amount of time, which makes it efficient to dequeue an item. Similarly, because of their binary tree structure, adding or removing an element takes logarithmic time, since we eliminate half of the possible nodes with each level that we traverse to add/delete an element.

Heaps are the very abstractions that we are (inadvertently) interacting with when we uses libraries to help us handle job scheduling, background workers, and even what our machines use to handle internal tasks! That should be reason enough to love these magnificent data structures that have been around us the entire timeĂ˘âŹĹ âĂ˘âŹĹ even if we didnât know that they were there.

### 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!

- Heaps and Priority Queues, Hacker Earth
- Introduction to a Heap, Paul Programming
- Binary Heaps, Professor Victor S.Adamchik
- Priority Queues (Heaps), Professor Ananth Kalyanaraman
- Priority Queues, Professor Mary K. Vernon
- Priority Queue, GeeksforGeeks

*This post was originally published on medium.com*

This is fantastic, a wonderful class on how to teach data structures. As a professor on this very subject at a college here in Brazil, I have to congratulate you so much for the quality of the explanations. Looking forward for more content like this soon!