Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 4.18. Метод перестройки пирамиды 
public Node Competition(ref Node ph) 
// 
Реорганизация поддерева 
{ 
if (ph.left!=null)
{ 
if (ph.left.data==ph.data) 
6 / 23

---

99 
ph.left = Competition(ref ph.left); 
else 
ph.right = Competition(ref ph.right); 
} 
else 
if (ph.right!=null) 
ph.right = Competition(ref ph.right); 
if ((ph.left==null) && (ph.right==null)) 
ph = null; 
else // 
состязание данных сыновей 
if ((ph.left==null) || ((ph.right != null)
&& (ph.left.data>ph.right.data))) 
ph.data = ph.right.data; 
else 
ph.data =ph.left.data; 
return ph; 
} 
На рисунке 4.7 демонстрируется результат реорганизации пирамиды 
после выбора двух узлов. 
Рис. 4.7. Выборка значений из турнирной пирамиды 
7 / 23

---

100 
Для оценки временной эффективность данного алгоритма сортировки 
следует принять во внимание, что для построения дерева требуется выпол-
нить N–1 сравнений, а для формирования упорядоченной выборки узлов – 
N×log
2
(N) сравнений. Таким образом, скорость роста алгоритма, опреде-
ляющаяся наибольшей из этих величин, составит O(N×log
2
N). Однако слож-
ность выполнения операций над динамическими структурами данных не по-
зволяет получить существенного преимущества во времени выполнения пе-
ред алгоритмами сортировки для статических структур данных. Недостатком 
алгоритма является также избыточное использование, обусловленное крат-
ным присутствием в дереве-пирамиде узлов с одинаковыми значениями клю-
ча. Фактически это приводит к удвоению числа узлов по сравнению с разме-
ром сортируемой последовательности.