1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
// 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 decending order by default, * using JavaScript's built in comparison operators to sort the values. */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();  }}