Почему при одинаковом приоритете объекты выводятся на экран не в том порядке, в котором были добавлены в очередь?

Question

Не совсем понимаю, почему при одинаковом приоритете (0) объекты выводятся на экран не в том порядке, в котором были добавлены в очередь PriorityQueue? То есть, после Maksim2 должен был идти Maksim3, но никак не Maksim5 (приоритет задаётся в конструкторе третьим параметром, и по нему работает метод compareTo()).

P.S: В чем тогда смысл PriorityQueue, если адекватно невозможно реализовать приоритеты и очередь? Проще модернизировать обычный Queue получается....

public static void main(String[] args) {
    Pacient p1 = new Pacient("Maksim1", 17,0);
    Pacient p2 = new Pacient("Maksim2", 17,0);
    Pacient p3 = new Pacient("Maksim3", 17,0);
    Pacient p4 = new Pacient("Maksim4", 17,0);
    Pacient p5 = new Pacient("Maksim5", 17,0);
    Pacient p6 = new Pacient("Maksim6", 11,1);
    PriorityQueue<Pacient> al = new PriorityQueue<>();
    
    al.add(p1);
    al.add(p2);
    al.add(p3);
    al.add(p4);
    al.add(p5);
    al.add(p6);
    
    while(al.size() > 0) {
        System.out.println(al.remove());
    }
    
}

Вывод:

{Maksim1; 17; 0}
{Maksim2; 17; 0}
**{Maksim5; 17; 0}** (почему-то идут раньше, чем Maksim3 (правило FIFO не работает) )
**{Maksim4; 17; 0}**
{Maksim3; 17; 0}
{Maksim6; 11; 1}

Answer 1

В документации PriorityQueue недвусмысленно указано, что элементы в очереди упорядочены либо в их естественном порядке (определённом в методе Comparable::compareTo), либо в соответствии с компаратором, заданным при создании очереди.
Если наименьшему значению ("голове" очереди) соответствует несколько элементов, такая неопределённость разрешается в произвольном порядке, а не в предполагаемом порядке вставки:

The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time...
The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily.

То есть, представленный код работает вполне корректно: при попытке прочитать множество элементов с одинаковым приоритетом из очереди приоритетов, их порядок не будет гарантирован.

Похожий вопрос: Порядок элементов в PriorityQueue.

Если нужно всё-таки обрабатывать элементы в порядке вставки, то достаточно написать класс-обёртку, сохраняющий порядок вставки, экземпляры которого и будут вставляться в очередь.

class PQItem<E extends Comparable<? super E>> implements Comparable<PQItem<E>> {
    private final static AtomicInteger counter = new AtomicInteger();
    private final int seq = counter.getAndIncrement();
    private final E item;

    public PQItem(E item) {
        this.item = item;
    }

    public E item() {
        return this.item;
    }

    @Override
    public int compareTo(PQItem<E> that) {
        if (this == that) return 0;
        int res = this.item.compare(that.item);
        if (res == 0) {
            res = Integer.compare(this.seq, that.seq);
        }
        return res;
    }
}

Соответственно, очередь будет создана и заполнена следующим образом:

PriorityQueue<PQItem<Pacient>> fifo = new PriorityQueue<>();

fifo.add(new PQItem(p1));
fifo.add(new PQItem(p2));
fifo.add(new PQItem(p3));
fifo.add(new PQItem(p4));
fifo.add(new PQItem(p5));
fifo.add(new PQItem(p6));

System.out.println("\nFIFO на очереди с приоритетами");
while(!fifo.isEmpty()) {
    System.out.println(fifo.remove().item());
}

Вывод:

FIFO на очереди с приоритетами
Pacient[name=Maksim1, num=17, pr=0]
Pacient[name=Maksim2, num=17, pr=0]
Pacient[name=Maksim3, num=17, pr=0]
Pacient[name=Maksim4, num=17, pr=0]
Pacient[name=Maksim5, num=17, pr=0]
Pacient[name=Maksim6, num=11, pr=1]

Онлайн демо

БЛОГ НА HUSL

Почему при одинаковом приоритете объекты выводятся на экран не в том порядке, в котором были добавлены в очередь?

Ответы (1 шт):