CODEWITHSUNDEEP
javajava-8priority-queue
seeker
seeker

Reputation: 6991

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

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]]

Upvotes: 5

Views: 295

Answers (1)

Thomas Kl&#228;ger
Thomas Kl&#228;ger

Reputation: 21435

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);                       
}

Upvotes: 4

Related Questions