Binary Heaps & Priority Queues in JavaScript
I worked at a computer repair shop where technicians processed computers in the order that they came in, according to how long they predicted the repair will take. Every day they had a running list of computers that needed to be opened and tested. However, if there was an emergency where a customer needed their data right away, we could sometimes push their computer to the front of the line.
The technicians were using a priority queue in order to handle repairs, where computers with the highest priority were handled first.
When we want to process data efficiently in computer programming, we sometimes use data structures called stacks and queues to form an order for our data. A priority queue functions somewhat like a queue in that it processes data from the front of the list (or queue), but it differs when data is added to the queue. While a traditional queue simply adds the data to the back of the line, priority queues need to ensure that the new data gets a proper place in the line according to its priority. We’ll need to use something called a binary heap to implement our priority queue.
Binary Heaps
Binary heaps are data structures that are similar to trees but have different rules.
- Each node in a binary heap has at most two children, but sibling order does not matter.
- Heaps are as compact as possible, meaning new elements are added first from top to bottom then from left to right.
- Binary heaps can have one of two formats: a Max Binary Heap or a Min Binary Heap.
- All of the child nodes in a Max Binary Heap are smaller than their parent
- All of the child nodes in a Min Binary Heap are greater than their parent
Implementation
We can use a class to implement adding and removing from the heap, but we need a way to store the values in order. What kind of data structures do we know in JavaScript that have a specific order? Arrays do! Let’s take a look at the model below:
There’s a pattern that children and parent nodes follow in our heap array. Where any index of an array is n,
- The index of the left child is 2n + 1
- The index of the right child is 2n + 2
In order to derive the index of the parent of a child we use (n-1)/2 rounded down. Using this information, we can develop our insertion and removal methods. We’ll start with a Max Binary Heap.
When inserting and removing in a binary heap, we use a method called bubbling to sort the heap. The insertion method uses two helper functions: swap and bubbleUp. The swap function swaps the elements in our values array at the two indices passed in. Once we push the new value into the array, our bubbleUp function compares the parent of the newly added element, and swaps it if the child is greater than the parent. We reassign our current index to the element’s new index if swapped, and keeps testing parents in a loop until the element fits, or we reach the root of the heap.
Our method for removal ( called removeMax above) also uses bubbling, but it’s a bit more complicated. We’ll first swap the the first and last element in our values array so that we can pop the max element off of the array and return it. Before we return it, we need to make sure our heap is properly sorted.
Our bubbleDown method then loops over the heap, checking the children nodes against our new root (the former last element in our array that we swapped). In order to bubble down properly, we first check the left child, and then the right child. If the parent is lesser than only one of the two children, we swap it with that child. However, if the parent is lesser than both of the children, we swap it with the greater value. We also need to ensure that both children exist. This is why we don’t swap until we’ve checked both the left and right child.
If you need more clarity on how bubbling works, you can step through the process on VisuAlgo.
Priority Queues
Our priority queue isn’t that different from our Max Binary Heap, we’ll just need to change a few things. The biggest change is that our values are no longer numbers but Nodes. Each node has a value and a priority, and we need to change our implementation to consider a node’s priority instead of it’s value. I changed the method names to enqueue and dequeue instead of insert and removeMax . Finally, lower priority numbers usually signify higher priority, so we’ll need to change our Max Binary Heap to a Min Binary Heap. We’ll convert all the > signs to < where we are comparing priorities.
Big O
Binary Heaps are great for processing data in a specific order — Insertion and removal are both in O(log n) time. Searching is O(n), so if you’re looking for something faster, I would suggest using a Binary Search Tree if possible.
