Форум программистов, компьютерный форум CyberForum.ru

Приоритетная очередь - C++

Восстановить пароль Регистрация
 
Kw1nT
0 / 0 / 0
Регистрация: 07.11.2012
Сообщений: 16
22.12.2013, 13:20     Приоритетная очередь #1
Добрый день друзья. Нужна ваша помощь в решении одной проблемы.
Суть проблемы в том что я в програмировании еще новичок но задача тяжелая для моего уровня программирования. Поэтому прошу вашей помощи в решении этой задачи ...
Нужно построить приоритетную очередь в С + + (консоли ) , чтобы когда мы добавляли или удаляли элементы в очередь ( из очереди ) мы указывали приоритет элемента.
И чтобы была возможность вывода информациии об очереди, всмысле обо всех элементах в ней ...

-----------------------------------------------------------------------------------------------------------------------
P.S Вот кстати полное условие этой задачи но она как на меня слишком умна ... Большое спасибо за любую указанную помощь ...


Приоритетная очередь - это очередь , в которой важно не то , кто стал последним (порядок перемещения в ней не играет роли) , а кто главнее. Более точно , при помещении в очередь указывается приоритет объекта помещается ( будем считать приоритеты целыми числами) , а при получении из очереди выбирается элемент с наибольшим приоритетом ( или один из таких элементов) .
Реализовать приоритетную очередь так , чтобы помещение и получения элемента требовали логарифмического числа действий (от размера очереди) .
Указания к решению . Согласно алгоритма сортировки деревом (в его окончательном варианте ) , будем размещать элементы очереди в массиве x [ 1 ] .. x [ k ] , поддерживая такое свойство : x [i] старше ( имеет больший приоритет) своих сыновей x [ 2 и ] и x [ 2 и +1 ] , если таковые существуют - и , следовательно , всякий элемент старше своих потомков. (Ведомости о приоритетах также хранятся в массиве , так что мы имеем дело с массивом пар ( элемент , приоритет) . ) Удаление элемента с сохранением этого свойства описано в алгоритме сортировки. Надо еще уметь восстанавливать свойство после добавления элемента в конец . Это делается так :
****t = номер добавленного элемента
****{ инвариант : в дереве любой предок приоритетнее потомка ,
********если этот потомок - не t }
****while t - не корень и t старше своего отца do begin
****| Поменять t с его отцом
****end ;
Если очередь образуют граждане , стоящие в вершинах дерева , т.е. за каждым стоит двое , а перед каждым (кроме первого) - один , то смысл этого алгоритма ясен: встав в конец , приоритетный гражданин начинает пробираться к началу , вытесняя тех , кто стоит перед ним - пока не встретит более приоритетного .
Замечания. Приоритетное очередь естественно использовать при моделировании процессов , протекающих во времени . При этом элементы очереди - это ожидаемые события , а их приоритет определяется временем , когда они произойдут.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ZeR_0
116 / 108 / 37
Регистрация: 30.01.2013
Сообщений: 297
22.12.2013, 13:35     Приоритетная очередь #2
Вам нужен heapsort (сортировка кучей) - это одна из разновидностей древовидной сортировки
Kw1nT
0 / 0 / 0
Регистрация: 07.11.2012
Сообщений: 16
22.12.2013, 17:56  [ТС]     Приоритетная очередь #3
Цитата Сообщение от ZeR_0 Посмотреть сообщение
Вам нужен heapsort (сортировка кучей) - это одна из разновидностей древовидной сортировки
А можно пожалуйста подробнее. Или с каким-то примером ..
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,921
Записей в блоге: 1
22.12.2013, 18:07     Приоритетная очередь #4
Priority queue
manage a priority queue as a heap
Kw1nT
0 / 0 / 0
Регистрация: 07.11.2012
Сообщений: 16
22.12.2013, 18:16  [ТС]     Приоритетная очередь #5
Цитата Сообщение от gazlan Посмотреть сообщение
Спасибо большое...
Yandex
Объявления
22.12.2013, 18:16     Приоритетная очередь
Ответ Создать тему
Опции темы

Текущее время: 07:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru