Debugging Priority queue implementation supporting priority update [closed]


Please let me know if you require any additional information, but please help me out here.

For an efficient implementation of algorithms like Dijkstra’s and Prim’s, we require a priority queue that supports decrease priority operation. I’ve come up with the following code(heap based priority queue) for this which stores the index of each entry in the priority queue using a HashMap.

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<>();     }      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;         }         n++;         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 = heap[j];         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;     } } 

For the problem I’m working on the program is supposed to output the total weight of the minimum spanning tree found by applying Prim’s algorithm. The input graph is a 500 node graph, and the answer obtained by this implementation is incorrect. I’m certain that the issue lies with the Heap and not with my implementation of Prim’s algorithm because using the inbuilt priority queue in java outputs the correct answer. Here is my Program running Prims’s algorithm.

import java.io.FileNotFoundException; import java.io.FileReader; import java.util.ArrayList; import java.util.List; import java.util.Scanner;  class Edge<Key>{     Key v;     int w;     public Edge(Key v, int w){         this.v = v; this.w = w;     }     @Override     public String toString(){         return "("+v+","+w+")";     } }  class vertex implements Comparable<vertex>{     int position, dis;     public vertex(int position){         this.position = position;         dis = Integer.MAX_VALUE;     }     @Override     public int compareTo(vertex v) {         if(dis > v.dis)             return 1;         if(dis < v.dis)             return -1;         return 0;     }     @Override     public String toString(){         return Integer.toString(position+1);     } } public class Prims {     public static void main(String[] args) throws FileNotFoundException {         Scanner in = new Scanner(new FileReader("prims.txt"));         int n = in.nextInt(), m = in.nextInt();         List<List<Edge<vertex>>> graph = new ArrayList<List<Edge<vertex>>>();         List<vertex> nodes = new ArrayList<vertex>();         for(int i = 0; i<n; i++){             graph.add(new ArrayList<>());             nodes.add(new vertex(i));         }         while(m-- > 0){             int u = in.nextInt()-1, v = in.nextInt()-1, w = in.nextInt();             graph.get(u).add(new Edge<vertex>(nodes.get(v), w));             graph.get(v).add(new Edge<vertex>(nodes.get(u), w));         }         in.close();         long st = System.currentTimeMillis();         System.out.println(prims(graph,nodes));         long end = System.currentTimeMillis();         System.out.println("Runtime = "+(end-st)+"ms");     }     static int prims(List<List<Edge<vertex>>> graph, List<vertex> nodes){         int n = graph.size(), weight = 0;         boolean[] inSpanTree = new boolean[n];         Heap<vertex> pq = new Heap<>(n);         inSpanTree[0] = true;         for(Edge<vertex> e : graph.get(0)){             e.v.dis = e.w;             pq.insert(e.v);         }         while(!pq.isEmpty()){             vertex u = pq.extractMin();             inSpanTree[u.position] = true;             weight += u.dis;             for(Edge<vertex> e : graph.get(u.position)){                 if(!inSpanTree[e.v.position]){                     if(e.v.dis > e.w){                         e.v.dis = e.w;                         pq.decreasePriority(nodes.get(e.v.position));                     }                 }             }         }         return weight;     } } 

If for this same implementation I use the inbuilt priority queue I get the correct output(-3612829)

static int prims(List<List<Edge<vertex>>> graph, List<vertex> nodes){         int n = graph.size(), weight = 0;         boolean[] inSpanTree = new boolean[n];         PriorityQueue<vertex> pq = new PriorityQueue<>();         inSpanTree[0] = true;         for(Edge<vertex> e : graph.get(0)){             e.v.dis = e.w;             pq.add(e.v);         }         System.out.println(pq);         while(!pq.isEmpty()){             vertex u = pq.poll();             if(u.position == 307)                 System.out.println(pq);             inSpanTree[u.position] = true;             weight += u.dis;             for(Edge<vertex> e : graph.get(u.position)){                 if(!inSpanTree[e.v.position]){                     if(e.v.dis > e.w){                         e.v.dis = e.w;                         pq.remove(nodes.get(e.v.position));                         pq.add(nodes.get(e.v.position));                     }                 }             }         }         return weight;     } 

My Heap implementation works for almost all test cases even up to 300 nodes. I don’t understand how to debug and find out where the problem lies. Here is the link to the Problem input:

https://d3c33hcgiwev3.cloudfront.net/_d4f3531eac1d289525141e95a2fea52f_edges.txt?Expires=1589673600&Signature=WSP-z481nsQgNDfN6zo0XNWy9nNTLAIty2k4HNhoQgW3pAsY0vUVaMdjg3g-UnKz9tKajuYcgGpYO3cw9H7N24tqescamo0q0n3Rykfb6BSkcI~DiKuiGpeA4gb630CU4gLAS8tDoaFRCjKNiyXAbXqHLeWhmGAmOrAnYl2rAMU_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A 

Can someone please help me debug my Heap implementation, I’ve been stuck a long time with this now. Thanks in advance.