Адаптивная сортировка кучи - Adaptive heap sort

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

Heapsort

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

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

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

#include  / *Пример кода сортировки кучи C ++, который сортирует массив в возрастающем порядке* / using namespace std; void heapify (int array [], int start, int end); // A функция, которая создает двоичное дерево с максимальной кучейvoid heapify (int array [], int start, int end) {int родительский = начало; int child = родитель * 2 + 1; while (child <= end) {if (child + 1 <= end) // когда есть два дочерних узла{если (массив [ребенок + 1]> массив [ребенок]) {ребенок ++; // берем больший дочерний узел}} если (массив [родитель]> массив [ребенок]) {возврат; // если родительский узел больше, значит он уже скопирован} if (массив [родитель] <массив [дочерний элемент]) // когда дочерний узел больше родительского{своп (массив [родитель], массив [дочерний]); // переключаем родительский и дочерний узелродитель = ребенок; ребенок = ребенок * 2 + 1; // продолжаем цикл, сравниваем дочерний узел и его дочерние узлы}}} void heap_sort (int array [], int len); // функция heap_sortvoid heap_sort (int array [], int len) {для (int i = len / 2 - 1; i> = 0; i--) // Шаг 1: создаем максимальную кучу{heapify (массив, я, лен); } для (int i = len - 1; i> = 0; i--) // Шаг 4: повторяем шаги 2 и 3 до завершения{своп (массив [0], массив [i]); // Шаг 2: поместите максимум в конец массиваheapify (массив, 0, i-1); // Шаг 3: удалим максимум из дерева и снова добавим в кучу}} int main () {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 (массив) / sizeof (* массив); // длина массиваheap_sort (array, array_len); // сортировка по куче return 0;}

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

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

Колебания (Osc)

Для последовательности , Крест(Икся) определяется как количество ребер линейного графика X, которые пересекаются горизонтальной линией через точку (i, xя). Математически это определяется как, за . Колебание (Osc) X - это просто общее количество пересечений, определяемое как .[1]

Прочие меры

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

Алгоритм

Адаптивная сортировка кучи - это вариант сортировки кучи, который стремится к оптимальности (асимптотически оптимальной) по отношению к нижней границе, полученной с помощью меры предварительной сортировки, используя преимущества существующего порядка в данных. В куче сортировки для данных , мы помещаем все n элементов в кучу, а затем продолжаем извлекать максимум (или минимум) n раз. Поскольку время каждого действия максимального извлечения является логарифмическим по размеру кучи, общее время выполнения стандартной сортировки кучи равно O (п войти п).[2] Для адаптивной сортировки кучи вместо помещения всех элементов в кучу в кучу будут помещены только возможные максимумы данных (max-кандидаты), так что требуется меньше запусков, когда каждый раз, когда мы пытаемся найти максимум (или минимум). Первый Декартово дерево строится из ввода в времени, помещая данные в двоичное дерево и делая каждый узел в дереве больше (или меньше), чем все его дочерние узлы, а корень декартова дерева вставляется в пустую двоичную кучу. Затем несколько раз извлеките максимум из двоичной кучи, извлеките максимум в декартовом дереве и добавьте его левый и правый дочерние элементы (если есть), которые сами являются декартовыми деревьями, в двоичную кучу. Если входные данные уже почти отсортированы, декартовы деревья будут очень несбалансированными, с несколькими узлами, имеющими левые и правые дочерние элементы, в результате чего двоичная куча останется небольшой и позволит алгоритму сортировать быстрее, чем для входов, которые уже почти отсортированы.[5]

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

Недостатки

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

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

Рекомендации

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