123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187
// Copyright 2018-2022 the Deno authors. All rights reserved. MIT license./** This module is browser compatible. */
import { descend } from "./_comparators.ts";export * from "./_comparators.ts";
/** Swaps the values at two indexes in an array. */function swap<T>(array: T[], a: number, b: number) {  const temp: T = array[a];  array[a] = array[b];  array[b] = temp;}
/** Returns the parent index for a child index. */function getParentIndex(index: number) {  return Math.floor((index + 1) / 2) - 1;}
/** * A priority queue implemented with a binary heap. The heap is in descending * order by default, using JavaScript's built-in comparison operators to sort * the values. * * | Method      | Average Case | Worst Case | * | ----------- | ------------ | ---------- | * | peek()      | O(1)         | O(1)       | * | pop()       | O(log n)     | O(log n)   | * | push(value) | O(1)         | O(log n)   | * * @example * ```ts * import { *   ascend, *   BinaryHeap, *   descend, * } from "https://deno.land/std@$STD_VERSION/collections/binary_heap.ts"; * import { assertEquals } from "https://deno.land/std@$STD_VERSION/testing/asserts.ts"; * * const maxHeap = new BinaryHeap<number>(); * maxHeap.push(4, 1, 3, 5, 2); * assertEquals(maxHeap.peek(), 5); * assertEquals(maxHeap.pop(), 5); * assertEquals([...maxHeap], [4, 3, 2, 1]); * assertEquals([...maxHeap], []); * * const minHeap = new BinaryHeap<number>(ascend); * minHeap.push(4, 1, 3, 5, 2); * assertEquals(minHeap.peek(), 1); * assertEquals(minHeap.pop(), 1); * assertEquals([...minHeap], [2, 3, 4, 5]); * assertEquals([...minHeap], []); * * const words = new BinaryHeap<string>((a, b) => descend(a.length, b.length)); * words.push("truck", "car", "helicopter", "tank"); * assertEquals(words.peek(), "helicopter"); * assertEquals(words.pop(), "helicopter"); * assertEquals([...words], ["truck", "tank", "car"]); * assertEquals([...words], []); * ``` */export class BinaryHeap<T> implements Iterable<T> {  #data: T[] = [];  constructor(private compare: (a: T, b: T) => number = descend) {}
  /** Creates a new binary heap from an array like or iterable object. */  static from<T>(    collection: ArrayLike<T> | Iterable<T> | BinaryHeap<T>,  ): BinaryHeap<T>;  static from<T>(    collection: ArrayLike<T> | Iterable<T> | BinaryHeap<T>,    options: {      compare?: (a: T, b: T) => number;    },  ): BinaryHeap<T>;  static from<T, U, V>(    collection: ArrayLike<T> | Iterable<T> | BinaryHeap<T>,    options: {      compare?: (a: U, b: U) => number;      map: (value: T, index: number) => U;      thisArg?: V;    },  ): BinaryHeap<U>;  static from<T, U, V>(    collection: ArrayLike<T> | Iterable<T> | BinaryHeap<T>,    options?: {      compare?: (a: U, b: U) => number;      map?: (value: T, index: number) => U;      thisArg?: V;    },  ): BinaryHeap<U> {    let result: BinaryHeap<U>;    let unmappedValues: ArrayLike<T> | Iterable<T> = [];    if (collection instanceof BinaryHeap) {      result = new BinaryHeap(        options?.compare ?? (collection as unknown as BinaryHeap<U>).compare,      );      if (options?.compare || options?.map) {        unmappedValues = collection.#data;      } else {        result.#data = Array.from(collection.#data as unknown as U[]);      }    } else {      result = options?.compare        ? new BinaryHeap(options.compare)        : new BinaryHeap();      unmappedValues = collection;    }    const values: Iterable<U> = options?.map      ? Array.from(unmappedValues, options.map, options.thisArg)      : unmappedValues as U[];    result.push(...values);    return result;  }
  /** The amount of values stored in the binary heap. */  get length(): number {    return this.#data.length;  }
  /** Returns the greatest value in the binary heap, or undefined if it is empty. */  peek(): T | undefined {    return this.#data[0];  }
  /** Removes the greatest value from the binary heap and returns it, or null if it is empty. */  pop(): T | undefined {    const size: number = this.#data.length - 1;    swap(this.#data, 0, size);    let parent = 0;    let right: number = 2 * (parent + 1);    let left: number = right - 1;    while (left < size) {      const greatestChild =        right === size || this.compare(this.#data[left], this.#data[right]) <= 0          ? left          : right;      if (this.compare(this.#data[greatestChild], this.#data[parent]) < 0) {        swap(this.#data, parent, greatestChild);        parent = greatestChild;      } else {        break;      }      right = 2 * (parent + 1);      left = right - 1;    }    return this.#data.pop();  }
  /** Adds values to the binary heap. */  push(...values: T[]): number {    for (const value of values) {      let index: number = this.#data.length;      let parent: number = getParentIndex(index);      this.#data.push(value);      while (        index !== 0 && this.compare(this.#data[index], this.#data[parent]) < 0      ) {        swap(this.#data, parent, index);        index = parent;        parent = getParentIndex(index);      }    }    return this.#data.length;  }
  /** Removes all values from the binary heap. */  clear() {    this.#data = [];  }
  /** Checks if the binary heap is empty. */  isEmpty(): boolean {    return this.#data.length === 0;  }
  /** Returns an iterator for retrieving and removing values from the binary heap. */  *drain(): IterableIterator<T> {    while (!this.isEmpty()) {      yield this.pop() as T;    }  }
  *[Symbol.iterator](): IterableIterator<T> {    yield* this.drain();  }}