CODEWITHSUNDEEP
javalinked-listcomparatorpriority-queue
Slayahh
Slayahh

Reputation: 393

Comparator not working correctly for Priorityqueue Java

I am adding edges to a PriorityQueue but for some reason they do not get sorted by their value, leading to a faulty result later.

My edge class looks like this

class Edge implements Comparable<Edge>{
int value;
String dest;
String start;

public Edge(String start, String dest, int g) {
    this.dest = dest;
    value = g;
    this.start = start;
}
@Override
public int compareTo(Edge o) {
    int temp = value - o.value;
    if (temp > 0) {
        return 1;
    }
    if (temp < 0) {
        return -1;
    }
    return 0;
}

Yet, when I run my code where I do addAll on a LinkedList belonging to the Node "Springfield, MO" to the PriorityQueue, the Edges get sorted in the wrong order as seen below, what is the issue?

queue.addAll(list.get(node));

enter image description here

I have tried to make a specific comparator class for Edge and using it as a parameter in the PriorityQueue but I still get the same result.

Upvotes: 6

Views: 2673

Answers (1)

xingbin
xingbin

Reputation: 28279

The internal structure of the PriorityQueue is not ordered, it is a heap, you can check this question.

When you retrieve data using method peek or poll, it is guranteed to be ordered.

But be careful when you iterator the queue:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

Upvotes: 9

Related Questions