Проблема с приоритетной очередью

Я пытаюсь использовать приоритетную очередь в своем коде, и по какой-то причине, когда я удаляю объекты, они не по порядку. Вы знаете, что я делаю неправильно? Вот мой код:

конструктор:

recordedsong = new PriorityQueue<recordedNote>(50, new Comparator<recordedNote>()
        {
            public int compare(recordedNote n1, recordedNote n2)
            {
                long l = n1.rt()-n2.rt();
                int i = (int)l;
                return i;
            }
        });

где каждая записанная заметка имеет длинное значение, возвращаемое методом rt().

Но когда я звоню

while (!Song.isEmpty())
        {
            recordedNote temp = (recordedNote)Song.remove();

а затем напечатайте temp.rt() для каждого, все числа не по порядку. И не просто в обратном порядке, а повсюду, например, 1103, 0, 500, 0, 220 таких порядков.

Вы видите, что-нибудь не так с моим конструктором?

Спасибо!


java priority-queue
person user607545    schedule 08.02.2011    source источник
comment
вы используете add() или offer() для вставки в очередь?   -  person Joe Phillips    schedule 08.02.2011
comment
Что такое Песня, кстати? Я не вижу это как объявленную переменную или класс.   -  person Hovercraft Full Of Eels    schedule 08.02.2011

Ответы (3)


arrow_upward
2
arrow_downward

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

import java.util.Comparator;
import java.util.PriorityQueue;

public class TestPriorityQueue {
    public static void main(String[] args) {
        long[] noteTimes = {1103L, 0L, 500L, 0L, 220L, 1021212812012L};
        PriorityQueue<RecordedNote> noteQueue = new PriorityQueue<RecordedNote>(10,
                    new Comparator<RecordedNote>() {
                        @Override
                        public int compare(RecordedNote o1, RecordedNote o2) {
                            Long time1 = o1.getTime();
                            Long time2 = o2.getTime();

                            // uses Long's built in compareTo method, so we 
                            //don't have to worry as much about edge cases.
                            return time1.compareTo(time2); 
                        }
                    });
        for (int i = 0; i < noteTimes.length; i++) {
            RecordedNote note = new RecordedNote(noteTimes[i]);
            System.out.println(note);
            noteQueue.add(note);
        }
        System.out.println();
        while (noteQueue.size() > 0) {
            System.out.println(noteQueue.remove());
        }
    }
}

class RecordedNote {
    private long time;

    public RecordedNote(long time) {
        this.time = time;
    }

    public long getTime() {
        return time;
    }

    @Override
    public String toString() {
        return "[Time: " + time + "]";
    }
}

Вот и возникает вопрос, почему у вас не работает? Лично я не вижу в вашем вопросе достаточно связного кода, чтобы ответить на него. Мы не уверены, что такое Song, поскольку я не вижу, чтобы это было объявлено как класс или переменная, и я также не вижу, где вы где-либо используете свою переменную PriorityQueue, записанную песню. Поэтому я предлагаю вам сделать то же, что и я: создать небольшую компилируемую исполняемую программу, которую мы можем запускать и изменять, и которая демонстрирует вашу проблему, http://sscce.org

person Hovercraft Full Of Eels    schedule 08.02.2011

arrow_upward
0
arrow_downward

Я предполагаю, что есть вероятность, что я получу 0. Поэтому измените метод сравнения, чтобы он возвращал положительное значение, а не результат.

person Ria_546    schedule 08.02.2011
comment
Что не так с возвратом 0? Что не так с возвратом -1? - person Hovercraft Full Of Eels; 08.02.2011
comment
@Hovercraft Full Of Eels: я попробовал ваш код, и теперь он работает. Спасибо! - person user607545; 08.02.2011

arrow_upward
0
arrow_downward

При чтении документации по API для PriorityQueue говорится следующее:

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

Я предполагаю, что remove() также не обязан следовать естественному порядку.

person Tom G    schedule 08.02.2011
comment
Я не согласен. remove имеет то же поведение, что и poll, и удаляет из головы очереди, за исключением того, что remove создает исключение, если очередь пуста. И при проверке удаление работает нормально. Пожалуйста, смотрите мой пост с ответом. - person Hovercraft Full Of Eels; 08.02.2011
comment
Доказательства побеждают каждый раз - голосование за ваш ответ. - person Tom G; 08.02.2011