[JavaScript] 优先队列

JavaScript 实现优先队列

代码如下：

class Heap {
    constructor(cmp = (a, b) => a < b) {
        this.arr = new Array();
        this.cmp = (a, b) => cmp(a, b) //比较函数
    }

    // 大小
    size() {
        return this.arr.length;
    }

    // 判空
    empty() {
        return this.size() == 0;
    }

    // 堆顶数据
    top() {
        return this.arr[0];
    }

    // 入队 
    push(val) {
        this.arr.push(val);
        this.shiftUp();
    }

    // 向上调整
    shiftUp() {
        let now = this.arr.length - 1;
        while (now > 0) {
            let t = (now - 1) >> 1;
            if (this.cmp(this.arr[now], this.arr[t])) {
                [this.arr[now], this.arr[t]] = [this.arr[t], this.arr[now]];
                now = t;
            }
            else break;
        }
    }

    // 出队
    pop() {
        if (this.size() == 1) return this.arr.pop();
        const res = this.arr[0];
        this.arr[0] = this.arr.pop();
        this.shiftDown();
        return res;
    };

    // 向下调整
    shiftDown() {
        let now = 0;
        while (now * 2 + 1 < this.size()) {
            let t = now * 2 + 1;
            if (t + 1 < this.size() && this.cmp(this.arr[t + 1], this.arr[t])) t++;
            if (this.cmp(this.arr[t], this.arr[now])) {
                [this.arr[now], this.arr[t]] = [this.arr[t], this.arr[now]];
                now = t;
            }
            else break;
        }
    }
}

例题：

​​​​​​力扣 743. 网络延迟时间https://leetcode.cn/problems/network-delay-time/

function node(a, b) {
    this.first = a;
    this.second = b;
}

var networkDelayTime = function (times, n, k) {
    const edges = Array.from(new Array(n + 1), () => new Array());
    for (const pair of times) {
        edges[pair[0]].push(new node(pair[1], pair[2]));
    }
    const dis = new Array(n + 1).fill(10001);
    const visited = new Array(n + 1).fill(false);
    const heap = new Heap((a, b) => a.first < b.first);
    dis[k] = 0;
    heap.push(new node(0, k));
    while (heap.size() > 0) {
        const now = heap.pop().second;
        if (visited[now]) continue;
        visited[now] = true;
        for (const edge of edges[now]) {
            const next = edge.first;
            const w = edge.second;
            if (dis[next] > dis[now] + w) {
                dis[next] = dis[now] + w;
                heap.push(new node(dis[next], next));
            }
        }
    }
    let res = 0;
    for (let i = 1; i <= n; i++) {
        if (dis[i] == 10001) return -1;
        res = Math.max(res, dis[i]);
    }
    return res;
};

// 优先队列
class Heap {
    constructor(cmp = (a, b) => a < b) {
        this.arr = new Array();
        this.cmp = (a, b) => cmp(a, b) //比较函数
    }

    // 大小
    size() {
        return this.arr.length;
    }

    // 判空
    empty() {
        return this.size() == 0;
    }

    // 堆顶数据
    top() {
        return this.arr[0];
    }

    // 入队 
    push(val) {
        this.arr.push(val);
        this.shiftUp();
    }

    // 向上调整
    shiftUp() {
        let now = this.arr.length - 1;
        while (now > 0) {
            let t = (now - 1) >> 1;
            if (this.cmp(this.arr[now], this.arr[t])) {
                [this.arr[now], this.arr[t]] = [this.arr[t], this.arr[now]];
                now = t;
            }
            else break;
        }
    }

    // 出队
    pop() {
        if (this.size() == 1) return this.arr.pop();
        const res = this.arr[0];
        this.arr[0] = this.arr.pop();
        this.shiftDown();
        return res;
    };

    // 向下调整
    shiftDown() {
        let now = 0;
        while (now * 2 + 1 < this.size()) {
            let t = now * 2 + 1;
            if (t + 1 < this.size() && this.cmp(this.arr[t + 1], this.arr[t])) t++;
            if (this.cmp(this.arr[t], this.arr[now])) {
                [this.arr[now], this.arr[t]] = [this.arr[t], this.arr[now]];
                now = t;
            }
            else break;
        }
    }
}