Heapsort Time Сложность

Куча называется «частично упорядоченной», а не «частично отсортированной». Слово «сортировка» означает полное упорядочение (полная сортировка). Куча не является частично упорядоченной произвольно. Куча частично упорядочена по критерию (шаблону), как показано ниже.

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

Цель этой статьи — кратко объяснить пирамидальную сортировку, а затем определить ее временную сложность (см. значение временной сложности ниже). Ближе к концу кодирование выполняется на C++.

Минимальная куча

Куча может быть минимальной кучей или максимальной кучей. Максимальная куча — это та, в которой первый элемент является самым высоким элементом, а все дерево или соответствующий список частично упорядочены в порядке убывания. Минимальная куча — это та, в которой первый элемент является наименьшим элементом, а весь список частично упорядочен в порядке возрастания. В этой статье рассматривается только минимальная куча. Примечание: в теме кучи элемент также называется узлом.

Куча — это полное бинарное дерево. Бинарное дерево можно представить в виде массива (списка); читать сверху вниз и слева направо. Свойство кучи для минимальной кучи заключается в том, что родительский узел меньше или равен каждому из двух своих дочерних узлов. Пример неупорядоченного списка:

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

Связь между узлами и индексами

Помните, что куча — это полное бинарное дерево до конфигурации кучи (свойство кучи). Предыдущий список еще не является кучей, потому что элементы не подчиняются свойству кучи. Он становится кучей после перестановки элементов в частичном порядке в соответствии со свойством min-heap. Частичный порядок можно рассматривать как частичную сортировку (хотя слово «сортировка» означает полный порядок).

Независимо от того, является ли бинарное дерево кучей или нет, у каждого родителя есть два дочерних элемента, кроме листовых (последних) узлов. Существует математическая связь между индексами между каждым родителем и его дочерними элементами. Это выглядит следующим образом: если родитель находится в индексе i, то левый дочерний элемент находится в индексе:

и правый ребенок находится в индексе:

Это для индексации с отсчетом от нуля. Таким образом, у родителя с индексом 0 есть левый дочерний элемент с индексом 2×0+1=1 и правый дочерний элемент с индексом 2×0+2=2. У родителя с индексом 1 есть левый дочерний элемент с индексом 2×1+1=3 и правый дочерний элемент с индексом 2×1+2=4; и так далее.

По свойству min-heap родитель в i меньше или равен левому дочернему элементу в 2i+1 и меньше или равен правому дочернему элементу в 2i+2.

куча

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

Если предыдущий несортированный список увеличить, он станет:

Примечание: в списке 12 элементов, а не 15. Во второй строке находятся индексы. В процессе построения кучи элементы приходилось проверять, а некоторые менять местами.

Обратите внимание, что наименьший и первый элемент равен 3. Остальные элементы следуют восходящим, но волнообразным образом. Если левый и правый дочерние элементы в позициях 2i+1 и 2i+2 больше или равны родительскому элементу в i, то это минимальная куча. Это не полный порядок или сортировка. Это частичное упорядочение в соответствии со свойством кучи. Отсюда начинается следующий этап сортировки кучи.

Увеличьте временную сложность

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

Где n равно N и максимально возможное количество основных операций. Эта запись называется записью Big-O. Он начинается с O в верхнем регистре, за которым следуют круглые скобки. В скобках указано максимально возможное количество операций.

Помните: сложение может стать умножением, если одно и то же прибавляемое повторяется.

Хипсорт Иллюстрация

Предыдущий несортированный список будет использоваться для иллюстрации пирамидальной сортировки. Данный список таков:

Минимальная куча, созданная из списка:

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

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

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

На втором этапе первое, что нужно сделать, это удалить 3 и поместить его в новый массив. Результаты:

а также

Остальные элементы должны быть загружены до того, как будет извлечен первый элемент. Куча остальных элементов может стать:

Извлечение 5 и добавление в новый список (массив) дает результаты:

а также

Наполнение оставшегося набора даст:

Извлечение 6 и добавление в новый список (массив) дает результаты:

а также

Наполнение оставшегося набора даст:

Извлечение 7 и добавление его в новый список дает результаты:

а также

Наполнение оставшегося набора дает:

Извлечение 9 и добавление в новый список дает результаты:

а также

Наполнение оставшегося набора дает:

Извлечение 11 и добавление его в новый список дает результаты:

а также

Наполнение оставшегося набора даст:

Извлечение 14 и добавление его в новый список дает результаты:

а также

Наполнение оставшегося набора даст:

Извлечение 15 и добавление его в новый список дает результаты:

а также

Наполнение оставшегося набора даст:

Извлечение 17 и добавление его в новый список дает результаты:

а также

Наполнение оставшегося набора даст:

Извлечение 19 и добавление его в новый список дает результаты:

а также

Наполнение оставшегося набора дает:

Извлечение 22 и добавление его в новый список дает результаты:

а также

Наполнение оставшегося набора дает:

Извлечение 24 и добавление его в новый список дает результаты:

а также

Массив кучи теперь пуст. Все элементы, которые у него были в начале, теперь находятся в новом массиве (списке) и отсортированы.

Алгоритм Heapsort

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

• Увеличить несортированный список.
• Извлеките первый элемент кучи и поместите его в качестве первого элемента нового списка.
• Увеличьте оставшийся список.
• Извлеките первый элемент новой кучи и поместите в качестве следующего элемента нового списка.
• Повторяйте предыдущие шаги по порядку, пока список кучи не станет пустым. В конце новый список сортируется.

Вертикальная сортировка по временной сложности

Одноэтапный подход используется для определения временной сложности пирамидальной сортировки. Предположим, что нужно отсортировать 8 несортированных элементов.

Возможное максимальное количество операций:

Среднее число этих операций равно:

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

так как журнал _два 8 = 3.

В целом, средняя временная сложность случая для пирамидальной сортировки составляет:

Где точка означает умножение, а n — это N, общее количество элементов в списке (любом списке).

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

Кодирование на С++

В библиотеке алгоритмов C++ есть функция make_heap(). Синтаксис:

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

Этот код изменяет содержимое вектора на минимальную конфигурацию кучи. В следующих векторах C++ вместо двух массивов будут использоваться два вектора.

Чтобы скопировать и вернуть первый элемент вектора, используйте векторный синтаксис:

Чтобы удалить первый элемент вектора и выбросить его, используйте векторный синтаксис:

Чтобы добавить элемент в конец вектора (следующий элемент), используйте векторный синтаксис:

Начало программы такое:

Алгоритм и векторные библиотеки включены. Далее в программе идет функция heapsort(), а именно:

Это рекурсивная функция. Он использует функцию make_heap() библиотеки алгоритмов C++. Второй сегмент кода в определении функции извлекает первый элемент из старого вектора после построения кучи и добавляет его в качестве следующего элемента для нового вектора. Обратите внимание, что в определении функции векторные параметры являются ссылками, а функция вызывается с идентификаторами (именами).

Подходящей основной функцией С++ для этого является:

Результат:

отсортировано (полностью).

Вывод

В статье подробно обсуждались природа и функции Heap Sort, широко известного как Heapsort, как алгоритма сортировки. Heapify Time Complexity, иллюстрация Heapsort и Heapsort как алгоритм были рассмотрены и подкреплены примерами. Средняя временная сложность хорошо написанной программы пирамидальной сортировки составляет O(nlog(n))