123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181
export type IComparator<T> = (a: T, b: T) => Number;
/** compare two values in a way that would sort them in descending order */const descendingComparator = <T>(a: T, b: T) => {  if (a > b) return -1;  else if (a < b) return 1;  return 0;};
/** * Heap that supports popping the max item. */export function MaxHeap<T>(initialValues: T[] = []) {  return Heap(descendingComparator, initialValues);}
/** compare two values in a way that would sort them in ascending order */const ascendingComparator = <T>(a: T, b: T) => {  if (a < b) return -1;  else if (a > b) return 1;  return 0;};
/* * Heap that supports popping the min item. */export function MinHeap<T>(initialValues: T[] = []) {  return Heap(ascendingComparator, initialValues);}
/** * A Heap: i.e. a collection of sorted values that supports the following operations: * * buildHeap - Create Heap from initialValues in O(n) time * * length - get number of items in collection in O(1) time * * peek - get first item in collection in O(1) time * * pop - remove the first item in collection in O(log(n)) time * * push - add a new item to the collection in O(log(n)) time *  * Space complexity is O(n). *  * @param initialValues {Array} Initial values to add to the Heap * @param comparator {(a: T, b: T) -> Number} Function to compare values. Determines which items can be peeked/popped. *  Same behavior expectations of comparator argument to Array#sort. */export function Heap<T>(comparator: IComparator<T>, initialValues: T[] = []) {  /**   * Store all values in this array.   * Array indexes are determined by position in the binary tree   * at (2 * level) + indexAtLevel, where both level and indexAtLevel start at 0   */  buildHeap(initialValues, comparator);  const array: T[] = initialValues;  return {    get length() {      return array.length;    },    peek,    pop,    push,  };
  /**   * @returns the minimum value of all items.   */  function peek() {    return array[0];  }  /**   * Remove the minimum value from the collection.   * @returns The minimum value that was removed   */  function pop() {    swap(array, 0, array.length - 1);    const popped = array.pop();    siftDown(array, 0, comparator);    return popped;  }  /**   * Add a new value.   * @param value The value to add   */  function push(value: T) {    array.push(value);    siftUp(array, array.length - 1, comparator);  }}
/** Given an index in an array storing a binary tree, return the index of its left child. There may be no value at that index. */function leftIndex(index: number) {  return (2 * index) + 1;}/** Given an index in an array storing a binary tree, return the index of its right child. There may be no value at that index. */function rightIndex(index: number) {  return (2 * index) + 2;}/** Given an index in an array storing a binary tree, return the index of its parent */function parentIndex(index: number) {  return Math.floor((index - 1) / 2);}
/** * Given an array of values, order the items so they represent a MinHeap binary tree. */function buildHeap<T>(initialValues: Array<T>, comparator: IComparator<T>) {  const lastChild = initialValues.length - 1;  const firstParent = parentIndex(lastChild);  for (let i = firstParent; i >= 0; i--) {    siftDown(initialValues, i, comparator);  }}
/** * Move the value at the provided index down in the binary tree until it satiesfies the Heap property. * (i.e. move it down until all its descendents are larger that it) * @param array {Array} An array of values representing a binary tree that has the Heap property * @param comparator {Function} comparator to use to sort values (same as argment to Array#sort) * @param index {Number} index of value to siftDown */function siftDown<T>(  array: Array<T>,  index: number,  comparator: IComparator<T>,) {  while (index < array.length) {    let left = leftIndex(index);    let right = rightIndex(index);    let hasLeft = left < array.length;    let hasRight = right < array.length;    if ((!hasLeft) && (!hasRight)) {    }    let minChild;    if ((!hasLeft) && (!hasRight)) {      // node with index is a leaf. nothing more to do      return;    } else if (!hasLeft) {      minChild = right;    } else if (!hasRight) {      minChild = left;    } else {      // have both left and right      minChild = (comparator(array[left], array[right]) < 0) ? left : right;    }    if (comparator(array[index], array[minChild]) > 0) {      swap(array, index, minChild);      index = minChild;    } else {      return;    }  }}
/** * Move the value at the provided index up in the binary tree until it satiesfies the Heap property. * (i.e. move it up until all its descendents are greater than it) * @param array {Array} An array of values representing a binary tree that has the Heap property * @param index {Number} index of value to siftUp * @param comparator {Function} comparator to use to sort values (same as argment to Array#sort) */function siftUp<T>(array: Array<T>, index: number, comparator: IComparator<T>) {  while (index) {    const parent = parentIndex(index);    // min heap    if (comparator(array[index], array[parent]) < 0) {      swap(array, index, parent);    }    index = parent;  }}
/** * Swap the values at two indexes in the array. * @param array  * @param i {Number} first index to swap * @param j {Number} second index to swap */function swap<T>(array: Array<T>, i: number, j: number) {  const temp = array[i];  array[i] = array[j];  array[j] = temp;}