Hey There, today we will look at what Binary Heaps and Priority queues are in Data Structures. We are just building upon previously visited topics to make a new one. So Binary Heaps what are they ?

They are nothing complicated but just binary trees which have a much more special characteristics.  Binary heaps have two main properties we need to take note of.

Minimum Heap: a type of binary heap in which a parent – child relation consist of the value of the Parent is always smaller than that of the Child therefore the child appears to be greater than the Parent in this case. ie. Minimum Heap (Parent < Child/Children)

Maximum Heap: Here obviously the the value of the Parent is always Greater than that of the child/Children it is connected to. ie Maximum Heap (Parent > Child/Children).

Some Functions/Methods can be run equally on Binary heaps let’s look at a few and how they work.

Searching: in searching we start from the left node after to the right node after we find the parent or the root node. and to identify the left node we have to compute a formula on the array index to determine the node ie. Left Node = 2x+1 Yes we move 2 times the current node plus 1 to get to any current Node left leaf or node. To now get the Right node of a parent we compute 2x + 2 in the same event to locate the right leaf or node of the parent node.

Inserting: We can insert any node on the array into a heap three by just respecting the Heap Principle if its a minimum or a maximum and we begin any insertion from the first index of non-leaf (a parent node) which can be determine by computing the

n/2 - 1

Other operation like Deleting  Sorting etc… can be performed on the Heap as well.

Let’s take a look at a Maximum binary heap code in action.

class MaxBinaryHeap {
  constructor() {
    this.values = [];
  }
  insert(element) {
    this.values.push(element);
    //create the heap tree now
    let idx = this.values.length - 1;
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      if (element <= parent) break;
      //Swap()
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }
}

let heap = new MaxBinaryHeap();
heap.insert(41);
heap.insert(39);
heap.insert(33);
heap.insert(18);
heap.insert(27);
heap.insert(12);
heap.insert(55);

console.log(heap);

Even though a heap is binary tree  it only needs an array of values as constructed in the MaxBinaryHeap an insertion is performed by looking for that non leaf index by the length of the array excluding the last element over 2 to determine where to start building the tree from. the important thing here is to know the type of heap under construction so as to know if it goes to the right or left based on the property the heap carry and in this case we’re dealing with a MaxBinaryHeap so the top node or parent node should be greater than its children therefore we swap the values appropriately. Some use cases of a Binary heap could be for implementing a priority queue, Dijkstra’s Algorithm, Heap Sort

Now let’s talk about priority queues since it is one of the things that can be done using a binary Heap.

A priority queue is a special type of queue in which each element is associated with a priority value. And, elements are served on the basis of their priority. That is, higher priority elements are served first. if elements with the same priority occur, they are served according to their order in the queue. The value of the element itself is considered for assigning the priority. ie. The element with the highest value is considered the highest priority element and in other cases, we can assume the element with the lowest value as the highest priority element.

since this is a queue enqueuing and dequeuing will not be missing but this also take a different approach from the normal queue system which uses First in First Out Principle whereas this one prioritizes its values. let’s have a look.

class PriorityQueue {
  constructor() {
    this.values = [];
  }
  enqueue(val, priority) {
    let newNode = new Node(val, priority);
    this.values.push(newNode);
    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;
  }
}

let ER = new PriorityQueue();
ER.enqueue('taking breakfast', 5);
ER.enqueue('morning devotion', 1);
ER.enqueue('take a bath', 4);
ER.enqueue('brush teeth', 2);
ER.enqueue('jogging', 3);
//ER.dequeue(4);

console.log(ER);

Priority Queue is a lot to digest and hover around which needs some time to study. I will leave it with to read meaning out of. Actually Priority  queues can be implemented on an array, a linked list, a heap data structure, or a binary search tree but the only reason we are focused on the heap is because it provide a very efficient process when operating on priority queues.

A comparative analysis of different implementations of priority queue is given below.

Some applications of a priority queue are:
Dijkstra’s algorithm
for implementing stack
for load balancing and interrupt handling in an operating system
for data compression in Huffman code