CODEWITHSUNDEEP
java
CHOCO BLOCK
CHOCO BLOCK

Reputation: 91

Sorting a Priority Queue with Objects made from a Map (values)

I have a problem with my Priority Queue not sorting my object values properly.

My code takes a String of text and gets the number of unique characters with also counting the frequency of each unique character. It is then put into a map of type Character and Integer with the Key and Value being assigned respectively.

It then takes each entry of the map and puts it into a PQNode object, also of type Character, Integer, then offers it to the Priority Queue.

The priority queue is to sort the PQNodes by the frequency (value) from lowest to highest via the compareTo method in PQNode.java

I have tried searching around on the web and trying to put in into a list to sort it but no luck.

public class Counting { 
public Counting(String text) {
    text = "mississippi river";
    Queue<PQNode> fringe = new PriorityQueue<>(); 
    char[] letters = text.toCharArray(); 
    Map<Character, Integer> frequency = new HashMap<>(); 

    for(char letter : letters) {
        if(frequency.containsKey(letter)) { 
            frequency.put(letter, frequency.get(letter) + 1);
        }
        else {frequency.put(letter, 1);} 
        }

    for(Map.Entry<Character, Integer> element : frequency.entrySet()) {
        PQNode pqN = new PQNode(element.getKey(), element.getValue());
        fringe.offer(pqN); 
    }
    System.out.println(fringe);
    }
}

public class PQNode implements Comparable<PQNode>{
    Character c;
    int freq;

    public PQNode(Character c, int freq) {
        this.c = c;
        this.freq = freq;
    }

    public String toString() {
        return "[c=" + c + ", freq=" + freq + "]";
    }

    public int compareTo(PQNode otherFreq) {
        return Integer.compare(this.freq, otherFreq.freq);
    }
}

The expected output is: [[c= , freq=1], [c=e, freq=1], [c=v, freq=1], [c=m, freq=1], [c=p, freq=2], [c=r, freq=2], [c=s, freq=4], [c=i, freq=5]]

But the actual output is: [[c= , freq=1], [c=e, freq=1], [c=v, freq=1], [c=m, freq=1], [c=p, freq=2], [c=r, freq=2], [c=i, freq=5], [c=s, freq=4]]

Where frequency is equal to 1, the order doesn't really matter but the last two elements are in the wrong order. Any ideas?

Upvotes: 0

Views: 458

Answers (1)

Amadan
Amadan

Reputation: 198324

PriorityQueue doesn't guarantee it will be sorted. PriorityQueue guarantees that the next item received from poll and peek will be the least. If you want your items in order, you have to poll them out one by one, not print the PriorityQueue as is.

If you are looking for a structure that will be sorted, a TreeSet might be better, or maybe a plain old ArrayList that you explicitly sort after you insert all the elements.

Upvotes: 2

Related Questions