Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

PriorityQueue.toString wrong element order

I am trying to make a priority queue in java with the nodes with the lowest frequency in priority. However, my comparator is not working and the output is very weird. I believe I need to change my comparator but I am not sure how to change it. Here is my code:

public class HuffmanComparator implements Comparator<TreeNodeHuffman> {
    public int compare(TreeNodeHuffman p1, TreeNodeHuffman p2) {
        if (p1.frequency < p2.frequency) return -1;
        if (p1.frequency > p2.frequency) return 1;
        return 0;
    }    
}

public class TreeNodeHuffman {
public static void main(String[] args) {    
    HuffmanComparator compare = new HuffmanComparator();
    TreeNodeHuffman e = new TreeNodeHuffman('e', 12702);
    TreeNodeHuffman t = new TreeNodeHuffman('t', 9056);
    TreeNodeHuffman a = new TreeNodeHuffman('a', 8167);
    TreeNodeHuffman o = new TreeNodeHuffman('o', 7507);
    TreeNodeHuffman i = new TreeNodeHuffman('i', 6966);
    TreeNodeHuffman n = new TreeNodeHuffman('a', 6749);
    TreeNodeHuffman s = new TreeNodeHuffman('s', 6327);
    TreeNodeHuffman h = new TreeNodeHuffman('h', 6094);
    TreeNodeHuffman r = new TreeNodeHuffman('r', 5987);
    TreeNodeHuffman d = new TreeNodeHuffman('d', 4253);
    TreeNodeHuffman l = new TreeNodeHuffman('l', 4025);
    TreeNodeHuffman c = new TreeNodeHuffman('c', 2782);
    TreeNodeHuffman u = new TreeNodeHuffman('u', 2758);
    TreeNodeHuffman m = new TreeNodeHuffman('m', 2406);
    TreeNodeHuffman w = new TreeNodeHuffman('w', 2360);
    TreeNodeHuffman f = new TreeNodeHuffman('f', 2228);
    TreeNodeHuffman g = new TreeNodeHuffman('g', 2015);
    TreeNodeHuffman y = new TreeNodeHuffman('y', 1974);
    TreeNodeHuffman p = new TreeNodeHuffman('p', 1929);
    TreeNodeHuffman b = new TreeNodeHuffman('b', 1492);
    TreeNodeHuffman v = new TreeNodeHuffman('v', 978);
    TreeNodeHuffman k = new TreeNodeHuffman('k', 772);
    TreeNodeHuffman j = new TreeNodeHuffman('j', 153);
    TreeNodeHuffman x = new TreeNodeHuffman('x', 150);
    TreeNodeHuffman q = new TreeNodeHuffman('q', 95);
    TreeNodeHuffman z = new TreeNodeHuffman('z', 74);
    PriorityQueue<TreeNodeHuffman> queue = new PriorityQueue<TreeNodeHuffman>(26, compare);
    queue.add(e);
    queue.add(t);
    queue.add(a);
    queue.add(o);
    queue.add(i);
    queue.add(n);
    queue.add(s);
    queue.add(h);
    queue.add(r);
    queue.add(d);
    queue.add(l);
    queue.add(c);
    queue.add(u);
    queue.add(m);
    queue.add(w);
    queue.add(f);
    queue.add(g);
    queue.add(y);
    queue.add(p);
    queue.add(b);
    queue.add(v);
    queue.add(k);
    queue.add(j);
    queue.add(x);
    queue.add(q);
    queue.add(z);
    System.out.println(queue);
}
}

The output is as follows: [z, k, q, g, v, x, u, d, f, y, b, m, j, i, c, e, s, o, w, a, r, h, p, t, l, a].

However, the output should be [z, q, x, j, k, v, b........].

like image 742
loolooo Avatar asked Jan 06 '15 20:01

loolooo


Video Answer


1 Answers

You need to poll the items from the PriorityQueue one by one. toString doesn't do that.

So instead of your System.out.println(queue); do this:

while(!queue.isEmpty()) {
   System.out.println(queue.poll());
}

The reason is that the PriorityQueue is never completely sorted internally, lookup how a heap works for more detail. Polling items from it fixes the heap during the calls, thus it should output the elements in sorted order.

like image 106
Thomas Jungblut Avatar answered Oct 04 '22 17:10

Thomas Jungblut