Пирамидальная сортировка. Выбор из дерева

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

(олимпийская система, попарно)

40 4 5 20 7 6 7 14 40

20

40 20 7 14 14

40 14 7

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

В 1968 году был предложен алгоритм, в котором отсутствовал элемент – ∞, а элементы располагались внутри самой последовательности. Такой алгоритм получил название пирамидально сортировки. Пирамидой называется последовательность Ключей к1 к2 кn, в которой выполняется K_{jdiv 2} >= K_j;,1 <= j div 2 <= N, причем ключи занумерованы в следующем порядке

1 K1

K2 2 3 K3

2j 4 2j+1 5 2j 6 7 2j+1

8 9 10 11 12 13 14 15

, то у узла K[j] сыновья будут с индексами 2j и 2j+1. Таким образом, в соответствии с формулой 1 пирамиды любой отец в пирамиде не превышает наименьшего из сыновей из своих сыновей, тогда корнем будет наименьший во всей последовательности. Алгоритм пирамидальной сортировки состоит из двух этапов:

1. Располагает произвольную последовательность в виде пирамиды

2. Последовательно исключаем вершину пирамиды и восстанавливаем условие j1 внутри последовательности.

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

15 7 5 14 40 6 7 20 -2

II -2 4 5 14 7 6 7 15

40 4 5 20 7 6 7 14

1 2 3 4 5 6 7 8

4 5

10 -2 6 7

14 15 7

В отличие от Хоару, трудоемкость (быстродействие) пирамидальной сортировки не зависит от частного случая взаимного расположения элементов: даже уже упорядоченную последовательность, первый этап переразместит в виде пирамиды по трудоемкости максимально возможного количества обменов (протаскивания) элементов, которая равна высоте дерева, высота сбалансированного дерева равна двоичному логарифму.

Z log ₂(n-i)

I N div 2

Log2(N(N-1))

0(f параметр) = const n log₂N