Binary heap

• Very similar to a binary search tree, but with some different rules
• MaxBinaryHeap: parent nodes are always larger than child nodes
  • Only rule : A child must be smaller than the parent.
• MinBinaryHeap: parent nodes are always smaller than child nodes
• left child is added and then a right child.
• No guarantees between sibling nodes (So again, no implied ordering between siblings.)
• used to implement Priority Queues, which are very commonly used data structure
• used with graph traversal algorithms

 

 

 

Adding to a MaxBinaryHeap

1. Add to the end

2. Bubble up

 

class MaxBinaryHeap {
  constructor() {
    this.values = [41, 39, 33, 18, 27, 12];
  }
  insert(element) {
    this.values.push(element);
    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;
    }
  }
}

let heap = new MaxBinaryHeap();