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

Question

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

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

请向我介绍我可能需要了解的任何其他 material。

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;
        }
    }

更多资源普林斯顿：

Answer 2

import java.util.HashMap;
import java.util.NoSuchElementException;

public class Heap<Key extends Comparable<Key>> {
    private Key[] heap;
    private int maxN, n;
    private HashMap<Key, Integer> map;
    @SuppressWarnings("unchecked")
    public Heap(int maxN) {
        if(maxN < 0 ) throw new IllegalArgumentException();
        this.maxN = maxN;
        n = 0;
        heap = (Key[]) new Comparable[maxN];
        map = new HashMap<>(maxN);
    }

    boolean isEmpty() {
        return n == 0;
    }

    boolean insert(Key e) {
        if(n +1 > maxN) throw new IllegalArgumentException("maximum capacity reached " + maxN);
        heap[n] = e;
        map.put(e,n);
        int i = n++;
        swim(i);
        return true;
    }

    Key extractMin() {
        if(n == 0) throw new NoSuchElementException("Priority queue underflow ");
        Key min = heap[0];
        swap(0, n-1);
        map.remove(min);
        n--;
        sink(0);
        return min;
    }

    void delete(Key e){
        if(!map.containsKey(e)) return; //throw new NoSuchElementException(e+" does not exist ");
        int j = map.get(e);
        swap(j, n-1);
        map.remove(e);
        n--;
        if(!swim(j))
            sink(j);
    }

    void decreasePriority(Key e){
        if(map.containsKey(e)){
            int j = map.get(e);
            swim(j);
        }
        else insert(e);
    }

    private void swap(int i, int j) {
        Key t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
        map.replace(heap[i], i);
        map.replace(heap[j], j);
    }
    private boolean swim(int j){
        boolean change = false;
        int parent;
        while( (parent = (j-1)/2 ) >= 0){
            if(heap[j].compareTo(heap[parent]) < 0){
                swap(j,parent);
                j = parent;
                change = true;
            }
            else break;
        }
        return change;
    }
    private void sink(int j){
        while(j <= n/2 - 1){
            int leftChild = j*2 + 1, rightChild = leftChild + 1, s;
            if(rightChild >= n)
                s = leftChild;
            else
                s = heap[leftChild].compareTo(heap[rightChild]) < 0 ? leftChild : rightChild;
            if(heap[j].compareTo(heap[s]) > 0){
                swap(j,s);
                j = s;
            }
            else break;
        }
    }

    @Override
    public String toString() {
        String res = "[";
        int i;
        for (i = 0; i < n-1; i++){
            res += heap[i] + ", ";
        }
        res += heap[i]+"]";
        return res;
    }
}

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

High level description of a priority queue with adjustable priority

java

graph-theory

priority-queue