Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What am I doing wrong with the Java 8 PriorityQueue comparator?

Tags:

I'm trying to solve this exercise and here's my solution. It basically holds a tree map to map the nodes at the same veritical offset to a key. And uses a priority queue to split ties when there are multiple keys at the same (horizontal level) using the value at the node.

public List<List<Integer>> verticalTraversal(TreeNode root) {
    Map<Integer, PriorityQueue<Node>> map = new TreeMap<>();
    List<List<Integer>> out = new ArrayList<>();
    if(root == null)
        return out;
    Queue<Node> q = new LinkedList<>();
    Node r = new Node(root, 0, 0);
    q.add(r);
    while(!q.isEmpty()) {
        Node curr = q.remove();
        int x = curr.x;
        int y = curr.y;
        PriorityQueue<Node> pq = map.getOrDefault(y, new PriorityQueue<Node>((a,b) ->(a.x == b.x? a.t.val - b.t.val: a.x - b.x)));
        pq.add(curr);
        map.put(y,pq);
        if(curr.t.left!=null){
            Node left = new Node(curr.t.left, x+1, y-1);
            q.add(left);
        }
        if(curr.t.right!=null){
            Node right = new Node(curr.t.right, x+1, y + 1);
            q.add(right);
        }
    }
for (Map.Entry<Integer, PriorityQueue<Node>> entry : map.entrySet()){
   PriorityQueue<Node> pq = entry.getValue();
    List<Integer> vals = new ArrayList<>();
   for (Node pqNode: pq){
       vals.add(pqNode.t.val);                       

   }
out.add(new ArrayList<Integer>(vals));

}
return out;
}




class Node {
    TreeNode t;
    int y;
    int x;
    Node(TreeNode t, int x, int y) {
        this.t = t;
        this.x = x;
        this.y = y; 
    }
}

}

And to be clear here's where I think the problem is

  PriorityQueue<Node> pq = map.getOrDefault(y, new PriorityQueue<Node>((a,b) ->(a.x == b.x? a.t.val - b.t.val: a.x - b.x)));

I get the expected order when a.x isnt equal to b.x but it doesnt seem to go by the val when they're equal.

Here's the failing test case enter image description here Actual : [[7,9],[5,6],[0,2,4],[1,3],[8]] Expected: [[9,7],[5,6],[0,2,4],[1,3],[8]]

like image 906
seeker Avatar asked Feb 06 '19 22:02

seeker


People also ask

How does PriorityQueue use comparator?

PriorityQueue. comparator() method shares an important function of setting and returning the comparator that can be used to order the elements in a PriorityQueue. The method returns a null value if the queue follows the natural ordering pattern of the elements.

How does PriorityQueue work in Java?

Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator. comparator - the comparator that will be used to order this priority queue. If null , the natural ordering of the elements will be used.

How do I change priority queue to maximum priority queue?

In Java, Priority Queue, by default implement min Priority Queue, If we need to change the order of Priority Queue from min to max Priority Queue, then we use some methods as follows: Using default Comparator Collections. reverseOrder() Using custom Comparator.

How do I create a priority queue with comparator?

Parameters: capacity - the initial capacity for this priority queue comparator - the comparator that will be used to order this priority queue. If null, the natural ordering of the elements will be used. public PriorityQueue(SortedSet ss) : Creates a PriorityQueue containing the elements in the specified sorted set.


1 Answers

What your doing wrong is that you iterate over the elements of the priority queue instead of polling it.

The documentation of PriorityQueue#iterator() clearly states:

Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.

Instead of writing

for (Node pqNode: pq){
    vals.add(pqNode.t.val);                       
}

you should use:

Node pqNode;
while ((pqNode = pq.poll()) != null) {
    vals.add(pqNode.t.val);                       
}
like image 151
Thomas Kläger Avatar answered Dec 14 '22 02:12

Thomas Kläger