Как перебирать PriorityQueue?

Ответ 1

Из Javadocs:

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

Есть, вероятно, другие эквивалентные механизмы.

Ответ 2

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

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

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

Ответ 3

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

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

Ответ 4

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

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

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

Ответ 5

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

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 будет пустым. @Другие: - пожалуйста, предложите лучший способ, если я смогу сделать то же самое. Я не могу использовать итератор, поскольку он не возвращает элементы в правильном порядке.

Ответ 6

Вы можете сделать копию очереди и опроса в цикле, в этом примере 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
    .....
}

Ответ 7

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

Итератор не возвращает элементы в правильном порядке, потому что он печатает из базовой структуры данных (аналогично ArrayList). ArrayList имеет данные, хранящиеся в нем, таким же образом, что данные хранятся в реализации массива 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 * я + 1 и 2 * я + 2, а parentOf (i) - (i-1)/2

Ответ 8

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