Лекция № 5: Пирамидальная сортировка

Затвитить
эту лекцию
Опубликовано 18‑го октября 2008 г.
Обновлено 31‑го октября 2011 г.

Статья написано давно, и на данный момент требует серьёзной переработки.

Оставим в стороне религиозные споры о преимуществах и недостатках алгоритма Quick Sort (который хорош в среднем, но требует усложнения для удовлетворительной работы в худшем случае), и будем рассматривать пирамидальную сортировку, как самый быстрый алгоритм из доступных (смотрите Лекцию № 3) для сортировки небольших объёмов данных, умещающихся в кэш процессора.

Алгоритм пирамидальной сортировки по-английски называется «Heap Sort». «Heap» переводится, как «куча». В связи с этим пирамидальную сортировку ещё называют «сортировка кучей»

Пирамидальная сортировка была предложена Дж. Уильямсом в 1964 году. Это алгоритм сортировки массива произвольных элементов; требуемый им дополнительный объём памяти не зависит от количества исходных данных. Время работы алгоритма — $O\left(n\cdot\ln n\right)$ в среднем, а также в лучшем и худшем случаях.

Для тех, кто попадает на эту страницу по поисковым запросам типа «пирамидальная сортировка, параллельный алгоритм»: к сожалению, попытки распараллелить этот алгоритм приводят к его существенному усложнению, и снижению эффективности вычислений.

Так как пирамидальную сортировку целесообразно применять для небольших объёмов сортируемых данных (когда они умещаются в кэш процессора), накладные расходы параллельной программы будут слишком велики. Пример параллельного алгоритма можете найти в этой статье

В данной лекции будет рассмотрен базовый вариант этого алгоритма, не отличающийся большой скоростью (в частности, работающий несущественно быстрее сортировки слиянием). Более быстрые (и сложные) варианты алгоритма вы можете найти в Интернете с помощью поисковых запросов типа «Heap sort modification».

Везде далее будем считать, что первый элемент массива имеет индекс 0.

Идея алгоритма

Для того, чтобы прояснить всё дальнейшее изложение, в двух словах опишу идею алгоритма.

Пирамида — двоичное дерево, в котором значение каждого элемента больше либо равно значений дочерних элементов.
Заполнив дерево элементами в произвольном порядке, можно легко его отсортировать (легче, чем исходный список элементов), превратив в пирамиду.
Самый большой элемент пирамиды находится в её вершине.
Отделяем вершинный элемент, и записываем его в конец результирующего массива.
На место вершинного элемента записываем элемент из самого нижнего уровня дерева.
Восстанавливаем (пересортировываем) пирамиду.
Самый большой элемент из оставшихся снова в вершине. Снова отделяем его и записываем его в качестве предпоследнего элемента результата, и так далее...
Весь фокус алгоритма в том, что пирамида без дополнительных затрат хранится прямо в исходном массиве. По мере того, как размер пирамиды уменьшается, она занимает всё меньшую часть массива, а результат сортировки записывается начиная с конца массива на освободившиеся от пирамиды места.

Ещё одно объяснение идеи алгоритма можете посмотреть в этом комментарии.

Двоичное дерево

Двоичное дерево — структура данных, в которой каждый элемент имеет левого и/или правого потомка, либо вообще не имеет потомков. В последнем случае элемент называется листовым.

Если элемент A имеет потомка B, то элемент A называется родителем элемента B. В двоичном дереве существует единственный элемент, который не имеет родителей; такой элемент называется корневым.

Пример двоичного дерева показан на рисунке 1:

Рисунок 1. Пример двоичного дерева

Почти заполненным двоичным деревом называется двоичное дерево, обладающее тремя свойствами:

все листовые элементы находятся в нижнем уровне, либо в нижних двух уровнях;
все листья в уровне заполняют уровень слева;
все уровни (кроме, быть может, последнего уровня) полностью заполнены элементами.

Дерево на рисунке 1 не является почти заполненным, так как уровень 4 не заполнен слева (элемент g «мешает»), и третий уровень (не являющийся последним), не заполнен полностью.

