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

Question

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?

Amadan · Accepted Answer · 2019-05-30 04:42:34Z

2

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.

answered May 30, 2019 at 4:42

Amadan

200k23 gold badges252 silver badges321 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

CHOCO BLOCK Over a year ago

Ah yes, I just tested it now and it polls correctly. I am actually attempting to design a program that follows HuffmanCoding, which I believe requires a Priority Queue first. However I am sure it can be implemented in many different ways.

Collectives™ on Stack Overflow

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

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related