https://leetcode.com/problems/cheapest-flights-within-k-stops/

cheapestFlightWithKStops.js

/**
 * @param {number} n
 * @param {number[][]} flights
 * @param {number} src
 * @param {number} dst
 * @param {number} K
 * @return {number}
 */
var findCheapestPrice = function(n, flights, src, dst, K) {
    
    const graph = {};
    flights.forEach(([from, to, cost]) => {
        if(!graph.hasOwnProperty(from)) graph[from] = [];
        graph[from].push([to, cost]);
    });
    
    const compare = (a, b) => a.cost - b.cost;
    const heap = new Heap(compare); // lowest cost first
    const stops = new Array(n).fill(Infinity);
    const dists = new Array(n).fill(Infinity);
    heap.push({ dest: src, cost: 0, stops: 0 });
    
    while(heap.size()){
        
        const current = heap.pop();
        if(current.dest === dst) return current.cost;
        
        if(current.stops > K) continue; // too many stops
        
        (graph[current.dest] || []).forEach(([to, cost]) => {
            const totalCost = current.cost + cost;
            const totalStops = current.stops+1;
            if(totalCost < dists[to] || totalStops < stops[to]){
                heap.push({ dest: to, cost: totalCost, stops: totalStops });
            }
        });
        
    }
    
    return -1;
};

// https://github.com/RP-3/lc-data-structures/blob/master/src/Heap.ts
class Heap {
    constructor(comparator, maxSize = Infinity) {
        this.comparator = comparator;
        this.maxSize = maxSize;
        this.storage = [];
    }
    static heapify(array, comparator, maxSize = Infinity) {
        const result = new Heap(comparator, maxSize);
        result.storage = array;
        result.heapify();
        return result;
    }
    push(val) {
        this.storage.push(val);
        this.percolateUp(this.storage.length - 1);
        if (this.storage.length > this.maxSize)
            return this.pop();
        return null;
    }
    pop() {
        if (this.storage.length === 0)
            return null;
        if (this.storage.length === 1)
            return this.storage.pop();
        const tmp = this.storage[0];
        this.storage[0] = this.storage.pop();
        this.percolateDown(0);
        return tmp;
    }
    peak() {
        if (!this.storage.length)
            return null;
        return this.storage[0];
    }
    size() {
        return this.storage.length;
    }
    inOrder(parentIndex, childIndex) {
        return this.comparator(this.storage[parentIndex], this.storage[childIndex]) <= 0;
    }
    percolateUp(i) {
        let parentIndex = this.parentIndex(i);
        while (parentIndex >= 0 && parentIndex < i && !this.inOrder(parentIndex, i)) {
            const tmp = this.storage[parentIndex];
            this.storage[parentIndex] = this.storage[i];
            this.storage[i] = tmp;
            i = parentIndex;
            parentIndex = this.parentIndex(i);
        }
    }
    percolateDown(i) {
        let childIndex = this.highestPriorityChildIndex(i);
        while (childIndex !== null && !this.inOrder(i, childIndex)) {
            [this.storage[i], this.storage[childIndex]] = [this.storage[childIndex], this.storage[i]];
            i = childIndex;
            childIndex = this.highestPriorityChildIndex(i);
        }
    }
    highestPriorityChildIndex(parentIndex) {
        const leftChildIndex = this.leftChildIndex(parentIndex);
        const rightChildIndex = this.rightChildIndex(parentIndex);
        if (leftChildIndex >= this.storage.length)
            return null;
        if (rightChildIndex >= this.storage.length)
            return leftChildIndex;
        const leftChild = this.storage[leftChildIndex];
        const rightChild = this.storage[rightChildIndex];
        const comparison = this.comparator(leftChild, rightChild);
        return (comparison <= 0) ? leftChildIndex : rightChildIndex;
    }
    parentIndex(childIndex) {
        return Math.floor((childIndex - 1) / 2);
    }
    leftChildIndex(parentIndex) {
        return parentIndex * 2 + 1;
    }
    rightChildIndex(parentIndex) {
        return parentIndex * 2 + 2;
    }
    heapify() {
        if (!this.storage.length)
            return;
        let parentIndex = Math.floor((this.storage.length - 1 - 1) / 2);
        while (parentIndex >= 0)
            this.percolateDown(parentIndex--);
    }
}