Binary Heaps and Priority Queues
Continuation of The Data Structure series. I’ll like to discuss Binary heaps and by extension Priority Queues. Buckle up buckaroos this one is a doozy.
Binary Heaps are used to implement priority queues, which are very common. Binary Heaps are very similar to binary search trees. Heaps are a type of tree by which each node only has two children. But with Binary Heaps, each node must be filled before creating a new child node, starting with the left node. So every parent node must have two children before creating a grandchild. Wow! starting off rough. Please visit visualgo.net to get a better picture because after this we’re going to be representing Heaps as arrays.
There are two types of Binary Heaps, Min and Max. A max binary heap the parent nodes are larger meaning if we have a binary heap of numbers, the largest number is the root of the heap and the numbers decrease as we go further down the tree. Min binary heaps the parent nodes are smaller than the child nodes. We’re going to use max heaps for our example of implementation of the data structure below.
First, like every data structure we create in Javascript we need to declare our class.
class MaxBinaryHeap {
// There is no node class we need to declare. /* The only thing that we have in our constructor method is our values variable saved as an array.
*/constructor(){
this.values = [];
};// First let's write our function to insert a element to our Heap.
/* This function accepts a value and pushes the value into the array of values.*/insert(element){
this.values.push(element);
this.bubbleUp();/* Notice the bubbleUp invocation this function sorts the element in the proper index of the array. It could be written in place of the invocation. Let's take a closer look at this function in the section below */
}}bubbleUp(){/*
Create a variable called 'idx' which is the length of the values property - 1 Create a variable called parentIndex which is the floor of
(index - 1)/2We must discuss the math of the Binary Heap.To find the index of a parent element in the heap array, we subtract 1 from the child node index and we divide that by 2.
(n - 1)/2
*/ let idx = this.values.length - 1;
//Create a variable called index which is the length of the values property - 1
const element = this.values[idx];// Keep looping as long as the values element at the parent Index is less than the values element at the child index. while(idx > 0){
let parentIdx = Math.floor((idx - 1)/2);// Create a variable called parentIndex which is the result floored of (index - 1)/2 let parent = this.values[parentIdx];// Swap the values of the values element at the parentIndex with the value of element property at the child index. if(element <= parent) break;
this.values[parentIdx] = element;
this.values[idx] = parent;// Set the index to be the parentIndex, and start over.
idx = parentIdx;
}
}
That was a very difficult function, feel free to copy and paste. Next we must discuss how to remove the top node or “Extract Max”. We are going to remove the root. replace the most recently added and adjust the array, which just like bubbleUP, we’re going to call it sinkDown().
extractMax(){
const max = this.values[0];
const end = this.values.pop();
if(this.values.length > 0 ){
this.values[0] = end;
this.sinkDown();
}
return max;
}This section of code does what the previous section mentions removing the root, replace the most recently added and sinkDown().
sinkDown(){// Your parent index starts at 0 (the root)
let idx = 0;
const length = this.values.length;
const element = this.values[0];/* To find the left child node of a parent node it's 2 * index of the parent node + 1For the right child node it's 2 * index + 2 if we are looping through using these equations we must make sure that they don't go out of bounds.*/ while(true){// The below lines finds the leftChild and rightChild nodes.
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let leftChild, rightChild;
let swap = null;// If the left or right child is greater than the element… swap. If both left and right children are larger, swap with the largest child.
if(leftChildIdx < length){
leftChild = this.values[leftChildIdx];
if(leftChild > element){
swap = leftChildIdx
}
}
if(rightChildIdx < length){
rightChild = this.values[rightChildIdx];// The child index you swapped to now becomes the new parent index.
if(
(swap === null && rightChild > element) ||
(swap !== null && rightChild > leftChild)
){
swap = rightChildIdx;
}
}// Keep Looping and swapping until neither child is larger than the element if(swap === null) break ;
this.values[Idx] = this.values[swap];
this.values[swap] = element;
}// Keep the old root! }
Before we continuing to our Priority Queue portion the Big O of the Binary Heap is O(log n) for insertion and removal.
A Priority Queue is a data structure where each element has a priority. Elements with higher priorities are served before elements with lower priorities. They are a separate concept from heaps and they’re different ways to implement them. But the most famous way is with heaps. We are going to implement with a min heap.
We’re going to use the same class with different conditionals as our max binary heap. We’re going to have a node class and the Node class will have a value and a priority number. Below, we have our insert and remove functions with new names enqueue and dequeue. Same bubbleUp function and sinkDown functions. The only difference is we’re going to organize the heap with our priority such as element.priority instead of element alone.
class PriorityQueue {
constructor(){
this.values = [];
}
enqueue(val, priority){
let newNode = new Node(val, priority);
this.values.push(newNode);
this.bubbleUp();
}
bubbleUp(){
let idx = this.values.length - 1;
const element = this.values[idx];
while(idx > 0){
let parentIdx = Math.floor((idx - 1)/2);
let parent = this.values[parentIdx];
if(element.priority >= parent.priority) break;
this.values[parentIdx] = element;
this.values[idx] = parent;
idx = parentIdx;
}
}
dequeue(){
const min = this.values[0];
const end = this.values.pop();
if(this.values.length > 0){
this.values[0] = end;
this.sinkDown();
}
return min;
}
sinkDown(){
let idx = 0;
const length = this.values.length;
const element = this.values[0];
while(true){
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let leftChild,rightChild;
let swap = null; if(leftChildIdx < length){
leftChild = this.values[leftChildIdx];
if(leftChild.priority < element.priority) {
swap = leftChildIdx;
}
}
if(rightChildIdx < length){
rightChild = this.values[rightChildIdx];
if(
(swap === null && rightChild.priority element.priority) ||
(swap !== null && rightChild.priority < leftChild.priority)
) {
swap = rightChildIdx;
}
}
if(swap === null) break;
this.values[idx] = this.values[swap];
this.values[swap] = element;
idx = swap;
}
}
}class Node {
constructor(val, priority){
this.val = val;
this.priority = priority;
}
}
Thanks for reading!
