1class Solution {
2    maxProbability(n, edges, succProb, start, end) {
3        const graph = new Array(n).fill(0).map(() => []);
4        for (let i = 0; i < edges.length; i++) {
5            const [u, v] = edges[i];
6            const prob = succProb[i];
7            graph[u].push([v, prob]);
8            graph[v].push([u, prob]);
9        }
10
11        const maxProb = new Array(n).fill(0);
12        maxProb[start] = 1;
13
14        const pq = new MaxHeap();
15        pq.insert([1.0, start]);
16
17        while (!pq.isEmpty()) {
18            const [currProb, node] = pq.extractMax();
19            if (node === end) {
20                return currProb;
21            }
22
23            for (const [nextNode, edgeProb] of graph[node]) {
24                if (maxProb[nextNode] < currProb * edgeProb) {
25                    maxProb[nextNode] = currProb * edgeProb;
26                    pq.insert([maxProb[nextNode], nextNode]);
27                }
28            }
29        }
30
31        return 0;
32    }
33}
34
35class MaxHeap {
36    constructor() {
37        this.heap = [];
38    }
39
40    insert(pair) {
41        this.heap.push(pair);
42        this._heapifyUp();
43    }
44
45    extractMax() {
46        [this.heap[0], this.heap[this.heap.length - 1]] = [this.heap[this.heap.length - 1], this.heap[0]];
47        const max = this.heap.pop();
48        this._heapifyDown();
49        return max;
50    }
51
52    isEmpty() {
53        return this.heap.length === 0;
54    }
55
56    _heapifyUp() {
57        let index = this.heap.length - 1;
58        while (index > 0) {
59            let element = this.heap[index];
60            let parentIndex = Math.floor((index - 1) / 2);
61            let parent = this.heap[parentIndex];
62
63            if (parent[0] >= element[0]) break;
64
65            this.heap[index] = parent;
66            this.heap[parentIndex] = element;
67            index = parentIndex;
68        }
69    }
70
71    _heapifyDown() {
72        let index = 0;
73        const length = this.heap.length;
74        const element = this.heap[0];
75        while (true) {
76            let leftChildIndex = 2 * index + 1;
77            let rightChildIndex = 2 * index + 2;
78            let leftChild, rightChild;
79            let swap = null;
80
81            if (leftChildIndex < length) {
82                leftChild = this.heap[leftChildIndex];
83                if (leftChild[0] > element[0]) {
84                    swap = leftChildIndex;
85                }
86            }
87
88            if (rightChildIndex < length) {
89                rightChild = this.heap[rightChildIndex];
90                if (
91                    (swap === null && rightChild[0] > element[0]) ||
92                    (swap !== null && rightChild[0] > leftChild[0])
93                ) {
94                    swap = rightChildIndex;
95                }
96            }
97
98            if (swap === null) break;
99            this.heap[index] = this.heap[swap];
100            this.heap[swap] = element;
101            index = swap;
102        }
103    }
104}