For i3 = min To max
List(i3) = Scratch(i3)
Next i3
End Sub
========246
Сортировка слиянием тратит много времени на копирование временного массива на место первоначального. Программа FastSort использует функцию API MemCopy, чтобы немного ускорить эту операцию.
Даже с использованием функции MemCopy, сортировка слиянием немного медленнее, чем быстрая сортировка. В нашем тесте на компьютере с процессором Pentium с тактовой частотой 90 МГц, сортировка слиянием потребовала 2,95 сек для упорядочения 30.000 элементов со значениями в диапазоне от 1 до 10.000. Быстрая сортировка потребовала всего 2,44 сек.
Преимущество сортировки слиянием в том, что время ее выполнения остается одинаковым независимо от различных распределений и начального расположения данных. Быстрая же сортировка дает производительность порядка O(N2) и достигает глубокого уровня вложенности рекурсии, если список содержит много одинаковых значений. Если список большой, быстрая сортировка может переполнить стек и привести к аварийному завершению работы программы. Сортировка слиянием никогда не достигает слишком глубокого уровня вложенности рекурсии, т.к. всегда делит список на равные части. Для списка из N элементов, глубина вложенности рекурсии для сортировки слиянием составляет всего лишь log(N).
В другом тесте, в котором использовались 30.000 элементов со значениями от 1 до 100, сортировка слиянием потребовала столько же времени, сколько и для элементов со значениями от 1 до 10.000 — 2,95 секунд. Быстрая сортировка заняла 15,82 секунды. Если значения лежали между 1 и 50, сортировка слиянием потребовала 2,95 секунд, тогда как быстрая сортировка — 138,52 секунды.
Пирамидальная сортировка (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. Всего таких узлов 2H-I, и всего создается 2H-I пирамид с высотой I.