Java Priority Queue reordering when editing elements

user_880050 0
Viewed 32972

I'm trying to implement Dijkstra's algorithm for finding shortest paths using a priority queue. In each step of the algorithm, I remove the vertex with the shortest distance from the priority queue, and then update the distances for each of its neighbors in the priority queue. Now I read that a Priority Queue in Java won't reorder when you edit the elements in it (the elements that determine the ordering), so I tried to force it to reorder by inserting and removing a dummy vertex. But this doesn't seem to be working, and I'm stuck trying to figure it out.

This is the code for the vertex object and the comparator

class vertex {
    int v, d;
    public vertex(int num, int dis) {
        v=num;
        d=dis;
    }
}

class VertexComparator implements Comparator {
    public int compare (Object a, Object b) {
        vertex v1 = (vertex)a;
        vertex v2 = (vertex)b;
        return v1.d-v2.d;
    }
 }

Here is then where I run the algorithm:

    int[] distances=new int[p];
    Comparator<vertex> comparator = new VertexComparator();
    PriorityQueue<vertex> queue = new PriorityQueue<vertex>(p, comparator);
    for(int i=0; i<p; i++) {
        if(i!=v) {
            distances[i]=MAX;
        }
        else {
            distances[i]=0;
        }
        queue.add(new vertex(i, distances[i]));
    }
    // run dijkstra
    for(int i=0; i<p; i++) {
        vertex cur=queue.poll();
        Iterator itr = queue.iterator();
        while(itr.hasNext()) {
            vertex test = (vertex)(itr.next());
            if(graph[cur.v][test.v]!=-1) {
                test.d=Math.min(test.d, cur.d+graph[cur.v][test.v]);
                distances[test.v]=test.d;
            }
        }
        // force the PQ to resort by adding and then removing a dummy vertex
        vertex resort = new vertex(-1, -1);
        queue.add(resort);
        queue.remove(resort);
    }

I've run several text cases, and I know that the priority queue isn't reordering correctly each time I go through and update the distances for vertices, but I don't know why. Did I make an error somewhere?

priority-queue java
7 Answers

I implemented an adaptive MinHeap that supports reorderining (O(nlogn)) when objects' priority are updated, written in Python.

class Node:
    """
    Model an object in Heap.
    """

    def __init__(self, key, val, i=-1) -> None:
        self.key = key  # object ID
        self.val = val  # object priority
        self.i = i  # index in heap array


class AdaptiveMinHeap:
    """
    Heap for objects. Support reorderining when objects' priority are updated.
    """

    def __init__(self) -> None:
        self.hp = {0: Node(-1, -1, 0)}  # Use dict to simulate list (key as the index) to support efficient reordering.
        self.d = dict()

    def __len__(self):
        return len(self.hp)-1

    def _swap(self, anode, bnode):
        d = self.d
        anode.key, bnode.key = bnode.key, anode.key
        anode.val, bnode.val = bnode.val, anode.val
        d[anode.key] = anode
        d[bnode.key] = bnode

    def _swim(self, i):
        hp = self.hp
        while i//2 > 0 and hp[i].val < hp[i//2].val:
            self._swap(hp[i], hp[i//2])
            i = i//2

    def _sink(self, i):
        hp = self.hp
        while i*2 < len(hp):
            if i*2 + 1 >= len(hp) or hp[i*2+1].val >= hp[i*2].val:
                min_child = i*2
            else:
                min_child = i*2+1
            if hp[min_child].val < hp[i].val:
                self._swap(hp[min_child], hp[i])
            i = min_child

    def push(self, key, val):
        hp = self.hp
        d = self.d
        if key in d:
            self.remove(key)
        node = Node(key, val, len(hp))
        d[key] = node
        hp[node.i] = node
        self._swim(node.i)

    def pop(self):
        hp = self.hp
        if len(hp) > 1:
            return self.remove(hp[1].key)

    def remove(self, key):
        hp = self.hp
        d = self.d
        node = d[key]
        self._swap(hp[node.i], hp[len(hp)-1])
        hp.pop(len(hp)-1)
        self._sink(node.i)
        return d.pop(key)

hp = AdaptiveMinHeap()
hp.push(1, 40)
hp.push(4, 8900)
hp.push(2, 500)
hp.push(3, 1075)
hp.push(1, 1)
for _ in range(len(hp)):
    poped = hp.pop()
    print(poped.key, poped.val)
# 1
# 500
# 1075
# 8900
user_125345430
Related