/* PriorityQueue */
/**
 *            best & avarage   worst
 * insertion  - O(log n)     O(log n)
 * removal    - O(log n)     O(log n)
 * searching  -   O(n)         O(n)
 */

function PriorityQueue () {
  let nodes = [];

  function Node (element, priority) {
    this.element = element;
    this.priority = priority;
  }

  this.enqueue = function (element, priority) {
    const node = new Node(element, priority);
    nodes.push(node);
    bubbleUp();
  }

  this.dequeue = function () {
    const max = nodes[0];
    const last = nodes.pop();

    if (!this.isEmpty()) {
      nodes[0] = last;
      sinkDown();
    }

    return max;
  }

  function bubbleUp () {
    let index = nodes.length - 1;
    const current = nodes[index];

    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      let parent = nodes[parentIndex];

      if (current.priority >= parent.priority) break;
      [nodes[index], nodes[parentIndex]] = [nodes[parentIndex], nodes[index]];
      index = parentIndex;
    }
  }

  function sinkDown () {
    let index = 0;
    const length = nodes.length;
    const current = nodes[0];

    while (true) {
      let leftChildIndex = index * 2 + 1;
      let rightChildIndex = index * 2 + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIndex < length) {
        leftChild = nodes[leftChildIndex];
        if (leftChild.priority < current.priority) {
          // we decide where will swap
          swap = leftChildIndex;
        }
      }

      if (rightChildIndex < length) {
        rightChild = nodes[rightChildIndex];
        if (
          // if we swaped but right is smaller
          (swap  !== null &&  rightChild.priority < leftChild.priority)||
          // if we didn't swap with left, we should swap right
          (swap === null && rightChild.priority < current.priority)
        ) {
          swap = rightChildIndex;
        }
      }

      if (swap === null) break;
      // swap values like this:
      /**
       * values[index] = values[swap];
       * values[swap] = element;
       */
      // or like this:
      [nodes[index], nodes[swap]] = [nodes[swap], nodes[index]];
      // set new index
      index = swap;
    }
  }

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

  this.getValues = function () {
    return JSON.parse(JSON.stringify(nodes, null, 2));
  }
}