Heaps

Heaps are trees but there are a few properties that make them different. There are many types of heaps. Focusing more on binary heaps.

• Binary heaps have two children nodes.
• There are two types of binary heaps.
  • Min Binary Heap: Parent always smaller than child nodes.
  • Max Binary Heap: Parent always larger than child nodes.

Max Binary Heap

• Each parent has at most two child nodes.
• The value of each parent node is always greater than its child nodes.
• In a max binary heap the parent is greater than the children, but there are no guarantees between sibling nodes.
• A binary heap is as compact as possible. All the children of each node are as full as they can be and left children are filled out first.

Min Binary heaps

Min binary heaps are converse of Max binary heaps

note

Binary heaps are used to implement Priority Queue and also used with graph traversal algorithms.

tip

Binary heaps implemented using arrays to know each child. Left child will be 2n+1 and Right child will be 2n+2. Parent Node will be (n-1)/2. (floored value)

Priority Queue

Priority Queue is a data structure where each element has a priority. Elements with higher priority are served before elements with lower priority.

We will implement a min priority queue. (Lower value is higher priority)

Time Complexity

Time Complexity of insertion and removal are O(log N) and searching is O(N)

Implementation

Max Binary Heap

class MaxBinaryHeap {
  constructor() {
    values = [];
  }
  insert(val) {
    this.values.push(val);
    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 <= parent) break;
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }
  extractMax() {
    const max = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.bubbleDown();
    }
    return max;
  }
  bubbleDown() {
    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 > element) {
          swap = leftChildIdx;
        }
      }
      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx];
        if (
          (swap === null && rightChild > element) ||
          (swap !== null && rightChild > leftChild)
        ) {
          swap = rightChildIdx;
        }
      }
      if (swap === null) break;
      this.values[idx] = this.values[swap];
      this.values[swap] = element;
      idx = swap;
    }
  }
}

let heap = new MaxBinaryHeap();

Priority Queue

class Node {
  constructor(val, priority) {
    this.priority = priority;
    this.val = val;
  }
}
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.bubbleDown();
    }
    return min;
  }
  dequeue() {
    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;
    }
  }
}