Информатика -продвинутый курс
Одним из алгоритмов, использующих структуру
Одним из алгоритмов, использующих структуру дерева, является сортировка с помощью пирамиды (Дж.Вилльямс). Пирамида определяется как последовательность ключей hL...hR, такая, что *
hi<=h2i и hi<=h2i+l, для i=L,...,R/2.
Другими словами пирамиду можно определить как двоичное дерево заданной высоты h, обладающее тремя свойствами:
• каждая конечная вершина имеет высоту h или h-1;
• каждая конечная вершина высоты h находится слева от любой конечной вершины высоты h-1;
• значение любой вершины больше значения любой следующей за ней вершины. Рассмотрим пример пирамиды, составленной по массиву
27 9 14 8 5 11 7 2 3.
У пирамиды п вершин, их значения можно разместить в массиве а, но таким образом, что следующие за вершиной из a[i] помещаются в a[2i] и a[2i+l]. Заметим, что а[6]=11,а[7]=7, а они следуют за элементом а[3]=14 (рис.3.14).
Рис. 3.14. Пирамида
Очевидно, что если 2i > n , тогда за вершиной a[i] не следуют другие вершины, и она является конечной вершиной пирамиды.
Процесс построения пирамиды для заданного массива можно разбить на четыре этапа:
1) меняя местами а[1] и а[п], получаем 3 9 14 8 5 11 7 2 27;
2) уменьшаем n на 1, т. е. n=n-l, что эквивалентно удалению вершины 27 из дерева;
3) преобразуем дерево в другую пирамиду перестановкой нового корня с большей из двух новых, непосредственно следующих за ним вершин, до тек пор, пока он не станет больше, чем обе вершины, непосредственно за ним следующие;
4) повторяем шаги 1, 2, 3 до тех пор, пока не получим n= I.
Для алгоритма сортировки нужна процедура преобразования произвольного массива в пирамиду (шаг 3). В ней необходимо предусмотреть последовательный просмотр массива справа налево с проверкой одновременно двух условий: больше ли a[i], чем a[2i] и a[2i+l].
Полный текст программы приведен ниже.
Программа 48
program sortirovka_5;
(*улучшенная сортировка выбором - сортировка с помощью дерева*) const N=8;
type item= integer;
var a : array(l..n] of item; k, L, R: integer; x: item;
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий