Я пытаюсь сделать очередь приоритетов в java с узлами с наименьшей частотой в приоритете. Однако мой компаратор не работает, и выход очень странный. Я считаю, что мне нужно изменить свой компаратор, но я не уверен, как его изменить. Вот мой код:
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);
}
}
Выход следующий: [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]. Однако выход должен быть [z, q, x, j, k, v, b........]. Спасибо заранее!
Вам нужно опросить элементы из PriorityQueue один за другим. toString не делает этого.
Поэтому вместо вашего System.out.println(queue); сделайте следующее:
while(!queue.isEmpty()) {
System.out.println(queue.poll());
}
Причина в том, что PriorityQueue никогда полностью не сортируется внутри, посмотрите, как куча работает более подробно. Опрос элементов из него фиксирует кучу во время вызовов, поэтому он должен выводить элементы в отсортированном порядке.
System.out.println(queue) печатает очередь несортированную. Если вы хотите распечатать реальный порядок очереди, следуйте нижеприведенному коду, который использует опрос, чтобы получить элементы из очереди сверху вниз:
TreeNodeHuffman tn = null;
do{
tn = queue.poll();
if(tn!=null){
System.out.print(tn.key+",");
}
}while(tn != null);
и вы увидите этот результат как ожидалось:
г, д, х, J, K, V, Ь, р, у, г, е, ж, м, и, с, л, д, г, д, с, а, я, о, а, т, е,
Вы хотите, чтобы более низкая частота повышалась так:
public int compare(TreeNodeHuffman p1, TreeNodeHuffman p2) {
if (p1.frequency < p2.frequency) return 1;
if (p1.frequency > p2.frequency) return -1;
return 0;
}
}
Если вы хотите протестировать его, отправьте его в один пул с потоком и посмотрите порядок обрабатываемых заданий вместо строки или итератора. как говорит doc на http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#iterator%28%29:
Возвращает итератор по элементам в этой очереди. Итератор не возвращает элементы в каком-либо конкретном порядке.
Можно просмотреть http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Executors.html#newSingleThreadExecutor%28%29 для быстрого однопоточного пула, чтобы проверить это.