mail task 2

by evgkch

JavaScript

// @flow

// type Node<T> = { value: T, p: number };

/* interface IPriorityQueue<T> {
  list: Array<Node<T>>;
  insert(value: T, p: number): void;
  getMax(): ?T;
  empty(): boolean;
  extractMax(p: number): ?T;
  remove(i: number): void;
  changePriority(i: number, p: number): void;
} */

// i: number
// j: number
// @returns: void
function swap(i, j) {
  const oldIVal = this.list[i];
  this.list[i] = this.list[j];
  this.list[j] = oldIVal;
}

// i: number
// @returns: number
function getParent(i) {
  return Math.floor((i - 1) / 2);
}

// i: number
// @returns: number
function getLeftChild(i) {
  return 2 * i + 1;
}

// i: number
// @returns: number
function getRightChild(i) {
  return 2 * i + 2;
}

// i: number
// @returns: number
function getPriority(i) {
  if (!this.list[i])
    return NaN;

  return this.list[i].p;
}

// i: number
// @returns: T
function getValue(i) {
  if (!this.list[i])
    return;  // 
  return this.list[i].value;
}

// i: number
// @returns: void
function shiftUp(i) {
  let p = getParent.call(this, i);
  while (i > 0 && getPriority.call(this, p) < getPriority.call(this, i))
  {
    swap.call(this, p, i);
    i = p;
    p = getParent.call(this, i);
  }
}

// i: number
// @returns: void
function shiftDown(i) {
  let maxIndex = i;
  let l = getLeftChild.call(this, i);
  let r = getRightChild.call(this, i);

  if (l < this.list.length - 1 && getPriority.call(this, l) > getPriority.call(this, maxIndex))
    maxIndex = l;

  if (r < this.list.length - 1 && getPriority.call(this, r) > getPriority.call(this, maxIndex))
    maxIndex = r;

  if (i != maxIndex)
  {
    swap.call(this, i, maxIndex);
    shiftDown.call(this, maxIndex);
  }
}

class PriorityQueue {
	// list: Array<Node<T>>
  // @returns PriorityQueue<T>	
  static build(list) {
    const heap = new PriorityQueue;
    list.forEach(item =>heap.insert(item.value, item.p));
    /* heap.list = list;
    for (let i = getParent(heap.list.length); i > 0; i--)
      shiftDown.call(heap, i);...