java - 具有可调整优先级的优先级队列的高级描述

Question

在实现 Dijkstra 和 Prim 算法时，我们需要一个具有可调整优先级的优先级队列。我了解堆函数的基于数组的实现如何，但我不明白如何使优先级可调。我读过哈希图允许这样做，但我不明白如何。

有人可以使用示例使用哈希图给我这个实现的高级描述。a、b、c、d、e、f 的优先级分别为 2、4、0、6、1、9，插入堆后如何跟踪它们的索引？如果 b 的优先级更改为 8，这将如何工作？

请参考我可能需要的任何其他材料来理解这一点。

标签： javagraph-theorypriority-queue

Answer 1

MinPQ 中的更改将使用swim()和sink()操作来调整优先级

例如decreaseKey()将降低与其所在顶点相关的优先级

只是调用swim()操作

, 并且increasekey()会增加与它的顶点相关的优先级

只是调用sink()操作

实现应如下所示：

    private void swim(int k) {
        while (k > 1 && greater(k/2, k)) {
            swap(k, k/2);
            k = k/2;
        }
    }

    private void swap(int k) {
        while (2*k <= n) {
            int j = 2*k;
            if (j < n && greater(j, j+1)) j++;
            if (!greater(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

更多资源普林斯顿：

1. 最短路径讲座
2. IndexMinPQ 代码
3. DijkstraSP 代码