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.

Monotone priority queues

I’m a little confused about how monotone priority queues work.

As far as I understand:

  • A queue is a FIFO data structure
  • A priority queue is a queue where the current element of highest (or lowest) priority is served before an item of lower (or higher) priority

Now, for monotone queues, I read the following on Wikipedia (also here):

Monotone priority queues are specialized queues that are optimized for the case where no item is ever inserted that has a lower priority (in the case of min-heap) than any item previously extracted.

I’m a little confused here. Does this mean that a monotone priority queue is nothing else than a queue with an enqueue method that simply prevents anyone from adding elements that are lower (monotone increasing) or higher (monotone decreasing) than the element at the tail?

If so:

  1. Why is this a priority queue? (if we are requiring the inserted elements to follow a monotonic sequence, the actual queue is just a FIFO queue, right?)
  2. In what ways are these FIFO queues “optimized” for monotonicity?

Questions regarding CPU scheduling algorithms ( Round Robin and Priority scheduling )

Consider the following processes :

enter image description here

1) My First Question is if we need to schedule them using preemptive priority scheduling with Round-Robin for equal processes priorities with a quantum of 3. Here is my answer to this problem :

enter image description here

Sorry about that bad drawing. My problem here is at time 13. At this time we have two processes of equal priority ( p1 and p3 ) that we need to schedule them using RR with a quantum of 3 . My question is what process we will start scheduling it here ? I have started with p1 as it was already being executed by the CPU . Also is the rest of the answer is right ?

2) Now for the second question. Let’s consider that We need to schedule the same process with a round-robin with a quantum of 4 . I have used this website to check my answer http://cpuburst.com/ and here its answer : enter image description here

According to this answer, at time 20 p4 should be executed, but according to my answer p1 is the process that should be executed ?? And due to this difference, the rest of the answer is different to mine.

Implementing an efficent priority queue using only stacks

Is it possible to implement an efficient priority queue (as efficient as a heap) only using the stack data structure?

The usual efficiency for a priority queue which is implemented using a heap is :

  • get min – $ O(1)$
  • extract min – $ O(\log n)$
  • add – $ O(\log n)$

Would it be possible to do something with the same complexity using only stacks?

Relation Between Priority Queue, Heap, Tree

There are $ 2$ “basic”/”fundamental” data structures due to the way memory works:

  1. array
  2. linked list

Then there are ADT that we implement using those two, for example: stack, queue and more.

When we arrive to priority queue we first need to implement and ADT called heap which can be implement using:

  1. array
  2. tree (which is ADT) the can be implemented using both array and linked list

So we have

array/linked list $ \subset$ tree $ \subset$ priority queue?

enter image description here

Should users know advanced and low priority features of the app?

Financial apps have lot of features, most of these features are nice-to-have features (e.g. changing PIN CODE, reports of income/outcome.. ) and advance features which few people may need (e.g. paying very specific bills, tracking selected transactions…)

Most of the users don’t know that the app has this kind of features and are simply using main functions.

Should designer try to make users know that this kind of features are available? In other words does user need to know about feature he/she will never use or use very seldom?