Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Пирамида. Пирамидальная сортировка является первым из рассматриваемых методов, быстродействие которых оценивается как O(n log n). В качестве некоторой
|
|
Пирамидальная сортировка является первым из рассматриваемых методов, быстродействие которых оценивается как O(n log n).
В качестве некоторой прелюдии к основному методу, рассмотрим перевернутую сортировку выбором. Во время прохода, вместо вставки наименьшего элемента в левый конец массива, будем выбирать наибольший элемент, а готовую последовательность строить в правом конце.
Пример действий для массива a[0]... a[7]:
44 55 12 42 94 18 06 67 исходный массив
44 55 12 42 67 18 06 |94 94 < -> 67
44 55 12 42 06 18 |67 94 67 < -> 06
44 18 12 42 06 |55 67 94 55 < -> 18
06 18 12 42 |44 55 67 94 44 < -> 06
06 18 12 |42 44 55 67 94 42 < -> 42
06 12 |18 42 44 55 67 94 18 < -> 12
06 |12 18 42 44 55 67 94 12 < -> 12
Вертикальной чертой отмечена левая граница уже отсортированной(правой) части массива.
Рассмотрим оценку количества операций подробнее.
Всего выполняется n шагов, каждый из которых состоит в выборе наибольшего элемента из последовательности a[0]..a[i] и последующем обмене. Выбор происходит последовательным перебором элементов последовательности, поэтому необходимое на него время: O(n). Итак, n шагов по O(n) каждый - это O(n2).
Произведем усовершенствование: построим структуру данных, позволяющую выбирать максимальный элемент последовательности не за O(n), а за O(logn) времени. Тогда общее быстродействие сортировки будет n*O(logn) = O(n log n).
Эта структура также должна позволять быстро вставлять новые элементы (чтобы быстро ее построить из исходного массива) и удалять максимальный элемент (он будет помещаться в уже отсортированную часть массива - его правый конец).
Итак, назовем пирамидой(Heap) бинарное дерево высоты k, в котором
• все узлы имеют глубину k или k-1 - дерево сбалансированное.
• при этом уровень k-1 полностью заполнен, а уровень k заполнен слева направо, т.е форма пирамиды имеет приблизительно такой вид:
• выполняется " свойство пирамиды": каждый элемент меньше, либо равен родителю.
Как хранить пирамиду? Наименее хлопотно - поместить ее в массив.
Таким образом, для массива, хранящего в себе пирамиду, выполняется следующее характеристическое свойство: a[i] > = a[2i+1] и a[i] > = a[2i+2]. Плюсы такого хранения пирамиды очевидны: • никаких дополнительных переменных, нужно лишь понимать схему. • узлы хранятся от вершины и далее вниз, уровень за уровнем. • узлы одного уровня хранятся в массиве слева направо. Запишем в виде массива пирамиду, изображенную выше.. Слева-направо, сверху-вниз: 94 67 18 44 55 12 06 42. На рисунке место элемента пирамиды в массиве обозначено цифрой справа-вверху от него. Восстановить пирамиду из массива как геометрический объект легко - достаточно вспомнить схему хранения и нарисовать, начиная от корня. |