Почти заполненное двоичное дерево можно хранить в массиве без дополнительных затрат. Для этого достаточно перенумеровать элементы каждого уровня слева-направо:

Нумерация элементов почти заполненного дерева

Рисунок 2. Пример нумерации элементов почти заполненного дерева

Нетрудно видеть, что при такой нумерации потомки узла с номером i имеют номера 2i+1 и 2i+2 (если они есть). Родитель узла имеет номер $\left\lfloor\left(i-1\right)/2\right\rfloor$ :

Нахождение потомков и родителя в массиве

Рисунок 3. Пример нахождения потомков и родителя в массиве

Пирамида

Возрастающей пирамидой называется почти заполненное дерево, в котором значение каждого элемента больше либо равно значений всех его потомков. Аналогично, в убывающей пирамиде значение каждого элемента меньше либо равно значений потомков.

Пример возрастающей пирамиды показан на рисунке:

Рисунок 4. Пример возрастающей пирамиды

Очевидно, самое большое значение в возрастающей пирамиде имеет корневой элемент. Однако, из свойств пирамиды не следует, что значения элементов уменьшаются с увеличением уровня. В частности, на рисунке 4 элемент со значением 3 на четвёртом уровне больше значений всех элементов, кроме одного, находящихся на третьем уровне.

Важной операцией является отделение последнего (в смысле нумерации) элемента от пирамиды. Нетрудно доказать, что в этом случае двоичное дерево остаётся почти заполненным, и все свойства пирамиды сохраняются.

Просеивание вверх

Рассмотрим теперь задачу присоединения элемента с произвольным значением к возрастающей пирамиде. Если просто добавить элемент в конец массива, то свойство пирамиды (значение любого элемента $\leqslant$ значения его родителя) может быть нарушено. Для восстановления свойства пирамиды к добавленному элементу применяется процедура просеивания вверх, которая описывается следующим алгоритмом:

если элемент корневой, или его значение $\leqslant$ значения родителя, то конец;
меняем местами значения элемента и его родителя;
переходим к родителю, и выполняем для него этот же алгоритм, начиная с пункта 1.

Пример просеивания вверх добавленного элемента показан на рисунке:

Рисунок 5. Процесс просеивания вверх добавленного элемента

После выполнения данной процедуры свойство пирамиды будет восстановлено, так как:

Если вновь добавленный элемент больше родителя, то он больше и второго потомка родителя (если второй потомок есть), так как до добавления нового элемента было выполнено свойство пирамиды, и родитель был не меньше своего потомка (на рисунке 5 слева: семёрка больше своего родителя — четвёрки, — поэтому она больше и второго потомка четвёрки — тройки). После обмена значений элемента и родителя свойство пирамиды будет восстановлено в поддереве, корнем которого является родитель с новым значением (например, после обмена местами семёрки и четвёрки, семёрка тройка и четвёрка будут образовывать правильное поддерево).
В результате обмена свойство пирамиды может быть нарушено в отношении родителя и родителя родителя (так как значение родителя стало больше). Процедура вызывается для родительского узла, чтобы восстановить это свойство.

Исходный код процедуры просеивания вверх я не привожу, так как он нам не понадобится.

Просеивание вниз

Что делать, если нам нужно заменить корневой элемент на какой-либо другой? В этом случае пирамидальную структуру двоичного дерева можно восстановить с помощью процедуры просеивания вниз:

если элемент листовой, или его значение $\geqslant$ значений потомков, то конец;
иначе меняем местами значения элемента и его потомка, имеющего максимальное значение;
переходим к изменившемуся потомку, и выполняем для него этот же алгоритм, начиная с пункта 1.

Пример просеивания вниз показан на рисунке:

Рисунок 6. Процесс просеивания вниз изменённого корневого элемента.
Красным цветом показан текущий элемент

Исходный код процедуры просеивания вниз приведён в листинге 1:

