sort priority queue of objects by specified value

Question

i want to add objects to priority queue by using specified value like this

PriorityQueue<Edge> queue=new PriorityQueue<Edge>();

this is class Edge which i want to sort in priority queue by its weight

public class Edge {
private int start,end;
private double weight;

public Edge(int s, int e,Double w){
    start=s;
    end=e;
    weight=w;
}

public int getStart(){
    return start;
}

public int getEnd(){
    return end;
}

public double getWeight(){
    return weight;
}

possible duplicate of [Java: How do I use a PriorityQueue?](http://stackoverflow.com/questions/683041/java-how-do-i-use-a-priorityqueue) — luk2302, May 16 '15 at 09:06
i am not familiar with Comparator what that mean ? PriorityQueue queue = new PriorityQueue(10, comparator); — miro, May 16 '15 at 09:16

score 5 · Accepted Answer · answered May 16 '15 at 09:21

5

You should create your priority Queue a little bit different by specifying how its elements should be compared. That is done by passing an anonymous Comparator for the Edge class:

PriorityQueue<Edge> queue=new PriorityQueue<Edge>(10, new Comparator<Edge>() {
    public int compare(Edge edge1, Edge edge2) {
        if (edge1.getWeight() < edge2.getWeight()) return -1;
        if (edge1.getWeight() > edge2.getWeight()) return 1;
        return 0;
    }
});

Maybe you will have to switch the returns of -1 and 1 depending on your sorting order.

answered May 16 '15 at 09:21

luk2302

55,258
23
97
137

this answer saved me thanks a lot, But i have only one question what 10 means ? – miro May 16 '15 at 09:28
1

the 10 refers to the initial capacity of the priority queue, if you already know how many edges you are going to insert, choose that number instead of 10 - otherwise 10 will be fine. it will not take up much space if you put in less than 10 and it will grow if you put more in. – luk2302 May 16 '15 at 09:30

score 0 · Answer 2 · answered Mar 23 '17 at 17:54

You can create a priority queue and a Checker (custom) class that compare the edges. like this :

  class Checker implements Comparator<Edge>
  {
      public int compare(Edge ob1, Edge ob2)
      {
          if (ob1.getWeight() > ob2.getWeight()) return 1;
          else                                   return -1;
      }
  }

 //Declared priority queue
  PriorityQueue<Edge> queue=new PriorityQueue<Edge>(5, new Checker());

score 0 · Answer 3 · answered Mar 24 '20 at 15:46

Java 8 :

PriorityQueue<Edge> queue = new PriorityQueue<>((edge1, edge2) -> {
            if (edge1.getWeight() < edge2.getWeight()) {
                return -1;
            }
            if (edge1.getWeight() > edge2.getWeight()) {
                return 1;
            }
            return 0;
});

score 0 · Answer 4 · answered Jun 25 '23 at 18:19

Solution 1:

Min Heap:

a -> a.getWeight()

Max Heap:

a -> -a.getWeight()

Example:

PriorityQueue<Edge> PriorityQueue = new PriorityQueue<>(Comparator.comparingDouble(a -> a.getWeight()));
PriorityQueue = new PriorityQueue<>(Comparator.comparingDouble(a -> -a.getWeight()));

Solution 2:

Min Heap:

Edge::getWeight

Max Heap:

(Edge::getWeight).reversed()

Example:

PriorityQueue<Edge> PriorityQueue = new PriorityQueue<>(Comparator.comparingDouble(Edge::getWeight));
PriorityQueue = new PriorityQueue<>(Comparator.comparingDouble(Edge::getWeight).reversed());

Solution 3:

Min Heap:

(a, b) -> a.getStart() - b.getStart()

(a, b) -> (int) (a.getWeight() - b.getWeight())

Max Heap:

(a, b) -> b.getStart() - a.getStart()

(a, b) -> (int) (b.getWeight() - a.getWeight())

Example:

PriorityQueue<Edge> PriorityQueue = new PriorityQueue<>((a, b) -> a.getStart() - b.getStart());
PriorityQueue = new PriorityQueue<>((a, b) -> (int) (a.getWeight() - b.getWeight()));
PriorityQueue = new PriorityQueue<>((a, b) -> b.getStart() - a.getStart());
PriorityQueue = new PriorityQueue<>((a, b) -> (int) (b.getWeight() - a.getWeight()));

sort priority queue of objects by specified value

4 Answers4

Solution 1:

Min Heap:

Max Heap:

Example:

Solution 2:

Min Heap:

Max Heap:

Example:

Solution 3:

Min Heap:

Max Heap:

Example: