Быстрый поиск

Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

Для того, чтобы снова превратить дерево без корня в пирамиду, возьмем последний элемент (самый правый элемент на нижнем уровне) и поместим его на вершину пирамиды. Затем при помощи процедуры 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)

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.

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

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

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

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

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

======253

Алгоритм пирамидальной сортировки

Алгоритм пирамидальной сортировки просто использует уже описанные алгоритмы для работы с пирамидами. Идея состоит в том, чтобы создать приоритетную очередь и последовательно удалять по одному элементу из очереди.

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

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

Public Sub Heapsort(List() As Long, ByVal min As Long, ByVal max As Long)

Dim i As Long

Dim tmp As Long

' Создать пирамиду (кроме корневого узла).

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

HeapPushDown List(), i, max

Next i

' Повторять:

' 1. Продвинуться вниз по пирамиде.

' 2. Выдать корень.

For i = max To min + 1 Step -1

' Продвинуться вниз по пирамиде.

HeapPushDown List(), min, i

' Выдать корень.

tmp = List(min)

List(min) = List(i)

List(i) = tmp

Next i

End Sub

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

=========254

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

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

Сортировка подсчетом

Сортировка подсчетом (countingsort) — специализированный алгоритм, который очень хорошо работает, если элементы данных — целые числа, значения которых находятся в относительно узком диапазоне. Этот алгоритм работает достаточно быстро, например, если значения находятся между 1 и 1000.

Если список удовлетворяет этим требованиям, сортировка подсчетом выполняется невероятно быстро. В одном из тестов на компьютере с процессором Pentium с тактовой частотой 90 МГц, быстрая сортировка 100.000 элементов со значениями между 1 и 1000 заняла 24,44 секунды. Для сортировки тех же элементов сортировке подсчетом потребовалось всего 0,88 секунд — в 27 раз меньше времени.

Выдающаяся скорость сортировки подсчетом достигается за счет того, что при этом не используются операции сравнения. Ранее в этой главе отмечалось, что время выполнения любого алгоритма сортировки, использующего операции сравнения, порядка O(N*log(N)). Без использования операций сравнения, алгоритм сортировки подсчетом позволяет упорядочивать элементы за время порядка O(N).

Сортировка подсчетом начинается с создания массива для подсчета числа элементов, имеющих определенное значение. Если значения находятся в диапазоне между min_value и max_value, алгоритм создает массив Counts с нижней границей min_value и верхней границей max_value. Если используется массив из предыдущего прохода, необходимо обнулить значения его элементов. Если существует M значений элементов, массив содержит M записей, и время выполнения этого шага порядка O(M).

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82