VPF::работа PriorityQueue - Форум программистов

Pawl

Дата 30.1.2012, 12:19 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Доброго времени суток! Тут поднимался вопрос по PriorityQueue, и мне стало любопытно, как эта штука работает. В доке нашел, что

Цитата

The elements of the priority queue are ordered according to their natural ordering

То есть, в этом коде

Код


import java.util.PriorityQueue;

public class NewSet {
    private static PriorityQueue<Integer> t = new PriorityQueue<Integer>();

    static {
        t.add(7);
        t.add(5);
        t.add(5);
        t.add(5);
        t.add(5);
    }
    
    public static void main(String[] args) {
        System.out.println(t);
    }
}

вывод, по идее, должен быть таким:

Цитата

[5, 5, 5, 5, 7]

Но он почему-то такой:

Цитата

[5, 5, 5, 7, 5]

Может, кто подскажет, почему тут не наблюдается natural ordering?
Спасибо!

--------------------

В действительности всё совсем не так, как на самом деле

Stolzen

Дата 30.1.2012, 12:25 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: 23
Всего: 48

Потому что внутри PriorityQueue, скорее всего, построена на куче. А natural ordering будет если последовательно элементы вытаскивать.

Это сообщение отредактировал(а) Stolzen - 30.1.2012, 12:26

--------------------

datatalks.ru - анализ данных, статистика, машинное обучение

Pawl

Дата 30.1.2012, 13:04 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Цитата(Stolzen @ 30.1.2012, 12:25

)

если последовательно элементы вытаскивать.

Это как? Если пулом, то нет - я в коде выше добавил

Код


        System.out.println(t.poll());
        System.out.println(t);

Так у меня получилось

Код


[5, 5, 5, 7, 5]
5
[5, 5, 5, 7]

--------------------

В действительности всё совсем не так, как на самом деле

Stolzen

Дата 30.1.2012, 13:10 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: 23
Всего: 48

Код


List<Integer> list = new ArrayList<Integer>();

PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
queue.addAll(Arrays.asList(10, 9, 5, 9, 5, 6, 10));

while (!queue.isEmpty()) {
    list.add(queue.poll());
}

System.out.println(list);

[5, 5, 6, 9, 9, 10, 10]

Добавлено через 1 минуту и 15 секунд
Сортировка кучей именно так и работает - с помощью последовательного вытаскивания из кучи элементов

--------------------

datatalks.ru - анализ данных, статистика, машинное обучение

Pawl

Дата 30.1.2012, 16:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Цитата(Stolzen @ 30.1.2012, 13:10

)

Сортировка кучей именно так и работает - с помощью последовательного вытаскивания из кучи элементов

Спасибо! Понятно теперь, где собака порылась! smile

Однако, интересно, в каких случаях применяются такие танцы с бубнами? Разве так

Код


List<Integer> list = Arrays.asList(10, 9, 5, 9, 5, 6, 10);
Collections.sort(list);
System.out.println(list);

не делается то же самое, только с меньшим количеством кода?

--------------------

В действительности всё совсем не так, как на самом деле

Stolzen

Дата 30.1.2012, 16:50 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: 23
Всего: 48

Ну вам же не отсортировать нужно. А куча очень удобно подошла на роль коллекции, лежащей в основе под очередью с приоритетом - так как в очереди обычно важен самый первый элемент, а в куче это как раз минимальный/максимальный (т.е. с наивысшим приоритетом).

Это сообщение отредактировал(а) Stolzen - 30.1.2012, 16:51

--------------------

datatalks.ru - анализ данных, статистика, машинное обучение

Pawl

Дата 30.1.2012, 17:02 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Благодарю, кое-что для себя с Вашей помощью прояснил.

--------------------

В действительности всё совсем не так, как на самом деле

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »