Java 中的 PriorityQueue 实现，支持 changePriority 操作

Question

我需要一个优先级队列的实现，它允许降低优先级操作以允许高效地实现 Prim 和 Dijkstra 的算法。

我已经使用 HashMap 编写了一个 minHeap 实现，以将元素的索引存储在我的堆中。我正在处理的问题需要计算使用 Prim 算法获得的最小生成树的总权重。虽然我的实现适用于最多 200 个节点的大多数测试用例，但对于许多更大的测试用例，我仍然得到不正确的输出。

据我了解，这种使用 HashMap 的基于最小堆的优先级队列实现很常见，如果我的假设有误，请提供更适合该问题的方法。

我已经尝试调试我的代码 2 天了，似乎修复它的唯一方法是将它与正确运行的实现进行比较。因此，有人可以在 java.

中使用 HashMap 分享这样一个 PriorityQueue 实现吗？

尽管我已经尝试了很多测试用例，并且对于所有我可以自己追踪的测试用例（最多 30 个节点），到目前为止我已经得到了正确的答案，但是如果有一些特定的边界测试用例这可以帮助我找出问题，那也很棒。

这是我的代码，我知道调试它对其他人来说会很耗时，但如果我遗漏了一些明显的东西并且有更多专业知识的人可以指出错误，那将不胜感激。

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++;
        while ( (i+1)/2 - 1 >= 0){
            if ( e.compareTo(heap[(i+1)/2 - 1]) < 0 ) {
                swap(i, (i+1)/2 - 1);
                i = (i+1)/2 - 1;
            }
            else 
                break;
        }
        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--;
        int j = 0, s;
        while(j <= (n/2)-1){
            if(j == (n/2)-1 && n == (j+1)*2 )
                s = (j+1)*2 - 1;
            else 
                s = heap[(j+1)*2 - 1].compareTo(heap[(j+1)*2]) < 0 ? (j+1)*2 - 1 : (j+1)*2; 
            if(heap[j].compareTo(heap[s]) > 0 ){
                swap(j, s);
                j = s;
            }
            else break;
        }
        return min;
    }

    Key delete(Key e){
        if(!map.containsKey(e)) throw new NoSuchElementException(e+"does not exist ");
        int j = map.get(e), s;
        Key del = e;
        swap(j, n-1);
        map.remove(e);
        n--;
        while( j <= n/2 - 1){
            if(j == (n/2)-1 && n == (j+1)*2)
                s = (j+1)*2 - 1;
            else
                s = heap[(j+1)*2 - 1].compareTo(heap[(j+1)*2]) < 0 ? (j+1)*2 - 1 : (j+1)*2; 
            if(heap[j].compareTo(heap[s]) > 0 ){
                swap(j, s);
                j = s;
            }
            else break;
        }
        return del;
    }

    boolean decreasePriority(Key e){
        if(n == 0)
            return insert(e);
        if(map.containsKey(e))
            delete(e);
        return 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);
    }

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

Answer 1

我认为问题出在您的 delete 方法中。您的代码这样做：

swap item to be removed with the last item in the heap
reduce heap count
push the new item down the heap

您假设 heap[j] < heap[n-1]。这不是一个有效的假设。考虑这个堆：

        1
    6       2
  7   8   3

如果删除值为 7 的节点，值 3 将替换它：

        1
    6       2
  3   8

您现在必须将它向上移动到树以创建一个有效的堆：

        1
    3       2
  6   8

这里的关键是，如果您要替换的项目与堆中的最后一个项目位于不同的子树中，则替换节点可能小于被替换节点的父节点。

如果您要从堆的中间移除一个项目，您将与最后一个项目交换，那么您必须检查替换节点是向上移动还是向下移动。

不过，您应该考虑的一点是，要更改项目的优先级，您不必删除并重新添加。您所要做的就是更改优先级，然后适当调整项目的位置：向上或向下移动以将其置于新位置。

Answer 2

删除方法不正确，我使用的是与extractMin相同的任意删除过程，没有考虑到我替换要删除的键的元素可能会上升或下降堆。使用 swim() 和 sink() 方法我已经纠正了这个错误。此外，不需要更改优先级删除和插入，只需简单地调用 swim 和 sink 就足够了。（仅在降低优先级时才游泳，在仅增加优先级时才下沉）。

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

编辑：小心你的 class 比较器。

Java 中的 PriorityQueue 实现，支持 changePriority 操作

PriorityQueue implementation in Java with support for changePriority operation

java

graph-theory

priority-queue

prims-algorithm

min-heap