If t^.data<q^.data Then Begin

Swap(t^.data,q^.data);

Push(q);

End;

End;

End;

Очередь с приоритетом на базе двоичной кучи

Очередью с приоритетами называют множество элементов, на котором задана функция приоритета, то есть для каждого элемента a множества вычисляется его приоритет – f (a) (обычно действительное значение) и выполняются следующие операции:

· поиск элемента с наивысшим (наибольшим) приоритетом (Search);

· удаление (извлечение) элемента с наибольшим приоритетом (Extract);

· добавление (включение) нового элемента в множество (Insert).

Значение приоритета определяют как ключ. Обычно сопутствующую информацию не рассматривают. В реальных задачах она перемещается в структуре данных вместе с ключом.

Наиболее приемлемой с точки зрения времени выполнения всех операций структурой данных для реализации очереди с приоритетом является двоичная куча. Пусть для представления кучи используется массив. Операция Search выполняется путем чтения первого элемента кучи, он имеет наибольший приоритет или значение ключа (время – О (1)). При выполнении операции Extract первый элемент кучи удаляется (извлекается), на его место записывается последний элемент кучи, размер кучи уменьшается на единицу, и новый первый элемент проталкивается по куче с помощью операции Push (п. 7.1). Время выполнения операции – O (log ₂ n), оно определяется временем выполнения Push.

Осталось разобрать логику выполнения операции Insert. Поясним ее на примере. Пусть есть куча (массив A), её начальное состояние приведено в первой строке табл. 7.2, и требуется вставить элемент с ключом 15. Размер кучи увеличивается на один элемент – это место отмечено в табл. 7.2 символом «█». А затем значение нового ключа сравнивается с ключом родителя (A[6]). Если он больше, то ключ родителя переписывается на место, отмеченное █, а место перемещается «вверх по куче» в позицию родителя. Эти действия продолжаются до тех пор, пока не будет найдено положение элемента в куче, то есть свойство последней должно выполняться. В рассматриваемом примере элемент вставляется на первое место.

Таблица 7.2

Номер шага	А
1	2	3	4	5	6	7	8	9	10	11	12
Начальное состояние												█
После 1-го шага						█
После 2-го шага			█
После 3-го шага	█
Результат

Графическое изображение этого процесса приведено на рис. 7.7. Символ █ изображен на рис. 7.7 пустым кружком.

Рис. 7.7. Вставка элемента с ключом 15 в кучу

Формализованная запись рассмотренных действий имеет вид:

Procedure Insert(x: Integer);

Var i: Integer;

Begin

n:=n+1;

i:=n;

Дата добавления: 2015-07-11