Приоритетные очереди

Приоритетной очередью (priority queue) легко управлять при помощи процедур BuildHeap и HeapPushDown. Если в качестве приоритетной очереди используется пирамида, легко найти элемент с самым высоким приоритетом — он всегда находится на вершине пирамиды. Но если его удалить, получившееся дерево без корня уже не будет пирамидой.

Для того, чтобы снова превратить дерево без корня в пирамиду, возьмем последний элемент (самый правый элемент на нижнем уровне) и поместим его на вершину пирамиды. Затем при помощи процедуры HeapPushDown продвинем новый корневой узел вниз по дереву до тех пор, пока дерево снова не станет пирамидой. В этот момент, можно получить на выходе приоритетной очереди следующий элемент с наивысшим приоритетом.

Public Function Pop() As Long

If NumInQueue < 1 Then Exit Function

' Удалить верхний элемент.

Pop = Pqueue(1)

' Переместить последний элемент на вершину.

PQueue(1) = PQueue(NumInPQueue)

NumInPQueue = NumInPQueue - 1

' Снова сделать дерево пирамидой.

HeapPushDown PQueue(), 1, NumInPQueue

End Function

Чтобы добавить новый элемент к приоритетной очереди, увеличьте пирамиду. Поместите новый элемент на свободное место в конце массива. Полученное дерево также не будет пирамидой.

Чтобы снова преобразовать его в пирамиду, сравните новый элемент с его родителем. Если новый элемент больше, поменяйте их местами. Заранее известно, что второй потомок меньше, чем родитель, поэтому нет необходимости сравнивать новый элемент с другим потомком. Если элемент больше родителя, то он также больше и второго потомка.

Продолжайте сравнение нового элемента с родителем и перемещение его по дереву, пока не найдется родитель, больший, чем новый элемент. В этот момент, дерево снова представляет собой пирамиду, и приоритетная очередь готова к работе.

Private Sub HeapPushUp(List() As Long, ByVal max As Integer)

Dim tmp As Long

Dim j As Integer

tmp = List (max)

Do

j = max \ 2

If j < 1 Then Exit Do

If List(j) < tmp Then

List (max) = List(j)

max = j

Else

Exit Do

End If

Loop

List(max) = tmp

End Sub

Подпрограмма Push добавляет новый элемент к дереву и использует подпрограмму HeapPushDown для восстановления пирамиды.

Public Sub Push (value As Long)

NumInPQueue = NumInPQueue + 1

If NumInPQueue > PQueueSize Then ResizePQueue

PQueue(NumInPQueue) = value

HeapPushUp PQueue(), NumInPQueue

End Sub

Анализ пирамид

При первоначальном превращении списка в пирамиду, это осуществляется при помощи создания множества пирамид меньшего размера. Для каждого внутреннего узла дерева строится пирамида с корнем в этом узле. Если дерево содержит N элементов, то в дереве O(N) внутренних узлов, и в итоге приходится создать O(N) пирамид.

При создании каждой пирамиды может потребоваться продвигать элемент вниз по пирамиде, возможно до тех пор, пока он не достигнет концевого узла. Самые высокие из построенных пирамид будут иметь высоту порядка O(log(N)). Так как создается O(N) пирамид, и для построения самой высокой из них требуется O(log(n)) шагов, то все пирамиды можно построить за время порядка O(N * log(N)).

На самом деле времени потребуется еще меньше. Только некоторые пирамиды будут иметь высоту порядка O(log(N)). Большинство из них гораздо ниже. Только одна пирамида имеет высоту, равную log(N), и половина пирамид — высоту всего в 2 узла. Если суммировать все шаги, необходимые для создания всех пирамид, в действительности потребуется не больше O(N) шагов.

Чтобы увидеть, так ли это, допустим, что дерево содержит N узлов. Пусть H — высота дерева. Это полное двоичное дерево, следовательно, H=log(N).

Теперь предположим, что вы строите все большие и большие пирамиды. Для каждого узла, который находится на расстоянии H-I уровней от корня дерева, строится пирамида с высотой I. Всего таких узлов 2^H-I, и всего создается 2^H-I пирамид с высотой I.

Для построения этих пирамид может потребоваться передвигать элемент вниз до тех пор, пока он не достигнет концевого узла. Перемещение элемента вниз по пирамиде с высотой I требует до I шагов. Для пирамид с высотой I полное число шагов, которое потребуется для построения 2^H-I пирамид, равно I*2^H-I.

Сложив все шаги, затрачиваемые на построение пирамид разного размера, получаем 1*2^H-1+2*2^H-2+3*2^H-3+…+(H-1)* 2¹. Вынеся за скобки 2^H, получим 2^H*(1/2+2/2²+3/2³+…+(H-1)/2^H-1).

Можно показать, что (1/2+2/2²+3/2³+…+(H-1)/2^H-1) меньше 2. Тогда полное число шагов, которое нужно для построения всех пирамид, меньше, чем 2^H*2. Так как H — высота дерева, равная log(N), то полное число шагов меньше, чем 2^log(N)*2=N*2. Это означает, что для первоначального построения пирамиды требуется порядка O(N) шагов.

Для удаления элемента из приоритетной очереди, последний элемент перемещается на вершину дерева. Затем он продвигается вниз, пока не займет свое окончательное положение, и дерево снова не станет пирамидой. Так как дерево имеет высоту log(N), процесс может занять не более log(N) шагов. Это означает, что новый элемент к приоритетной очереди на основе пирамиды можно добавить за O(log(N)) шагов.

Другим способом работы с приоритетными очередями является использование упорядоченного списка. Вставка или удаление элемента из упорядоченного списка с миллионом элементов занимает примерно миллион шагов. Вставка или удаление элемента из сопоставимой по размерам приоритетной очереди, основанной на пирамиде, занимает всего 20 шагов.

Программа Priority на компакт‑диске с примерами использует пирамиду для работы с приоритетной очередью. Введите число и нажмите на кнопку Add (Добавить) для добавления нового элемента в очередь. Нажмите на кнопку Leave (Выбывать) для удаления элемента с самым высоким приоритетом из очереди.