Queueing task is one of common problem that you might encounter as programmer. Whether this queue is caused by the limited resources, or maybe just because of the use case to solve a problem. The very basic queue case is a First in First out/Last in Last out, which in this case you may simply use either a List/Array or a Linked List structure. Which the better i think is depends on how big the queue would be. But, there's another use case that i found, it's to add a prioritization parameter to determine which item need to be out first. Then, comes the concept of something called Priority Queue.

One of the most common data structure to solve Priority Queue is to use a heap. A heap is a tree-based structure that have an extra rules or property based on the variation. The basic and fundamental structure type of heap is called Binary Heap. This type of heap is having a structure of a complete Binary Tree but having two extra rules to it.

The rules of a Binary Heap would include:

• Complete binary tree, the tree node in each level should be filled except for the last level, which should be filled from left to right.
• Satisfy a priority rule property, each node children should consistently have larger or smaller priority over its parent. If the problem require a higher priority queue to comes first, then the parent priority needs to be larger than all of its children, this type is called a max-heap, and an opposite case where the parent is always smaller than its children is called a min-heap type.

From image above you can see the example of a valid and invalid Binary Heap structure with min-heap type. The left, is an example a structure that satisfy all the rules. Whereas the right one doesn't satisfy both rule. It can be seen that this tree have 4 level, but there's a null value on the third level. It also can be found that in the orange node, those nodes doesn't follow the min-heap rule, which the parent should be smaller than its children.

Create A Priority Queue With Binary Heap

After understanding the concept, now comes the question, how to create a priority queue using binary heap ? or how to turn a basic FIFO/LIFO queue into a priority queue ? Then, here comes the fun part to write some codes to build it. I will create an example of a max-heap binary heap.

First, we need to understand that there's one important characteristics of this binary heap. That a binary heap structure allow us to not necessarily create a binary tree structure, we actually able to use a 1D array to create it, with tree root as the first array element and the last tree node as the last array element. This characteristics is the reason of the first binary heap rule. The array structure allow us to effectively access any nodes in the heap, while also effective at manipulating it. We also able to easily find the index of a parent nodes, and its children. The relation can be described with

1left_child = (index * 2) + 1
2right_child = (index * 2) + 2
3parent_node = floor((index - 1) / 2)

After knowing those characteristics, now we can start to actually write some code. Let's start with how to add an element to this Binary Tree Queue. We can do it by start adding a new tree node, which also mean push a new element to the binary heap array. Then, we will need to evaluate whether this new node satisfy the first rule or not by continuously checking if this new node smaller than its parent, if not then we need to swap this node and its parent. We need to check again to the next tree level, until the parent is bigger or this node become the root node.

1function shiftUp(heap, index) {
2  // Get the index of parent node
3  const parentIdx = Math.floor((index - 1) / 2);
4
5  // Check if this heap is not at root and is bigger than the parent
6  if (parentIdx >= 0 && heap[index] > heap[parentIdx]) {
7    // If satisfy the condition, swap the heap and parent node
8    [heap[parentIdx], heap[index]] = [head[index], heap[parentIdx]];
9
10    // Recursively run the same operation until the condition is not met;
11    heap = shiftUp(heap, parentIdx);
12  };
13
14  return heap;
15};
16
17function add(heap, value) {
18  // Push the new value to last array element
19  heap.push(value);
20
21  // Check and mutate the heap with shiftUp function
22  heap = shiftUp(heap, heap.length - 1);
23
24  return heap;
25}

After able to adding value to the heap, the other important function is to extract a value and take it out from the queue. With the this binary heap structure, we know that the root of the tree will always be the value that we want to take out first. Getting this value will be easy, with indexing the first element of array. But, extracting it will require more effort. Since if we extract it right away, we will lose our root node and breaking the structure.

A trick to extract the root is to switch the root with the last node, since popping the last node is the only way to not break the first rule. But, this can potentially make the structure violate the second rule. That's where we need another step, we need to swap this new root node with its bigger child, until this node placed on the last level or there's no child of this node that have bigger value. This operation is exactly the opposite of "shiftUp" function that we create before.

1function shiftDown(heap, index) {
2  // Get children node index
3  const leftChildIdx = (index * 2) + 1;
4  const rightChildIdx = (index * 2) + 2;
5
6  // Check if there's any children that have bigger value
7  if (
8    (leftChildIdx < heap.length && heap[index] < heap[leftChildIdx])
9    || (rightChildIdx < heap.length && heap[index] < heap[rightChildIdx])
10  ) {
11    // Find which children has the bigger value, this will also return left index if the right index undefined
12    const smallerChildIdx = heap[rightChildIdx] > heap[leftChildIdx] 
13      ? rightChildIdx : leftChildIdx;
14
15    // Swap the node with the bigger children
16    [[heap[smallerChildIdx], heap[index]]] = [heap[index], heap[smallerChildIdx]];
17
18    // Recursively do the opartion until rule satisfied
19    heap = shiftDown(heap, smallerChildIdx);
20  };
21
22  return heap;
23};
24
25function extract(heap) {
26  // Swap the root and last node
27  [heap[0], heap[heap.length - 1]] = [heap[heap.length - 1], heap[0]];
28
29  // Extract the root value (which already located as last node)
30  const rootVal = heap.pop();
31
32  // Fix the structure to satisfy the rule
33  shiftDown(heap, 0);
34
35  return heap;
36}

With that code we basically already cover all main functionality of a Binary Heap. But, to put in extend, let's add a case where we want to update some node value and to build a Binary Heap from any array, this allow us to turn a FIFO/LIFO queue into a Priority Queue.

Updating the node value will require two steps. First is definitely to swap the node value, the second one is to make the tree structure to satisfy the rule. With knowing how "add" and "extract" function work, you might already have the intuition how we can do the second step.

The second step is either a "shiftUp" or "shiftDown" operation, this depends with if the new value is bigger or smaller that the old value. If the new value is bigger, then it must already bigger that all nodes bellow, but it might be bigger that the parent too, so we need to do a "shiftUp" operation. In the opposite if the value is smaller, then it must be smaller that all the node above it. But, it might be smaller than its children, so we need to do a "shiftDown" operation.

1function update(heap, index, value) {
2  // Check is new value bigger or smaller
3  const isBigger = value > heap[index];
4
5  // Update the heap value
6  heap[index] = value;
7
8  // Do the necessary fix operation
9  if (isBigger) {
10    heap = shiftUp(heap, index);
11  } else {
12    heap = shiftDown(heap, index);
13  }
14
15  return heap;
16}

The last problem that will need to cover is to build a Priority Queue using an array input. To do this, we basically only need to create a make the array to satisfy the second rule. Since, as long the array doesn't have an empty value, then it already satisfy the first rule. We can utilize the "shiftUp" and "shiftDown" to do this, but here i will chose the "shiftDown" operation since we can do a more effective operation. The concept is to make every sub-tree starting from smallest to satisfy the rule. This can be done by iterating from the back of the array, and do "shiftDown" operation on that index.

1function build(arr) {
2  // Iterate through the heap from the back
3  for (let i=arr.length - 1;i>=0;i--) {
4    // Make the subtree become valid Binary Heap
5    arr = shiftDown(arr, i);
6  };
7
8  return arr;
9}

That's all of the feature we can create with this Binary Heap to create a Priority Queue. Of course, we can make all those function to become a Binary Heap class to make the operation easier. Here, at the end of this article i will put the full class of this Binary Heap.

Binary Heap Full Code

1class BinaryHeapQueue {
2  heap = [];
3
4  build(arr) {
5    this.heap = arr;
6
7    for (let i=arr.length - 1;i >= 0;i--) {
8      this.shiftDown(i);
9    };
10  };
11
12  add(value) {
13    this.heap.push(value);
14    this.shiftUp(this.heap.length - 1);
15  };
16
17  extract() {
18    this.swap(0, this.heap.length -1);
19    const rootVal = this.heap.pop();
20    this.shiftDown(0);
21    
22    return rootVal;
23  };
24
25  shiftUp(index) {
26    const parentIdx = Math.floor((index - 1) / 2);
27  
28    if (parentIdx >= 0 && this.heap[index] > this.heap[parentIdx]) {
29      this.swap(parentIdx, index);
30      this.shiftUp(parentIdx);
31    };  
32  };
33
34  shiftDown(index) {
35    const leftChildIdx = (index * 2) + 1;
36    const rightChildIdx = (index * 2) + 2;
37  
38    if (
39      (leftChildIdx < this.heap.length && this.heap[index] < this.heap[leftChildIdx])
40      || (rightChildIdx < this.heap.length && this.heap[index] < this.heap[rightChildIdx])
41    ) {
42      const smallerChildIdx = this.heap[rightChildIdx] > this.heap[leftChildIdx] 
43        ? rightChildIdx : leftChildIdx;
44  
45      this.swap(smallerChildIdx, index);
46      this.shiftDown(smallerChildIdx);
47    };
48  };
49
50  update(index, value) {
51    const isBigger = value > this.heap[index];  
52    this.heap[index] = value;
53  
54    if (isBigger) {
55      this.shiftUp(heap, index);
56    } else {
57      this.shiftDown(heap, index);
58    };
59  };
60
61  swap(index1, index2) {
62    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
63  }
64}