Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Kw1nT
0 / 0 / 0
Регистрация: 07.11.2012
Сообщений: 16
#1

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

22.12.2013, 13:20. Просмотров 1285. Ответов 4
Метки нет (Все метки)

Добрый день друзья. Нужна ваша помощь в решении одной проблемы.
Суть проблемы в том что я в програмировании еще новичок но задача тяжелая для моего уровня программирования. Поэтому прошу вашей помощи в решении этой задачи ...
Нужно построить приоритетную очередь в С + + (консоли ) , чтобы когда мы добавляли или удаляли элементы в очередь ( из очереди ) мы указывали приоритет элемента.
И чтобы была возможность вывода информациии об очереди, всмысле обо всех элементах в ней ...

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


Приоритетная очередь - это очередь , в которой важно не то , кто стал последним (порядок перемещения в ней не играет роли) , а кто главнее. Более точно , при помещении в очередь указывается приоритет объекта помещается ( будем считать приоритеты целыми числами) , а при получении из очереди выбирается элемент с наибольшим приоритетом ( или один из таких элементов) .
Реализовать приоритетную очередь так , чтобы помещение и получения элемента требовали логарифмического числа действий (от размера очереди) .
Указания к решению . Согласно алгоритма сортировки деревом (в его окончательном варианте ) , будем размещать элементы очереди в массиве x [ 1 ] .. x [ k ] , поддерживая такое свойство : x [i] старше ( имеет больший приоритет) своих сыновей x [ 2 и ] и x [ 2 и +1 ] , если таковые существуют - и , следовательно , всякий элемент старше своих потомков. (Ведомости о приоритетах также хранятся в массиве , так что мы имеем дело с массивом пар ( элемент , приоритет) . ) Удаление элемента с сохранением этого свойства описано в алгоритме сортировки. Надо еще уметь восстанавливать свойство после добавления элемента в конец . Это делается так :
****t = номер добавленного элемента
****{ инвариант : в дереве любой предок приоритетнее потомка ,
********если этот потомок - не t }
****while t - не корень и t старше своего отца do begin
****| Поменять t с его отцом
****end ;
Если очередь образуют граждане , стоящие в вершинах дерева , т.е. за каждым стоит двое , а перед каждым (кроме первого) - один , то смысл этого алгоритма ясен: встав в конец , приоритетный гражданин начинает пробираться к началу , вытесняя тех , кто стоит перед ним - пока не встретит более приоритетного .
Замечания. Приоритетное очередь естественно использовать при моделировании процессов , протекающих во времени . При этом элементы очереди - это ожидаемые события , а их приоритет определяется временем , когда они произойдут.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.12.2013, 13:20
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Приоритетная очередь (C++):

Приоритетная очередь - C++
Здравствуйте. У меня есть небольшая проблема с приоритетной очередью. Я имею задачу. Мне даются фамилии и оценки, нужно вывести фамилии и...

Приоритетная очередь и конструктор копии - C++
День добрый, форумчане! Прошу просвятить в таком вопрос: -имеется класс, и в мейне пытаюсь запихнуть объекты этого класса в очередь с...

Сформировать очередь по файлу целых чисел. Промоделировать очередь в супермаркете - C++
Сформировать очередь по файлу целых чисел. Промоделировать очередь в супермаркете. В каждый момент времени происходит одно из событий:...

Очередь (сделать очередь, чтобы добавляло, удаляло, читало. Не STL.) - C++
Помогите пожалуйста написать очередь. Есть Температура double и ее тип int ну и нужно сделать очередь, чтобы добавляло, удаляло, читало....

Задача на очередь (вывод сообщения, что очередь пуста) - C++
Доброго дня! Есть задачка на очередь, которая работает нормально, только надо добавить код, чтобы выводил сообщение, что очередь пуста.....

Очередь, теория. Очередь на шести стеках - C++
Здравствуйте, пытаюсь побольше найти информации про очереди и их применение в программировании. Из того что я нашел, все описывается лишь...

4
ZeR_0
117 / 109 / 37
Регистрация: 30.01.2013
Сообщений: 297
22.12.2013, 13:35 #2
Вам нужен heapsort (сортировка кучей) - это одна из разновидностей древовидной сортировки
1
Kw1nT
0 / 0 / 0
Регистрация: 07.11.2012
Сообщений: 16
22.12.2013, 17:56  [ТС] #3
Цитата Сообщение от ZeR_0 Посмотреть сообщение
Вам нужен heapsort (сортировка кучей) - это одна из разновидностей древовидной сортировки
А можно пожалуйста подробнее. Или с каким-то примером ..
0
gazlan
3133 / 1909 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
22.12.2013, 18:07 #4
Priority queue
manage a priority queue as a heap
1
Kw1nT
0 / 0 / 0
Регистрация: 07.11.2012
Сообщений: 16
22.12.2013, 18:16  [ТС] #5
Цитата Сообщение от gazlan Посмотреть сообщение
Спасибо большое...
0
22.12.2013, 18:16
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.12.2013, 18:16
Привет! Вот еще темы с ответами:

Создать очередь. Добавить элемент в очередь. Удалить элемент из очереди - C++
Нужно создать очередь. Добавить элемент в очередь. Удалить элемент из очереди. Вот моё "творение". int main() { int...

Очередь - C++
В чем проблема? не хочет запускаться код? Ошибки следующие: #include <iostream> #include <queue> using namespace std; ...

Очередь - C++
Описать структуру с именем TRAIN, содержащую следующие поля: - название пункта назначения - номер поезда - время отправления ...

Очередь - C++
Задача проги сделать очередь, по сути прога написана по лекции, но выдает ошибки с преобразованием параметра, понимаю, что ошибки глупые,...


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

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

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