Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
ddvamp1
2 / 1 / 1
Регистрация: 11.08.2019
Сообщений: 14
1

Выбор оптимальной структуры для очереди с приоритетом

11.08.2019, 20:39. Просмотров 300. Ответов 5

Собственно, вопрос в заголовке. Как осуществить такой выбор, то есть от чего зависит выбор структуры для данного АТД. Читал про различные виды куч, включая Фибоначчиеву и кучу Бродала-Окасаки, но нигде не смог найти (видимо плохо искал), когда какую выбирать. Если конкретно, интересует выбор структуры для priority queue для реализации алгоритма Форчуна (для очереди событий), библиотечные функции просьба не предлагать.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.08.2019, 20:39
Ответы с готовыми решениями:

Выбор оптимальной структуры данных
Здравствуйте! Задача состоит в следующем. Есть большой файл (~68 mb) с текстом. Нужно посчитать...

Очередь с приоритетом. Элементы с наивысшим приоритетом ставятся в начало очереди, с наименьшим – в конец
Здравствуйте! имеется задание: создать очередь с приоритетом (у каждого элемента свой приоритет)....

Выбор оптимальной видекарты для системы:
Core 2 Duo E4300 1.8 2 gb ddr2 667 Asus P5B Блок питания 450 W пока выбор пал на MSI Radeon...

Выбор оптимальной видеокарты для AMD A10 7850k
1) Системная плата Gigabyte G1.Sniper A88X (FM2+) 2) Процессор AMD A10 7850k, 3.70 ГГц 3) Блок...

Очереди с приоритетом
Написать функции для работы с очередями с приоритетом. Создание очереди из N элементов (N и...

5
Shamil1
Модератор
2327 / 1617 / 363
Регистрация: 26.03.2015
Сообщений: 5,884
12.08.2019, 11:48 2
Цитата Сообщение от ddvamp1 Посмотреть сообщение
но нигде не смог найти (видимо плохо искал), когда какую выбирать
Всегда выбирайте двоичную кучу (пирамиду). Другие кучи рассматривайте, только если можете чётко сформулировать, почему двоичная куча Вам не подходит.
0
ddvamp1
2 / 1 / 1
Регистрация: 11.08.2019
Сообщений: 14
17.08.2019, 17:10  [ТС] 3
Цитата Сообщение от Shamil1 Посмотреть сообщение
Всегда выбирайте двоичную кучу
Но почему именно двоичную, чем она превосходит другие? И мне нужна возможность удалять произвольный элемент, что двоичная не предоставляет.
0
ddvamp1
2 / 1 / 1
Регистрация: 11.08.2019
Сообщений: 14
18.08.2019, 19:37  [ТС] 4
Цитата Сообщение от ddvamp1 Посмотреть сообщение
что двоичная не предоставляет
Хотя можно хранить указатель на элемент массива и по необходимости уменьшать значение ключа.
0
Shamil1
Модератор
2327 / 1617 / 363
Регистрация: 26.03.2015
Сообщений: 5,884
19.08.2019, 12:14 5
Цитата Сообщение от ddvamp1 Посмотреть сообщение
Но почему именно двоичную, чем она превосходит другие?
Простотой. Другие варианты дают дополнительные возможности за счёт усложнения кода и потери производительности. Использовать, только если точно знаете, зачем Вам эти дополнительные возможности.

Цитата Сообщение от ddvamp1 Посмотреть сообщение
И мне нужна возможность удалять произвольный элемент, что двоичная не предоставляет.
Если удалить произвольный элемент, то нарушится инвариант "Последний слой заполняется слева направо без «дырок»". Но можно поменять значение ключа произвольного элемента (нужна прямая ссылка на него). После изменения ключа необходимо вызвать MoveUp() или MoveDown(), в зависимости от того, как поменялось значение.

Есть два варианта (мне больше нравится второй):
1. Поменять на Int32.MaxValue (элемент станет корнем) и затем удалить.
2. Поменять на Int32.MinValue и оставить. Затем уменьшить размер кучи так, чтобы последний элемент был не фиктивным.
0
Shamil1
Модератор
2327 / 1617 / 363
Регистрация: 26.03.2015
Сообщений: 5,884
20.08.2019, 10:53 6
Можно удалять по почти стандартной схеме:
3. Заменять удаляемый элемент на последний. Затем выполнять MoveUp() или MoveDown().
0
20.08.2019, 10:53
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.08.2019, 10:53

Реализация очереди с приоритетом
Просьба удалить тему. Решил проблему самостоятельно.

Создание очереди с приоритетом
Здравствуйте, нужна программа, которая создает очередь с приоритетом (натуральное число от 0 до 10)...

Интересное применение очереди с приоритетом (priority_queue)
Здравствуйте, уважаемые пользователи данного форума! Изучая деки, стеки и очереди дошел до такого...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru