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

4.3. Т
УРНИРНАЯ СОРТИРОВКА
 
Простейший вид сортировки на деревьях уже упоминался – это по-
строение упорядоченного дерева и последовательное взятие значений узлов 
при обходе «слева-направо». Однако существуют и более эффективные сор-
тировки, использующие древовидную структуру.
Идея турнирной сортировки фактически заимствована у организаторов 
спортивных чемпионатов. Чемпионат проводится в несколько туров, причем 
в следующий тур выходят победители парных встреч из предыдущего тура.
22 / 23

---

92 
Турнирная сортировка является одним из вариантов пирамидальной 
сортировки. Алгоритм такой сортировки состоит из двух шагов. Сначала на 
основе сортируемой последовательности строится дерево, называемое пира-
мидой, и с этим связано название алгоритма (HeapSort от англ. heap – куча, 
пирамида).
На рисунке 4.6 показана форма проекта «Турнирная сортировка» с изо-
браженным на ней пирамидальным деревом. На этой форме размещены сле-
дующие элементы управления: 
− текстовое поле, предназначенный для ввода данных; 
− кнопка «Создать», при нажатии на которую строится исходное 
турнирное дерево, имеющее вид пирамиды, и отображается на 
форме; 
− кнопка «Сортировать», при нажатии на которую выполняется вы-
бор значения с вершины дерева и перестройка дерева; 
− элемент PictureBox для построения изображения дерева. 
Рис. 4.6. Исходное дерево турнирной сортировки 
В отличие от обычного дерева пирамида формируется от основания к 
вершине. Кроме того, узлы, расположенные на одном уровне, связываются в 
линейный список. По этой причине каждый узел дерева, дополнительно к 
ссылкам на прямых потомков, содержит указатель на брата. Структура клас-
са, описывающего узел дерева-пирамиды, представлена в листинге 4.14.