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