Как перебрать приоритетную очередь?

Question

for (Event e : pq)

не повторяется в порядке приоритетов.

while(!pq.isEmpty()){
  Event e = pq.poll();
}

Это работает, но очищает очередь.

Answer 1

Из Javadocs :

Итератор, предоставленный в методе iterator(), не гарантирует прохождение элементов PriorityQueue в каком-либо конкретном порядке. Если вам нужен заказанный обход, рассмотрите возможность использования Arrays.sort(pq.toArray()).

Возможно, существуют другие эквивалентные механизмы.

Answer 2

Вы не можете пройти приоритетную очередь в этом порядке из-за базовой реализации (я думаю, что это минимальная куча в Java).Это не отсортированный массив, так что вы можете просто перейти от одного элемента к элементу с меньшим приоритетом.Просмотр - это постоянное время, потому что он смотрит на самый маленький элемент.Чтобы получить следующий (за O (log n) раз), вы должны удалить из очереди самый маленький элемент, вот как это работает.Выписка из очереди - это не просто удаление этого элемента, базовая структура перестраивает себя, чтобы сначала вывести элемент с наименьшим приоритетом.

Кроме того, пройти через всю очередь приоритетов - Olog (n)) операция.Таким образом, вы можете просто взять все элементы в очереди и отсортировать их (также O (n log (n))), а затем вы можете просматривать их по своему желанию.Единственным недостатком является то, что у вас есть дополнительная копия очереди.

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

Answer 3

Очередь приоритетов на основе кучи гарантирует только то, что первый элемент самый высокий / самый низкий.Не существует дешевого (то есть O (n)) способа получения элементов в отсортированной форме.

Если вам нужно делать это часто, рассмотрите возможность использования структуры, которая поддерживает элементы в отсортированной форме.Например, используйте java.util.TreeSet и используйте pollFirst() или pollLast() вместо peek() / poll()

Answer 4

Предыдущие постеры говорили, что все, но никто не дал полный рабочий пример (кроме копирования pq), так что вот оно:

Event[] events = pq.toArray(new Event[pq.size()]);
Arrays.sort(events, pq.comparator());
for (Event e : events) {
    System.out.println(e);
}

Answer 5

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

Итератор не возвращает элементы в правильном порядке, поскольку он печатает из базовой структуры данных (аналогично ArrayList). Данные ArrayList хранятся в нем таким же образом, как они хранятся в реализации Array BinaryHeap. Например:

PriorityQueue<Integer> pq = new PriorityQueue<>();
ArrayList<Integer> test = new ArrayList(Arrays.asList(6,12,7,9,2));
test.forEach(x -> pq.add(x)); 
System.out.println("Priority Queue:- "+pq); [2, 6, 7, 12, 9]

, где childOf (i) равно 2 * i + 1 и 2 * i + 2, а parentOf (i) равно (i-1) / 2

Answer 6

for (Event event: pq.toArray(new Event[pq.size()])) {
    event.toString();
}

Answer 7

Вы можете сделать копию очереди и опросить в цикле, в этом примере pq является исходной очередью приоритета:

PriorityQueue<Your_class> pqCopy = new PriorityQueue<Your_class>(pq);
while(!pqCopy.isEmpty()){
    Your_Class obj = pqCopy.poll();
    // obj is the next ordered item in the queue
    .....
}

Answer 8

Недавно у меня была такая же проблема.Я хотел использовать какой-то конкретный объект из очереди приоритетов, а затем сохранить оставшиеся элементы.

1) Я создал newPriorityQueue.2) Использовал Iterator для анализа каждого элемента в oldQueue 3) использовал метод oldQueue.poll () для извлечения элемента 4) вставил элемент 3) в newPriorityQueue, если не используется.

 Queue<String> newQueue = new PriorityQueue<String>(); 
    // Assuming that oldQueue have some data in it.

    Iterator<String> itr = oldQueue.iterator();
    while(itr.hasNext()){
        String str = oldQueue.poll();
        // do some processing with str
        if(strNotUsed){
            newQueue.offer(str);
        }
    }

В конце oldQueueбудет пустым.@ Другие: - Пожалуйста, предложите лучший способ, если я могу сделать то же самое.Я не могу использовать итератор, поскольку он не возвращает элементы в правильном порядке.

Answer 9

Метод peek() ничего не удаляет из очереди, но из-за этого он будет постоянно получать верхнее значение, пока не станет пустым. Я предполагаю, что вы проверили, не было ли оно пустым после цикла while, что даст вам такой вывод.

Единственный способ сделать это - отсортировать это самостоятельно. Вы можете получить оригинальный компаратор для него так:

Event[] events = Arrays.sort(pq.toArray(), pq.comparator());
for (Event e : events) {
    // do stuff
}