Адаптивная сортировка кучи

В информатике адаптивная сортировка кучей — это алгоритм сортировки на основе сравнения из семейства адаптивных сортировок . Это вариант сортировки кучей , который работает лучше, когда данные содержат существующий порядок. Опубликованный Христосом Левкопулосом и Олой Петерссоном в 1992 году, алгоритм использует новую меру предварительной сортировки, Osc, как число колебаний. ^[1] Вместо того, чтобы помещать все данные в кучу, как это делала традиционная сортировка кучей, адаптивная сортировка кучей берет только часть данных в кучу, так что время выполнения значительно сокращается, когда предварительная сортировка данных высока. ^[1]

Пирамидальная сортировка

Сортировка кучи — это алгоритм сортировки, который использует двоичную структуру данных кучи . Метод рассматривает массив как полное двоичное дерево и создает Max-Heap/Min-Heap для достижения сортировки. ^[2] Обычно он включает следующие четыре шага.

Построить Max-Heap(Min-Heap): поместить все данные в кучу так, чтобы все узлы были больше или равны (меньше или равны для Min-Heap ) каждому из ее дочерних узлов.
Поменять местами первый элемент кучи с последним элементом кучи.
Удалить последний элемент из кучи и поместить его в конец списка. Отрегулируйте кучу так, чтобы первый элемент оказался в правильном месте в куче.
Повторяйте шаги 2 и 3, пока в куче не останется только один элемент. Поместите этот последний элемент в конец списка и выведите список. Данные в списке будут отсортированы.

Ниже представлена реализация на языке C/C++, которая создает Max-Heap и сортирует массив после создания кучи.

/* Пример кода сортировки кучи на AC/C++, сортирующего массив в порядке возрастания */// Функция, которая создает двоичное дерево с максимальной кучей void heapify ( int array [], int start , int end ) { int parent = start ; int child = parent * 2 + 1 ; while ( child <= end ) { if ( child + 1 <= end ) // когда есть два дочерних узла { if ( array [ child + 1 ] > array [ child ]) { child ++ ; // берем больший дочерний узел } } if ( array [ parent ] > array [ child ]) { return ; // если родительский узел больше, то он уже кучный } if ( array [ parent ] < array [ child ]) // когда дочерний узел больше родительского узла { swap ( array [ parent ], array [ child ]); // меняем местами родительский и дочерний узлы parent = child ; child = child * 2 + 1 ; // продолжаем цикл, сравниваем дочерний узел и его дочерние узлы } } }                                                    // heap_sort function void heap_sort ( int array [], int len ) { for ( int i = len / 2 - 1 ; i >= 0 ; i -- ) //Шаг 1: создаем максимальную кучу { heapify ( array , i , len ); } for ( int i = len - 1 ; i >= 0 ; i -- ) //Шаг 4: повторяем шаги 2 и 3 до завершения { swap ( array [ 0 ], array [ i ]); //Шаг 2: помещаем максимум в конец массива heapify ( array , 0 , i -1 ); //Шаг 3: удаляем максимум из дерева и снова выполняем heapify } }                                   инт мейн () { // массив, который будет отсортирован int array [] = { 42 , 1283 , 123 , 654 , 239847 , 45 , 97 , 85 , 763 , 90 , 770 , 616 , 328 , 1444 , 911 , 315 , 38 , 5040 , 1 }; int array_len = sizeof ( array ) / sizeof ( * array ); // длина массива                         heap_sort ( array , array_len );  вернуть 0 ; }

Меры предварительной сортировки

Меры предварительной сортировки измеряют существующий порядок в заданной последовательности. ^[3] Эти меры предварительной сортировки определяют количество данных, которые будут помещены в кучу во время процесса сортировки, а также нижнюю границу времени выполнения. ^[4]

Колебания (Оск)

Для последовательности Cross ( x i ₎ определяется как число ребер линейного графика X , которые пересекаются горизонтальной линией, проходящей через точку ( i, x _i ). Математически это определяется как . Осцилляция ( Osc ) X — это просто общее число пересечений, определяемое как . ^[1] $X=\langle x_{1},x_{2},x_{3},\dots,x_{n}\rangle$ ${\mathit {Крест}}(x_{i})=\{j\mid \min\{x_{j},x_{j+1}\}<x_{i}<\max\{x_{j},x_{j+1}\}{\text{ для }}1\leq j<n\}{\text{, для }}1\leq i\leq n$ ${\mathit {Осц}}(x)=\textstyle \sum _{i=1}^{n}\displaystyle \lВерт {\mathit {Крест}}(x_{i})\rВерт$

Другие меры

Помимо исходного измерения Osc, другие известные меры включают число инверсий Inv , число запусков Runs , число блоков Block и меры Max , Exc и Rem . Большинство из этих различных измерений связаны с адаптивной сортировкой кучи. Некоторые меры доминируют над другими: каждый Osc-оптимальный алгоритм является Inv-оптимальным и Runs-оптимальным; каждый Inv-оптимальный алгоритм является Max-оптимальным; и каждый Block-оптимальный алгоритм является Exc-оптимальным и Rem-оптимальным. ^[4]

Алгоритм

Адаптивная сортировка кучей — это вариант сортировки кучей, которая ищет оптимальность (асимптотически оптимальную) относительно нижней границы, полученной с помощью меры предварительной сортировки, используя существующий порядок в данных. В сортировке кучей для данных мы помещаем все n элементов в кучу, а затем продолжаем извлекать максимум (или минимум) n раз. Поскольку время каждого действия по извлечению максимума является логарифмическим по размеру кучи, общее время выполнения стандартной сортировки кучей составляет . ^[2] Для адаптивной сортировки кучей, вместо помещения всех элементов в кучу, в кучу будут помещены только возможные максимумы данных (максимальные кандидаты), так что потребуется меньше запусков, когда каждый раз мы пытаемся найти максимум (или минимум). $X=\langle x_{1},x_{2},x_{3},\dots,x_{n}\rangle$ $\color {Синий}O(n\log n)$

Сначала декартово дерево строится из входных данных со временем путем помещения данных в двоичное дерево и делая каждый узел в дереве больше (или меньше), чем все его дочерние узлы, а корень декартового дерева вставляется в пустую двоичную кучу. Затем многократно извлекается максимум из двоичной кучи, извлекается максимум в декартовом дереве и добавляется его левый и правый потомки (если есть), которые сами являются декартовыми деревьями, в двоичную кучу. Если входные данные уже почти отсортированы, декартовы деревья будут очень несбалансированными, с немногими узлами, имеющими левых и правых потомков, в результате чего двоичная куча остается небольшой и позволяет алгоритму сортировать быстрее, чем для входных данных, которые уже почти отсортированы. ^[5] $O(n)$ $O(n\log n)$

Ниже представлена реализация в псевдокоде: ^[1]

Входные данные: массив из n элементов, которые необходимо отсортировать.Построить декартово дерево l ( x )Вставьте корень l ( x ) в кучудля i = от 1 до n{ Выполнить ExtractMax в куче если максимальный извлеченный элемент имеет какие-либо дочерние элементы в l ( x ) { получить детей в l ( x ) вставить дочерний элемент в кучу }}

Недостатки

Несмотря на десятилетия исследований, между теорией адаптивной сортировки кучи и ее практическим применением все еще существует разрыв. Поскольку алгоритм использует декартовы деревья и манипуляцию указателями, он имеет низкую эффективность кэширования и высокие требования к памяти, что ухудшает производительность реализаций. ^[4]

Смотрите также

Ссылки

^ abcd Левкопулос, К.; Петерссон, О. (1993-05-01). «Адаптивная пирамидальная сортировка». Журнал алгоритмов . 14 (3): 395–413. doi :10.1006/jagm.1993.1021. ISSN 0196-6774.
^ ab Шаффер, Р.; Седжвик, Р. (1993-07-01). «Анализ пирамидальной сортировки». Журнал алгоритмов . 15 (1): 76–100. doi :10.1006/jagm.1993.1031. ISSN 0196-6774.
^ Маннила, Хейкки (апрель 1985 г.). «Меры предварительной сортировки и оптимальные алгоритмы сортировки». IEEE Transactions on Computers . C-34 (4): 318–325. doi :10.1109/TC.1985.5009382. ISSN 0018-9340.
^ abc Эделькамп, Стефан; Элмасри, Амр; Катаяйнен, Юрки (2011). «Две оптимальные по константам коэффициентов реализации адаптивной пирамидальной сортировки». В Iliopoulos, Костас С.; Смит, Уильям Ф. (ред.). Комбинаторные алгоритмы . Конспект лекций по информатике. Том 7056. Springer Berlin Heidelberg. стр. 195–208. doi :10.1007/978-3-642-25011-8_16. ISBN 9783642250118. S2CID 10325857.
^ "Архив интересного кода". www.keithschwarz.com . Получено 2019-10-31 .