mokkenstorm.dev
fork of hey-api/openapi-ts because I need some additional things
1export class MinHeap {
2 private heap: Array<string> = [];
3
4 constructor(public declIndex: Map<string, number>) {}
5
6 isEmpty(): boolean {
7 return !this.heap.length;
8 }
9
10 pop(): string | undefined {
11 const [top] = this.heap;
12 if (!this.heap.length) return;
13 const last = this.heap.pop()!;
14 if (!this.heap.length) return top;
15 this.heap[0] = last;
16 this.sinkDown(0);
17 return top;
18 }
19
20 push(item: string): void {
21 this.heap.push(item);
22 this.bubbleUp(this.heap.length - 1);
23 }
24
25 private bubbleUp(index: number): void {
26 const heap = this.heap;
27 while (index > 0) {
28 const parent = Math.floor((index - 1) / 2);
29 const parentVal = heap[parent]!;
30 const curVal = heap[index]!;
31 if (this.declIndex.get(parentVal)! <= this.declIndex.get(curVal)!) break;
32 heap[parent] = curVal;
33 heap[index] = parentVal;
34 index = parent;
35 }
36 }
37
38 private sinkDown(index: number): void {
39 const heap = this.heap;
40 const len = heap.length;
41 while (true) {
42 const left = 2 * index + 1;
43 const right = 2 * index + 2;
44 let smallest = index;
45 if (left < len) {
46 const leftVal = heap[left]!;
47 const smallestVal = heap[smallest]!;
48 if (this.declIndex.get(leftVal)! < this.declIndex.get(smallestVal)!) smallest = left;
49 }
50 if (right < len) {
51 const rightVal = heap[right]!;
52 const smallestVal = heap[smallest]!;
53 if (this.declIndex.get(rightVal)! < this.declIndex.get(smallestVal)!) smallest = right;
54 }
55 if (smallest === index) break;
56 const tmp = heap[smallest]!;
57 heap[smallest] = heap[index]!;
58 heap[index] = tmp;
59 index = smallest;
60 }
61 }
62}