{"version":3,"file":"MinimumHeap.js","sourceRoot":"","sources":["../src/MinimumHeap.ts"],"names":[],"mappings":";AAAA,4FAA4F;AAC5F,2DAA2D;;;AAE3D;;;;;GAKG;AACH,MAAa,WAAW;IAItB;;;;;;OAMG;IACH,YAAmB,UAAkC;QAVpC,WAAM,GAAQ,EAAE,CAAC;QAWhC,IAAI,CAAC,WAAW,GAAG,UAAU,CAAC;IAChC,CAAC;IAED;;;OAGG;IACH,IAAW,IAAI;QACb,OAAO,IAAI,CAAC,MAAM,CAAC,MAAM,CAAC;IAC5B,CAAC;IAED;;;OAGG;IACI,IAAI;QACT,OAAO,IAAI,CAAC,MAAM,CAAC,CAAC,CAAC,CAAC;IACxB,CAAC;IAED;;;OAGG;IACI,IAAI;QACT,IAAI,IAAI,CAAC,IAAI,GAAG,CAAC,EAAE,CAAC;YAClB,MAAM,MAAM,GAAM,IAAI,CAAC,MAAM,CAAC,CAAC,CAAC,CAAC;YACjC,MAAM,IAAI,GAAM,IAAI,CAAC,MAAM,CAAC,GAAG,EAAG,CAAC;YAEnC,MAAM,IAAI,GAAW,IAAI,CAAC,IAAI,CAAC;YAC/B,IAAI,IAAI,KAAK,CAAC,EAAE,CAAC;gBACf,oCAAoC;gBACpC,OAAO,MAAM,CAAC;YAChB,CAAC;YAED,IAAI,KAAK,GAAW,CAAC,CAAC;YAEtB,IAAI,iBAAiB,GAAW,CAAC,CAAC;YAElC,OAAO,iBAAiB,GAAG,IAAI,EAAE,CAAC;gBAChC,IAAI,YAAY,GAAM,IAAI,CAAC,MAAM,CAAC,iBAAiB,CAAC,CAAC;gBAErD,MAAM,eAAe,GAAW,iBAAiB,GAAG,CAAC,CAAC;gBAEtD,IAAI,eAAe,GAAG,IAAI,EAAE,CAAC;oBAC3B,MAAM,UAAU,GAAM,IAAI,CAAC,MAAM,CAAC,eAAe,CAAC,CAAC;oBACnD,IAAI,IAAI,CAAC,WAAW,CAAC,UAAU,EAAE,YAAY,CAAC,GAAG,CAAC,EAAE,CAAC;wBACnD,iBAAiB,GAAG,eAAe,CAAC;wBACpC,YAAY,GAAG,UAAU,CAAC;oBAC5B,CAAC;gBACH,CAAC;gBAED,IAAI,IAAI,CAAC,WAAW,CAAC,YAAY,EAAE,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC;oBAC7C,IAAI,CAAC,MAAM,CAAC,KAAK,CAAC,GAAG,YAAY,CAAC;oBAClC,KAAK,GAAG,iBAAiB,CAAC;oBAC1B,iBAAiB,GAAG,KAAK,GAAG,CAAC,GAAG,CAAC,CAAC;gBACpC,CAAC;qBAAM,CAAC;oBACN,MAAM;gBACR,CAAC;YACH,CAAC;YAED,oEAAoE;YACpE,IAAI,CAAC,MAAM,CAAC,KAAK,CAAC,GAAG,IAAI,CAAC;YAE1B,OAAO,MAAM,CAAC;QAChB,CAAC;IACH,CAAC;IAED;;;OAGG;IACI,IAAI,CAAC,IAAO;QACjB,IAAI,KAAK,GAAW,IAAI,CAAC,IAAI,CAAC;QAC9B,OAAO,KAAK,GAAG,CAAC,EAAE,CAAC;YACjB,mEAAmE;YACnE,MAAM,WAAW,GAAW,CAAC,CAAC,KAAK,GAAG,CAAC,CAAC,IAAI,CAAC,CAAC,GAAG,CAAC,CAAC;YACnD,MAAM,MAAM,GAAM,IAAI,CAAC,MAAM,CAAC,WAAW,CAAC,CAAC;YAC3C,IAAI,IAAI,CAAC,WAAW,CAAC,IAAI,EAAE,MAAM,CAAC,GAAG,CAAC,EAAE,CAAC;gBACvC,IAAI,CAAC,MAAM,CAAC,KAAK,CAAC,GAAG,MAAM,CAAC;gBAC5B,KAAK,GAAG,WAAW,CAAC;YACtB,CAAC;iBAAM,CAAC;gBACN,MAAM;YACR,CAAC;QACH,CAAC;QACD,IAAI,CAAC,MAAM,CAAC,KAAK,CAAC,GAAG,IAAI,CAAC;IAC5B,CAAC;CACF;AAlGD,kCAkGC","sourcesContent":["// Copyright (c) Microsoft Corporation. All rights reserved. Licensed under the MIT license.\n// See LICENSE in the project root for license information.\n\n/**\n * Implements a standard heap data structure for items of type T and a custom comparator.\n * The root will always be the minimum value as determined by the comparator.\n *\n * @public\n */\nexport class MinimumHeap<T> {\n  private readonly _items: T[] = [];\n  private readonly _comparator: (a: T, b: T) => number;\n\n  /**\n   * Constructs a new MinimumHeap instance.\n   * @param comparator - a comparator function that determines the order of the items in the heap.\n   *   If the comparator returns a value less than zero, then `a` will be considered less than `b`.\n   *   If the comparator returns zero, then `a` and `b` are considered equal.\n   *   Otherwise, `a` will be considered greater than `b`.\n   */\n  public constructor(comparator: (a: T, b: T) => number) {\n    this._comparator = comparator;\n  }\n\n  /**\n   * Returns the number of items in the heap.\n   * @returns the number of items in the heap.\n   */\n  public get size(): number {\n    return this._items.length;\n  }\n\n  /**\n   * Retrieves the root item from the heap without removing it.\n   * @returns the root item, or `undefined` if the heap is empty\n   */\n  public peek(): T | undefined {\n    return this._items[0];\n  }\n\n  /**\n   * Retrieves and removes the root item from the heap. The next smallest item will become the new root.\n   * @returns the root item, or `undefined` if the heap is empty\n   */\n  public poll(): T | undefined {\n    if (this.size > 0) {\n      const result: T = this._items[0];\n      const item: T = this._items.pop()!;\n\n      const size: number = this.size;\n      if (size === 0) {\n        // Short circuit in the trivial case\n        return result;\n      }\n\n      let index: number = 0;\n\n      let smallerChildIndex: number = 1;\n\n      while (smallerChildIndex < size) {\n        let smallerChild: T = this._items[smallerChildIndex];\n\n        const rightChildIndex: number = smallerChildIndex + 1;\n\n        if (rightChildIndex < size) {\n          const rightChild: T = this._items[rightChildIndex];\n          if (this._comparator(rightChild, smallerChild) < 0) {\n            smallerChildIndex = rightChildIndex;\n            smallerChild = rightChild;\n          }\n        }\n\n        if (this._comparator(smallerChild, item) < 0) {\n          this._items[index] = smallerChild;\n          index = smallerChildIndex;\n          smallerChildIndex = index * 2 + 1;\n        } else {\n          break;\n        }\n      }\n\n      // Place the item in its final location satisfying the heap property\n      this._items[index] = item;\n\n      return result;\n    }\n  }\n\n  /**\n   * Pushes an item into the heap.\n   * @param item - the item to push\n   */\n  public push(item: T): void {\n    let index: number = this.size;\n    while (index > 0) {\n      // Due to zero-based indexing the parent is not exactly a bit shift\n      const parentIndex: number = ((index + 1) >> 1) - 1;\n      const parent: T = this._items[parentIndex];\n      if (this._comparator(item, parent) < 0) {\n        this._items[index] = parent;\n        index = parentIndex;\n      } else {\n        break;\n      }\n    }\n    this._items[index] = item;\n  }\n}\n"]}