max heap

What are Heaps Used For? And What Do Heaps Do?

Heaps are complex sounding but simple data structures once you break them down.

Let’s dive in.

What are Heaps?

Heaps are essentially binary tree data structures. However, there’s one thing that’s different about heaps than just any regular binary tree: heaps can be used efficiently as priority queues.

Priority queues are abstract data structures that act as queues except that these aren’t normal queues.

In priority queues, the element that’s popped off the front of the queue is the element with the highest priority.

This brings us to the next topic of heaps…

Max Heaps and Min Heaps

what are heaps used for

Max heaps are one form of heaps (priority queues) whose priority is determined by the highest integer value. The integer with the highest integer value is placed at the top of the heap (root).

Also, if you scan through the heap, every node has a greater integer value than its two child nodes.

what are heaps used for

On the other hand, min heaps are another form of heaps whose priority is determined by the lowest integer value. Opposite of max heaps, the integer with the lowest integer value is placed at the top of the heap.

In addition, if you scan through the heap, every node is less than the integer values of both of its child nodes.

Time Efficiency

The great thing about heaps is that they allow you to search for the element with the highest priority in O(1) time. Pretty fast, huh?

However, searching for any other element in the heap is O(n) because the nodes across the heap aren’t ordered like they would be in a binary search tree.

In addition, heaps have good deletion time. For instance, if you want to remove the value at the top of a heap, it will take O(logn) time.

The reason that deleting the top value isn’t constant time is because after the top value is removed, the remaining heap must be heapified.

Heapify In Action

Heapify is a strange word to say the least. When you heapify, several things are happening.

First of all, the element at the top of the heap is removed.

Second of all, the element at the right most bottom of the heap is removed and is placed at the root. We’ll call this element the heapifiedElement.

Next, the heapifiedElement is compared to its children. Assuming we’re using a max heap, if the heapifiedElement is less than any of its child nodes, the heapifiedElement is swapped with the largest child node.

This process of comparing and swapping the heapified element is known as bubbling down.

Now, the heapifiedElement will continue to bubble down the heap until it’s greater than both of its children.

At this point, the heapified process is done and it has taken O(logn) time worst case.

Interestingly enough, the heapsort algorithm is simply n iterations of heapify!

Can you guess what heapsort’s time complexity is? (Answer’s at the end of the article).

If you still don’t understand how heapify works, check out this visual animation and watch the delete function.

Insertion

Insertion in a binary heap is similar to heapify except instead of bubbling down, we bubble up.

When you insert an element, you simply insert the element at the most bottom right part of our heap.

Next, the element bubbles up until it is placed into its appropriate position in the heap.

Worst case, insertion is O(logn) time where n is the number of elements in the heap.

Implementation

The interesting thing about heaps is that they don’t need to be implemented with binary trees.

Using a binary tree for heaps is a great way to model the heap data structure; it’s simple and it’s intuitive.

what are heaps used for

However, there’s another data structure that can be used to implement a binary heap, and that’s the array data structure.

The way a heap is stored in an array is that, you place the root in the heap at the zeroth index.

Every sequential value in the array is the left to right order if you’re scanning down the heap, which is shown in the image above.

To find the children of any given value in a heap, all you do is look at the 2i + 1 and 2i + 2 indices in the array, where i is the current index in the array.

To find the parent of any given node, look at the i / 2 index in the array, where i is the current index.

Why Use an Array?

Arrays are used over actual trees because trees are inefficient. Here’s why.

Binary tree implementations of heaps contain next pointers that point to nodes within the tree.

Each of these nodes cost memory and if you have limited memory then this can be a bottleneck to performance.

With arrays, you don’t have as much memory overhead as the tree because arrays simply don’t use pointers.

What are Heaps Used For?

Heaps are important because they allow you to search and select the element with the highest priority at any given time.

This feature is very important and it’s found in many places.

For instance, heaps are used for schedulers. They’re also used in GPS routing (Dijkstra’s algorithm).

If it weren’t for heaps, GPS routing wouldn’t be as time efficient and you would be pissed off waiting for your GPS to directions to load.

Remember how much greater your life is because of this simple data structure.

Final Thoughts

Heaps are simple data structures that you can use any time you want to write your own GPS routing software or when you need fast access to the element with the highest priority.

P.S. If you think “heap” is a funny word for a data structure, then you may like my newsletter. Sign up now.

By the way, the answer to the heapsort question is O(nlogn) time.

binary_search_tree

How Trees Work

We continue our journey into the world of computer science data structures. Trees are graphs that consists of nodes that are grouped together in a hierarchical structure. These hierarchical structures typically represent the relationships between all the nodes in a tree. Classifications Tree nodes typically are considered child nodes, parent nodes, or leaf nodes. Parent […]

How Graphs Work

Graphs are interesting data structures that you encounter in software that you use every day. Graphs are used by top tech companies, such as Facebook, Twitter, and LinkedIn to represent relationships in social networks. However, the scope of graphs goes beyond social networks. Graphs are great for representing relationships. Because of this graphs can be implemented […]

The Software Engineer Framework: 8 Ways to Become a Better Software Engineer

Becoming a great software engineer is a never ending and sometimes bumpy journey. To make your software engineer journey a less bumpy one, it’s appropriate that you adopt a framework that puts you in a position to make better software. The software engineer framework is a resilient one and if you apply all of the facets […]