! JavaScript Heap & Priority Queue.md

JavaScript Heap & Priority Queue

• GenericHeap
• MinHeap
• MaxHeap
• PriorityQueue

generic-heap.js

class GenericHeap 
{
  constructor(comparer, items)
  {
    this._heap = [];
    this._comparer = comparer;
    if (items) {
      for(const item of items)
      {
        this.insert(item);
      }
    }
  }

  isEmpty() 
  {
    return this._heap.length == 0;
  }

  size() {
    return this._heap.length;
  }
  
  length() {
    return this._heap.length;
  }

  peek() {
    return this._heap.length === 0 ? null : this._heap[0];
  }

  rawHeap() 
  {
    return this._heap;
  }

  insert(item)
  {
    this._heap.push(item);
    let i = this._heap.length -1;
    while(i > 0) {
      const p = this._parent(i)
      if(this._comparer(this._heap[p], this._heap[i])) break;
      const tmp = this._heap[i]
      this._heap[i] = this._heap[p]
      this._heap[p] = tmp
      i = p
    }
  }
  
  push(item)
  {
    this.insert(item);
  }
      
  pop()
  {
    if(this._heap.length == 0) return null
    
    this._swap(0, this._heap.length - 1)
    const item = this._heap.pop();

    let current = 0
    while(this._hasLeft(current)) {
      let smallerChild = this._left(current)
      if(this._hasRight(current) && this._comparer(this._heap[this._right(current)], this._heap[this._left(current)])) 
        smallerChild = this._right(current)

      if(!this._comparer(this._heap[smallerChild], this._heap[current])) break

      this._swap(current, smallerChild)
      current = smallerChild
    }

    return item;
  }

  print()
  {
    console.log(">>> -= HEAP =-");
    console.log(`>>> COUNT: ${this.length()}`);
    for(const x of this._heap)
    {
      console.log(`|- ${JSON.stringify(x)}`);
    }
    console.log(">>> --------------------");
  }


  /*****/
  _parent(index) {
    return Math.floor((index - 1) / 2);
  }

  _left(index) {
    return 2 * index + 1;
  } 
  _right(index) {
    return 2 * index + 2;
  }
  _hasLeft(index) { 
    return this._left(index) < this._heap.length;
  }
  _hasRight(index) {
    return this._right(index) < this._heap.length;
  }

  _swap(a, b)
  {
    const tmp = this._heap[a];
    this._heap[a] = this._heap[b];
    this._heap[b] = tmp;
  }
}

max-heap.js

class MaxHeap extends GenericHeap
{
  constructor(items)
  {
    super((a, b) => a > b, items);
  }
}

min-heap.js

class MinHeap extends GenericHeap
{
  constructor(items)
  {
    super((a, b) => a < b, items);
  }
}

priority-queue

priority-queue