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

Question

在实现Dijkstra算法和Prim算法时，我们需要一个优先级可调的队列。我理解堆函数的基于数组的实现，但我不知道如何使优先级可调。我读过hashmap允许这样做，但我不明白是怎么回事。

有人能给我一个高层次的描述这个实现使用一个hashmap使用一个例子。a，b，c，d，e，f分别有2,4,0,6,1,9的优先级，插入堆后如何跟踪它们的索引？如果b的优先级改为8，这将如何工作？

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

Answer 1

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

Answer 2

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代码