template<class T> void SiftDown(T* const heap, int i, int const n)

{   //Просеивает элемент номер i вниз в пирамиде heap.

    //n -- размер пирамиды

    //Идея в том, что вычисляется максимальный элемент из трёх:

    //  1) текущий элемент

    //  2) левый потомок

    //  3) правый потомок

    //Если индекс текущего элемента не равен индексу максималь-

    //  ного, то меняю их местами, и перехожу к максимальному

    //Индекс максимального элемента в текущей тройке элементов:

    int nMax( i );

    //Значение текущего элемента (не меняется):

    T const value( heap[i] );

    while ( true )

    { //Рассматривается элемент i и его потомки i*2+1 и i*2+2

      //В начале каждой итерации nMax == i и value == heap[i]

        int childN( i*2+1 ); //Индекс левого потомка

        //Если есть левый потомок и он больше текущего элемента,

        if ( ( childN < n ) && ( heap[childN] > value      ) )

            nMax = childN; //  то он считается максимальным

        ++childN; //Индекс правого потомка

        //Если есть правый потомок и он больше максимального,

        if ( ( childN < n ) && ( heap[childN] > heap[nMax] ) )

            nMax = childN; //  то он считается максимальным

        //Если текущий элемент является максимальным из трёх

        //  (т.е. если он больше своих детей), то конец:

        if ( nMax == i ) break;

        //Меняю местами текущий элемент с максимальным:

        heap[i] = heap[nMax]; heap[nMax] = value; 

        //  при этом значение value будет в ячейке nMax,

        //  поэтому в начале следующей итерации значение value

        //  правильно, т.к. мы переходим именно к этой ячейке

        //Переходим к изменившемуся потомку

        i = nMax;

    };

}

Листинг 1. Функция просеивания вниз в возрастающей пирамиде

Внутри цикла while имеются 5 условных операторов (операторы && по сути тоже являются условными). Эти операторы являются медленными. Их количество можно сократить, но тогда код будет сложно читаем.

Корректность процедуры просеивания вниз предлагаю вам доказать самостоятельно.

Построение пирамиды

Допустим, у нас есть произвольный набор из n элементов, и мы хотим построить из него пирамиду. Самый простой способ этого добиться — начать с пустой пирамиды, и добавлять в неё элементы один за другим, каждый раз вызывая процедуру просеивания вверх для нового элемента. Назовём этот метод построения пирамиды «методом просеивания вверх». Пример работы алгоритма показан на рисунке:

Рисунок 7. Анимация простого алгоритма построения пирамиды

Рассчитаем быстродействие этого метода в самом плохом случае. Пусть массив уже отсортирован по возрастанию, и каждый добавляемый элемент вынужден просеиваться вверх до самого корня. Тогда при добавлении элемента номер i нам потребуется $O\left(\ln\left(i+1\right)\right)$ операций. Мы делаем эту процедуру для всех i от 0 до n-1 :

$T_1\left(n\right)=\sum_{i=0}^{n-1}{O\left(\ln\left(i+1\right)\right)}=O\left(\sum_{i=2}^n{\ln i}\right).$

(1)

Оценим сумму в выражении (1) с помощью определённого интеграла:

$\int\limits_2^{n+1}{\ln\left(x-1\right)dx} < \sum_{i=2}^n{\ln i} < \int\limits_2^{n+1}{\ln x dx}.$

(2)

Вычисляя интегралы, получаем:

$n\ln n -n+1 < \sum_{i=2}^n{\ln i} < \left(n+1\right)\cdot\ln \left(n+1\right) -n-2\ln2+1.$

(3)

Это означает, что:

$T_1\left(n\right)=O\left(n\cdot\ln n\right).$

(4)

На самом деле пирамиду можно построить быстрее. Для этого заполним дерево элементами в произвольном порядке (например так, как они идут в массиве изначально), и будем его исправлять.

Заметим, что если у нас есть две пирамиды, то, если их соединить общим корнем, а затем просеять корень вниз, то мы получим новую большую пирамиду. Деревья, состоящие из одного элемента, заведомо являются пирамидами, поэтому начнём с набора листовых элементов, и будем соединять имеющиеся пирамиды попарно до тех пор, пока не получим одну большую пирамиду. Первый добавляемый корень имеет индекс $n_0=\left\lfloor n/2 \right\rfloor-1$ . Алгоритм следующий: «для всех i от n_0 до 0 вызываем процедуру просеивания элемента вниз». Назовём этот метод построения пирамиды «методом просеивания вниз».

Вычислим быстродействие этого алгоритма в худшем случае. Пусть массив отсортирован по возрастанию, и каждый добавляемый корень должен быть просеян в самый низ строящейся пирамиды. Высота дерева примерно равна $\log_2n$ , глубина залегания элемента номер i в дереве равна $\log_2i$ , поэтому он будет просеиваться вниз $\log_2n-\log_2i$ шагов. Тогда общее время построения пирамиды будет равно:

$T_2\left(n\right)=O\left(\sum_{i=n/2}^1{\left(\ln n-\ln i\right)}\right).$

(5)

Оценивая сумму интегралами аналогично (2), (3), получим:

$T_2\left(n\right)=O\left(n\right).$

(6)

Отсюда следует, что для большого числа элементов $T_2\left(n\right)$ будет меньше, чем $T_1\left(n\right)$ . Более точные оценки дадут, что $T_2\left(n\right) < T_1\left(n\right)$ для любых n, так как, во первых, при построении пирамиды методом просеивания вверх процедура просеивания вызывается в 2 раза больше раз, чем при построении методом просеивания вниз, и, во вторых, элементы с номерами от n/2 до n просеиваются вверх на большее расстояние, чем расстояние, на которое просеиваются вниз элементы от n/2 до 0. Поэтому в дальнейшем будем строить пирамиду методом просеивания вниз.

Сортировка

Имея построенную пирамиду, несложно реализовать сортировку. Так как корневой элемент пирамиды имеет самое большое значение, мы можем отделить его и поместить в отсортированный список. Вместо отсутствующего корневого элемента можно поставить последний (в смысле нумерации) элемент дерева и, просеяв его вниз, снова получить пирамиду.

В новой уменьшенной пирамиде корень имеет самое большое значение среди оставшихся элементов. Его снова можно отделить и поместить в отсортированный список перед имеющимися там элементами, и так далее.

Вдумчивый читатель может заметить неэффективность, связанную с тем, что на место отсутствующего корневого элемента ставится элемент из последнего уровня пирамиды. Элементы последнего уровня имеют, в некотором смысле, малые значения, поэтому, ставя элемент из последнего уровня на место корневого элемента мы, скорее всего, будем вынуждены просеивать его в самый низ пирамиды.

На самом деле предложенный способ — самый простой и быстрый (в том смысле, что ничего лучше пока не придумано) из всех возможных способов восстановить пирамиду с отсутствующим корневым элементом

Для хранения отсортированного списка будем использовать элементы исходного массива, освобождающиеся в результате уменьшения размера пирамиды. Алгоритм получается следующий:

поменять местами значения первого и последнего элементов пирамиды;
отделить последний элемент от дерева, уменьшив размер дерева на единицу (элемент остаётся в массиве);
восстановить пирамиду, просеяв вниз её новый корневой элемент;
перейти к пункту 1;

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

Реализация пирамидальной сортировки на языке программирования C++ приведена в листинге 2 (используется процедура просеивания вниз из листинга 1):

template<class T> void HeapSort(T* const heap, int n)

{   //Пирамидальная сортировка массива heap.

    //  n -- размер массива

    //Этап 1: построение пирамиды из массива

    for(int i(n/2-1); i>=0; --i) SiftDown(heap, i, n);

    //Этап 2: сортировка с помощью пирамиды.

    //  Здесь под «n» понимается размер пирамиды

    while( n > 1 ) //Пока в пирамиде больше одного элемента

    {

        --n; //Отделяю последний элемент

        //Меняю местами корневой элемент и отделённый:

        T const firstElem( heap[0] );

        heap[0] = heap[n];

        heap[n] = firstElem;

        //Просеиваю новый корневой элемент:

        SiftDown(heap, 0, n);

    }

}

Листинг 2. Пирамидальная сортировка

Теоретическое время работы этого алгоритма нетрудно оценить, если заметить, что пирамидальная сортировка (без учёта начального построения пирамиды) полностью аналогична построению пирамиды методом просеивания вверх, только производится «в обратном порядке»: пирамида не строится, а «разбирается» элемент-за-элементом, и элементы просеиваются не вверх, а вниз. Поэтому время работы алгоритма пирамидальной сортировки T_3 без учёта времени построения пирамиды будет определяться аналогично формуле (4):

$T_3\left(n\right)=O\left(n\cdot\ln n\right).$

(7)

Тогда общее время сортировки (с учётом построения пирамиды) будет равно:

$T\left(n\right) = T_2\left(n\right)+T_3\left(n\right) = O\left(n\right)+O\left(n\cdot\ln n\right) = O\left(n\cdot\ln n\right).$

(8)

Измерение быстродействия алгоритма

Мы уже выяснили с помощью теоретических оценок, что время работы алгоритма пирамидальной сортировки равно: $T\left(n\right) = O\left(n\cdot\ln\left(n\right)\right)$ . Полезно также знать, чему равен неизвестный коэффициент перед $n\cdot\ln\left(n\right)$ при выполнении сортировки на реальной вычислительной системе.

На рисунке 8 показан график величины $k\left(n\right)$ , определяемой выражением:

$k\left(n\right)=10^9\cdot\frac{T\left(n\right)}{n\cdot\ln\left(n+1\right)},$

(9)

где n — количество сортируемых псевдослучайных четырёхбайтовых целых чисел, $T\left(n\right)$ — время сортировки на моём компьютере.

Мой процессор: Intel Mobile Core 2 Duo T7500 (во время тестов программа работала на одном ядре). Тактовая частота: 2.2 ГГц. Кэш L2: 4 МБ, 16-ассоциативный, 64 байта на строку.

Для каждого числа элементов было выполнено восемь тестов, и из их результатов был взят минимум, чтобы исключить случайное влияние других вычислительных процессов на ход эксперимента.

Отношение времени пирамидальной сортировки к n∙ln(n)

Рисунок 8. Отношение времени пирамидальной сортировки к $n\cdot\ln\left(n+1\right)$

На графике проявляются две важные особенности алгоритма:

Алгоритм относительно медленно работает, когда число сортируемых элементов меньше сотни. Для малого числа элементов желательно использовать сортировочные сети; об этом я расскажу в одной из следующих лекций.
Когда количество сортируемых данных начинает превышать размер кэша процессора (в нашем случае миллион чисел по 4 байта), скорость сортировки падает. Это вызвано тем, что алгоритм обращается к элементам массива довольно случайным образом (с точки зрения алгоритма работы кэша). По мере того, как всё меньшая часть данных уменьшается в кэше, скорость работы алгоритма всё более определяется скоростью работы оперативной памяти, а не скоростью работы кэша. В одной из следующих лекций мы устраним этот недостаток.

Затвитить
эту лекцию

45 отзывов на запись «Лекция № 5: Пирамидальная сортировка»

Отзыв № 1
Автор: Роман Куличков. Дата: 7-го июня 2009 г. Время: 11:58.

Спасибо Вам огромное за лекцию. Очень мне помогла.

Отзыв № 2
Автор: Йорданка. Дата: 31-го июля 2009 г. Время: 18:39.

Теперь все понятно! Спосибо!

Отзыв № 3
Автор: Андрей. Дата: 4-го октября 2009 г. Время: 18:33.

Спасибо

Отзыв № 4
Автор: Лёха. Дата: 13-го октября 2009 г. Время: 02:15.

Чё-то я нихуя не понял.

Отзыв № 6 (ответ на отзыв № 4).
Автор: Антон. Дата: 16-го октября 2009 г. Время: 17:16.

Очень жаль

Отзыв № 42 (ответ на отзыв № 6).
Автор: Юрий. Дата: 3-го октября 2011 г. Время: 13:12.

Все понятно, но студентам которые не знают С++ сложновато его читать. ИМХО лучше параллельно (рядом с имеющимися) сделать примеры на Java или псевдокоде каком нибудь. Так будет удобнее.

Отзыв № 5
Автор: Sated. Дата: 14-го октября 2009 г. Время: 19:56.

Нихера не понял, так как всё-таки составлять пирамиду? Как её потом сортировать, можно попонятнее???

Отзыв № 7 (ответ на отзыв № 5).
Автор: Антон. Дата: 16-го октября 2009 г. Время: 21:49.

В полностью отсортированном массиве каждый следующий элемент больше предыдущего (и, значит, больше всех предыдущих). Пирамида же — это частично отсортированный массив. В ней элемент номер i больше элементов с номерами 2i+1 и 2i+2 (элементы нумеруются с нуля). Соответственно, построение пирамиды сводится к особой сортировке массива, чтобы выполнялось это свойство. При этом такая «неполная» сортировка делается гораздо быстрее, чем полная сортировка массива, так как отсортированные цепочки короткие.

Допустим, у нас имеется последовательность чисел:

1, 4, 2, 7, 8, 0, 5, 2, 6.

Чтобы построить пирамиду, нужно добиться, чтобы все элементы номер i были больше элементов номер 2i+1 и 2i+2 . Например, нулевой элемент должен быть больше первого и второго. В нашем примере это не так, поэтому поменяем нулевой элемент и первый:

4, 1, 2, 7, 8, 0, 5, 2, 6.

Первый элемент (единица) должен быть больше третьего (семёрки) и четвёртого (восьмёрки). Для этого поменяем местами единицу и восьмёрку:

4, 8, 2, 7, 1, 0, 5, 2, 6.

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

8, 4, 2, 7, 1, 0, 5, 2, 6.

Снова первый и третий не в порядке. Поменяем местами четвёрку и семёрку:

8, 7, 2, 4, 1, 0, 5, 2, 6.

Второй элемент (двойка) должен быть больше пятого (нуля) и шестого (пятёрки). Это не так. Поменяем местами двойку и пятёрку:

8, 7, 5, 4, 1, 0, 2, 2, 6.

Аналогично, четвёрка должна быть больше последних двойки и шестёрки. Поменяем местами четвёрку и шестёрку:

8, 7, 5, 6, 1, 0, 2, 2, 4.

Последние пять элементов не с чем сравнивать; их мы не трогаем. Теперь свойство пирамиды выполнено для всех элементов. Пирамида построена.

Обрати внимание, что первый элемент (семёрка) никак не связан со вторым (пятёркой), поэтому они остаются в «неправильном» порядке.

После того, как пирамида построена, из неё можно получить полностью отсортированный массив. Особенность пирамиды в том, что в её вершине (нулевой элемент) находится максимальный элемент среди всех элементов пирамиды. Но максимальный элемент должен быть в конце массива. Поменяем местами нулевой и последний элементы, и больше не будем последний элемент считать частью пирамиды:

4, 7, 5, 6, 1, 0, 2, 2 | 8.

Пирамида при этом нарушается. Восстанавливаем её так, как строили вначале (восьмёрку при этом не учитываем):

7, 6, 5, 4, 1, 0, 2, 2 | 8.

Снова самый большой элемент пирамиды находится вначале. Этот элемент — самый большой из оставшихся слева от восьмёрки. Поэтому он должен быть перед ней. Меняем местами нулевой элемент и последний элемент пирамиды, и отделяем последний элемент от пирамиды:

2, 6, 5, 4, 1, 0, 2 | 7, 8.

Восстанавливаем пирамиду:

6, 4, 5, 2, 1, 0, 2 | 7, 8.