时间戳

首页 > 解决方案 > Java 中的 PriorityQueue 实现，支持 changePriority 操作

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

问题描述

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

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

据我了解，这种使用 HashMaps 的基于 minheap 的优先级队列实现很常见，如果我的假设有误，请提供更合适的方法来解决这个问题。

我已经尝试调试我的代码 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;
    }
}

标签： javagraph-theorypriority-queueprims-algorithmmin-heap

解决方案

我认为问题出在你的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

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

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

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

推荐阅读