Binary Heaps in JavaScript
As a continuation of our series on Data Structures in this article, we will be discussing Binary Heaps and I will be including code to implement a Binary Heap in JavaScript. As per my previous posts, Colt Steele’s Udemy course has been invaluable in my learning process.
What is a Heap?
In computer science, a heap is a tree-based data structure that satisfies the heap property. A max heap is a tree where each parent node is larger than its children similarly, a min heap is a tree where each parent node is smaller than its children. A binary heap, similar to a binary tree is a structure that can have 2 children at most.
A binary heap is stored as compact as possible. All the children of each node are as full as they can be and left children are filled out first. Siblings, nodes with the same parent have no implied order.
What are binary heaps used for?
Heaps are used to implement priority queues, an abstract data type that will come back in future posts. A priority queue will be used when we traverse graphs but at this moment what is a priority queue?
In a standard queue that we have discussed, elements leave the queue on a FIFO basis. The order with which the element was placed into the queue is preserved. In a priority queue, each element contains a priority. We can assign priorities to non-integer elements and have the priority queue return the highest priority element or lowest priority element when we perform the ‘dequeue’ operation.
One of the best real-world examples I’ve come across that has helped me understand a priority queues role is an emergency room queue. At any given moment patients come in and out of an ER with various ailments. Nurses and doctors perform triage and effectively assign a priority to each patient that comes through their doors. A patient with a sprained ankle may be in discomfort but may be priority 3 to two other patients one suffering from a gunshot wound (priority 1) and one with a broken leg (priority 2).
Depending on the urgency of each situation the patient with the top priority, the patient with the gunshot wound, will be seen first. As this heap grows with each patient that is enqueued we can be sure that patients with the utmost priority will be dequeued first. This property can be used for other abstract examples like operating system schedulers, A* search, and routing. The last 2 examples are related to graph traversal and will be the main use of priority queues for our study purposes.
Fortunately, heaps can be stored as an array or list.
- Left child: 2n+1
- Right child: 2n+2
- n being the index of the parent node
For example, the index of 17 is 3 in the above list. We can determine its left child by performing the calculations: 2(3) + 1 = 7 and its right child 2(3)+2 = 8. Its children are located at array[7] and array[8] which coincides with the above example.
For simple problems, a list or an array can be used along with the above logic to implement a priority queue just note that the use of arrays in JavaScript for larger data sets are expensive implementations.
Implementing a Priority Queue // Max Binary Heap
In this section, I will be discussing the two main methods related to a Binary Heap, enqueue and dequeue. If you would like to view the entire implementation click here.
Adding to a Max Binary Heap (enqueue) :
- Automatically add to the end of the array and have the element ‘bubble up’
- Using the parent — child relationship we can compare the latest addition
- If the child is larger than the parent, swap the 2 values.
Removing from a Max Binary Heap (dequeue):
- Remove the root (this is the value with the highest priority)
- Replace the root with the most recently added element (the last element)
- Adjust the heap with a ‘sink down function
- Similar to the enqueue method we will make use of the parent — child relationship noted above (l: 2n+1, r: 2n+2) to compare values of the root to its children until the new root percolates down to its proper spot.
I included two helper functions (bubbleUp and sinkDown) which were taught in the Colt Steele course but we could have coded it straight out without the use of helper functions, it is just more readable, for me at least to do it this way.
With these 2 methods, we can add to our Priority Queue and return the min or max depending on what we determine the priority to be.
BigO of Binary Heaps
One of our favorite sections is discussing the BigO of data structures. What’s the point of implementing a Binary Heap over an array? Time complexity is greatly reduced when making use of a binary heap over an array. Insertion and Deletion in a binary heap are very fast, both operations are done in O(logn) compared to O(n) when using arrays. It is very worth implementing a binary heap if your goal is to constantly add and delete nodes.
Thank you for keeping up with me thus far! Next week we will be discussing Hash Tables.
Resources:
