Является улучшенным вариантом алгоритма сортировки выбором. при сортировке выбором повторяется выбор наименьших элементов среди n,n-1,n-2…1 элементов. При каждом просмотре массива в прямом методе сортировки отыскивается 1 наименьший элемент. Пирамида – разновидность дерева. Сортировка дерева улучшает предложенный подход за счет того, что на каждом этапе просматриваемого массива используется дополнительная информация об упорядоченности некоторых пар элемнетов. Такая информация хранится в виде дерева. Например пусть имеется следующий массив:
5,3,7,27,9,11,14,2,8
В простейшем случае дерево для выбора наибольшего решения имеет вид:
Организация сортировки данных в виде бинарного дерева позволяет построить алгоритм сортировки с числом элементов операции не превышающих даже в худшем случае O(nlog2n) операций. Однако подобный способ хранения данных требует дополнительных затрат памяти для 2n-1 записей.
Избежать подобных затрат позволяет метод пирамид. В котором сортируемое дерево имеет специальную структуру, называемую пирамидой. Пирамида представляет собой помеченное бинарное дерево заданной высоты h удовлетворяющее 3 условиям.
• Любая конечная вершина (лист) имеет глубину h или h-1.
• Любая конечная вершина с глубиной h всегда находится левее любого листа с глубиной h-1.
• Начиная от корня к листьям метка любой вершины больше или равна метке любой следующей ща ней вершины.
Высота дерева – длина самого длинного пути от корня к листу.
Глубина вершины – длина пути от корня в эту веошину.
зе условие обеспечивает факт, что метка корня является наибольшей меткой дерева.
Структура дерева, представленная пирамидой позволяет описать ее виде массива сорт. элементов, включающих только n – вершин.
ai – одномерный массив, в котором потомки имеют номера 2i и 2i+1
Если для нек. вершин пирамиды аi получится, что 2i>n, то она – лист.
Используя представленную сортировку масс. в виде пирамиды, процесс сортировки можно представить следующим образом. Шаг 1
Переставить местами элементы с индексами а1 и аn. Шаг 2
Уменьшить количество сортируемых элементов на 1 Шаг 3
Преобразовать полученное дерево в пирамиду. Для этого сравнивают метку корня с метками ее потомков и перестав. ее с наибольшим значением.
Повторяют эту процедуру для следующих потомков до тех пор, пока ключ переставляемого элемента (бывшего корневого) не станет меньше ключей потомков.
Процедура повторяется для массива с меньшим на 1 количеством элементов. В послед. позиции размещается максимальный элемент массива.
Рассмотрим процедуру преобразования произвольного массива. В основе этой процедуры лежат действия подобные действиям, выполняемым на шаге 3рассмотренног алгоритма сортировки. Предполагаем, что исходный массив А = (а1…аn)
Чтобы его преобразовать в массив, определяющий пирамиду выполняются следующие действия.
2) Определяется индекс элемента k=[n/2]2)
3) i:=k
4) 3)Если f(ai)
ap – ключ последования, имеющий большее значение.
5) Проверяется условие p<[n/2]. Если вершина, в которую переставляется значение еще не лист, то процедура повторяется. (i:=p, пункт 3)
6) Если k=1 то конец алгоритма. Иначе k:=k-1; переход к пункту 2.
Опубликовал Kest
January 28 2010 13:59:15 ·
2 Комментариев ·
12858 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
AnTiKilLeR February 19 2011 09:15:50
Pasibki
Настя December 06 2011 16:37:41
а программный код для паскаль есть?
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
