PriorityQueue not sorting map by value

Question

I have a simple class Cell:

public class Cell {
    private int row, column;

    public Cell(int row, int column) {
        this.row = row;
        this.column = column;
    }

    public void setRow(int row) {
        this.row = row;
    }

    public void setColumn(int column) {
         this.column = column;
    }

    public int getRow() {
        return row;
    }

    public int getColumn() {
        return column;
    }

    @Override
    public String toString() {
         return "[" + row + "," +  column + "]";
    }


    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + column;
        result = prime * result + row;
        return result;
    }


    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Cell other = (Cell) obj;
        if (column != other.column)
            return false;
        if (row != other.row)
            return false;
        return true;
      }
}

I have created a HashMap. Now, I want to sort it by value. This was my approach:

PriorityQueue<Entry<Cell, Integer>> sortedCells = new PriorityQueue<Map.Entry<Cell, Integer>>(cells.size(), new CompareByValue());
sortedCells.addAll(cells.entrySet());

and CompareByValue is a Comparator:

private class CompareByValue implements Comparator<Map.Entry<Cell, Integer>> {

    @Override
    public int compare(Entry<Cell, Integer> lhs,
            Entry<Cell, Integer> rhs) {

        return lhs.getValue().compareTo(rhs.getValue());
    }
}

This entrySet:

{[1,2]=1, [1,0]=2, [2,1]=1, [-1,0]=1, [-1,1]=1, [0,2]=1, [0,-1]=1}

returns this PriorityQueue:

[[1,2]=1, [-1,0]=1, [2,1]=1, [1,0]=2, [-1,1]=1, [0,2]=1, [0,-1]=1]

Why it doesn't sort by value? I want something like:

[[1,0]=2, [1,2]=1, [-1,0]=1, [2,1]=1, [-1,1]=1, [0,2]=1, [0,-1]=1]

It's not my first time sorting a map by value using PriorityQueue, but I don't understand what is going on here..

possible duplicate of [Why is this strange order happens in PriorityQueue in java?](http://stackoverflow.com/questions/12369204/why-is-this-strange-order-happens-in-priorityqueue-in-java) — Fred Foo, May 27 '14 at 11:39
When I use poll(), elements are returned on that order. The 2-value entry should be returned first. — haxtron, May 27 '14 at 11:43

wastl · Accepted Answer · 2014-05-27T11:50:56.607

1

If you check out the PriorityQueue Docs you will see, that

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()).

But

The queue retrieval operations poll, remove, peek, and element access the element at the >head of the queue.

Thus, if you use poll, or some of the other methods, you should get the elements in order
In order to achive a descending order of the Integers, you would have to change the comparison from

return lhs.getValue().compareTo(rhs.getValue());

to

return rhs.getValue().compareTo(lhs.getValue());

since the first orders the numbers in natural order (from smallest to largest)

edited May 27 '14 at 11:50

answered May 27 '14 at 11:45

wastl

2,643
14
27

I'm using poll(). And poll() should return the 2-value entry. The head element should be the largest. – haxtron May 27 '14 at 11:48
that's because your comparator uses the natural ordering of numbers – wastl May 27 '14 at 11:51
I should get the elements in order, but I don't. As I said, it's not my first time using this approach (with Double instead Integer), and worked great! – haxtron May 27 '14 at 11:52
i have edited my answer, please see the two return statements and adapt yours – wastl May 27 '14 at 11:53
Changing to return rhs.getValue().compareTo(lhs.getValue()); worked. Thanks man! – haxtron May 27 '14 at 11:54

PriorityQueue not sorting map by value

1 Answers1