Пирамидальная сортировка

Пирамидальная сортировка (heapsort) использует специальную структуру, называемую пирамидой (heap), для организации элементов в списке. Пирамиды интересны сами по себе и полезны при реализации приоритетных очередей.

В начале этой главы описываются пирамиды, и объясняется, как вы можете реализовать пирамиды на языке Visual Basic. Затем показано, как использовать пирамиду для построения эффективной приоритетной очереди. Располагая средствами для управления пирамидами и приоритетными очередями, легко реализовать алгоритм пирамидальной сортировки.

Пирамиды

Пирамида (heap) — это полное двоичное дерево, в котором каждый узел не меньше, чем оба его потомка. Это ничего не говорит о взаимосвязи между потомками. Они должны быть меньше родителя, но любой из них может быть больше, чем другой. На рис. 9.6 показана небольшая пирамида.

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

 

=========247

 

Рис. 9.6. Пирамида

 

Поскольку пирамида является полным двоичным деревом, вы можете использовать методы, изложенные в 6 главе, для сохранения пирамиды в массиве. Поместите корневой узел в 1 позицию массива. Потомки узла I размещаются в позициях 2 * I и 2 * I + 1. Рис. 9.7 показывает пирамиду с рис. 9.6, записанную в виде массива.

Чтобы понять, как устроена пирамида, заметим, что пирамида создана из пирамид меньшего размера. Поддерево, начинающееся с любого узла пирамиды, также является пирамидой. Например, в пирамиде, показанной на рис. 9.8, поддерево с корнем в узле 13 также является пирамидой.

Используя этот факт, можно построить пирамиду снизу вверх. Вначале, разместим элементы в виде дерева, как показано на рис. 9.9. Затем организуем пирамиды из небольших поддеревьев внизу дерева. Поскольку в них всего по три узла, сделать это достаточно просто. Сравним вершину с каждым из потомков. Если один из потомков больше, он меняется местами с родителем. Если оба потомка больше, больший потомок меняется местами с родителем. Этот шаг повторяется до тех пор, пока все поддеревья, имеющие по 3 узла, не будут преобразованы в пирамиды, как показано на рис. 9.10.

Теперь объединим маленькие пирамиды для создания более крупных пирамид. Соединим на рис. 9.10 маленькие пирамиды с вершинами 15 и 5 и элемент, создав пирамиду большего размера. Сравним новую вершину 7 с каждым из потомков. Если один из потомков больше, поменяем его местами с вершиной. В нашем случае 15 больше, чем 7 и 4, поэтому узел 15 меняется местами с узлом 7.

Поскольку правое поддерево, начинающееся с узла 4, не изменялось, это поддерево по‑прежнему является пирамидой. Левое же поддерево изменилось. Чтобы определить, является ли оно все еще пирамидой, сравним его новую вершину 7 с потомками 13 и 12. Поскольку 13 больше, чем 7 и 12, необходимо поменять местами узлы 7 и 13.

 

@Рис. 9.7. Представление пирамиды в виде массива

 

========248

 

@Рис. 9.8. Пирамида образуется из меньших пирамид

 

@Рис. 9.9. Неупорядоченный список в полном дереве

 

@Рис. 9.10. Поддеревья второго уровня являются пирамидами

 

=========249

 

@Рис. 9.11. Объединение пирамид в пирамиду большего размера

 

Если поддерево выше, можно продолжить перемещение узла 7 вниз по поддереву. В конце концов, либо будет достигнута точка, в которой узел 7 больше обоих своих потомков, либо алгоритм достигнет основания дерева. На рис. 9.11 показано дерево после преобразования этого поддерева в пирамиду.

Продолжим объединение пирамид, образуя пирамиды большего размера до тех пор, пока все элементы не образуют одну большую пирамиду, такую как на рис. 9.6.

Следующий код перемещает элемент из положения List(min) вниз по пирамиде. Если поддеревья ниже List(min) являются пирамидами, то процедура сливает пирамиды, образуя пирамиду большего размера.

 

Private Sub HeapPushDown(List() s Long, ByVal min As Long, _

ByVal max As Long)

Dim tmp As Long

Dim j As Long

 

tmp = List(min)

Do

   j = 2 * min

   If j <= max Then

      ‘ Разместить в j указатель на большего потомка.

   If j < max Then

   If List(j + 1) > List(j) Then _

      j = j + 1

   End If

 

   If List(j) > tmp Then

      ‘ Потомок больше. Поменять его местами с родителем.

      List(min) = List(j)

      ‘ Перемещение этого потомка вниз.

              min = j

          Else

              ‘ Родитель больше. Процедура закончена.

          Exit Do

      End If

   Else

      Exit Do

   End If

Loop

List(min) = tmp

End Sub

 

Полный алгоритм, использующий процедуру HeapPushDown для создания пирамиды из дерева элементов, необычайно прост:

 

Private Sub BuildHeap()

Dim i As Integer

 

For i = (max + min) \ 2 To min Step -1

   HeapPushDown list(), i, max

Next i

End Sub

 

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

Приоритетной очередью (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

 

 

========252

 

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

При первоначальном превращении списка в пирамиду, это осуществляется при помощи создания множества пирамид меньшего размера. Для каждого внутреннего узла дерева строится пирамида с корнем в этом узле. Если дерево содержит 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 шагов.

 

======253