Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
Имитационное мо... 61265
Реклама
Сейчас на сайте
Гостей: 8
На сайте нет зарегистрированных пользователей

Пользователей: 13,124
новичок: alejka
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Медиа плейер на Delphi + Пояснительная записка
Моделирование работы обрабатывающего участка цеха в GPSS
Моделирование процесса передачи данных по магистрали с основным и резерв...

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Пирамидальная сортировка
Является улучшенным вариантом алгоритма сортировки выбором. при сортировке выбором повторяется выбор наименьших элементов среди 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 Январь 28 2010 16:59:15 · 2 Комментариев · 10527 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
AnTiKilLeR Февраль 19 2011 12:15:50
Pasibkismiley
Настя Декабрь 06 2011 20:37:41
а программный код для паскаль есть?
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
DCAVI
AntiRus
База для Allsubmi...
Книга по Delphi (...
Шкрыль А. - Разра...
INSTANT BOOSTER v...
Меню проводника в...
Delphi 2005. Разр...
Задача о 8ми ладьях
IPAddresseEdit
Базы данных в Инт...
Scrrlcaptoin
NotePad Pro [Исхо...
Illusion
Delphi 2005 Учимс...
Swing. Эффектные...
AUTOWEB
Ильдар Хабибуллин...
Java Server Pages...
Библия хакера 2. ...

Топ загрузок
Приложение Клие... 100546
Delphi 7 Enterp... 92604
Converter AMR<-... 20109
GPSS World Stud... 15750
Borland C++Buil... 13285
Borland Delphi ... 9292
Turbo Pascal fo... 7124
Калькулятор [Ис... 5263
Visual Studio 2... 5042
FreeSMS v1.3.1 3564
Случайные статьи
История возникнове...
Работа с базами да...
Стандарт IEEE 802....
Обработка исключит...
Новая форма Ливерпуля
Передача оцифрован...
Защита с использов...
Директивы компилят...
Проблемы с USB под...
Надстройки над OpenGL
Практичность
Общение в ICQ
Форматирование объ...
параметры политики...
Контекстная реклама
Алгоритмы и способ...
Стандарт POSIX
Работа с OLE-объек...
Итератор end
Уровни разработки
Программирование в...
Здравый смысл
Переключитесь в ре...
службы, связанную ...
Архитектура ОП дол...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?