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

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

Сортировка кучи (heapsort) — это метод сортировки, основанный на сравнении, использующий двоичную кучу.

Что такое двоичная куча?

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

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

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

При представлении кучи в виде массива, предполагая, что индекс начинается с 0, корневой элемент хранится в 0. В общем случае, если родительский узел находится в позиции I, то левый дочерний узел находится в позиции (2 * I + 1), а правый узел находится в (2 * I + 2).

Общий алгоритм

Ниже приведен общий алгоритм для метода сортировки кучи:

  • Создать максимальную кучу из заданных данных таким образом, чтобы корень был самым высоким элементом кучи.
  • Удалить корневой узел, то есть самый высокий элемент из кучи, и заменить его последним элементом кучи.
  • Затем отрегулировать максимальную кучу, чтобы не нарушать свойства максимальной кучи (heapify).
  • Приведенный выше шаг уменьшает размер кучи на 1.
  • Повторить вышеуказанные три шага, пока размер кучи не уменьшится до 1.

Читать также:  Списки В STL

Как показано в общем алгоритме сортировки данного набора данных в порядке возрастания, мы сначала создаем максимальную кучу для заданных данных.

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

6, 10, 2, 4, 1

Мы можем построить дерево из этого набора данных следующим образом:

Построить дерево

В приведенном выше древовидном представлении, числа в скобках представляют соответствующие позиции в массиве.

Чтобы построить максимальную кучу вышеупомянутого представления, нам нужно выполнить условие кучи, чтобы родительский узел был больше, чем его дочерние узлы. Другими словами, нам нужно “нагромождать” дерево, чтобы преобразовать его в max-heap (максимальную кучу).

После приведенного выше дерева мы получим максимальную кучу, как показано ниже:

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

Выше показана максимальная куча, сгенерированная из массива.

Далее мы представим демонстрацию сортировки кучи. Ознакомившись с построением max-heap, мы пропустим подробные шаги по построению max-heap и будем непосредственно показывать максимальную кучу на каждом шаге.

Демонстрация

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

Массив элементов

Давайте построим максимальную кучу, как показано ниже, для сортируемого массива:

Построение максимальной кучи

Как только куча создана, мы представляем ее в виде массива, как показано ниже:

Куча создана

Теперь мы сравниваем 1-й узел (корневой) с последним узлом, а затем меняем их местами. Таким образом, как показано на схеме выше, мы меняем местами 17 и 3 так, чтобы 17 было на последней позиции, а 3 — на первой.

Теперь мы удаляем узел 17 из кучи и помещаем его в отсортированный массив, как показано в заштрихованной части на схеме ниже:

Изображение - Удаляем узел 17 из кучи

Теперь мы снова создаем кучу для элементов массива. На этот раз размер кучи уменьшен на 1, поскольку мы удалили один элемент (17) из кучи.

Читать также:  Моделирование дифференциального привода робота, управляемого операционной системой ROS

Куча оставшихся элементов показана ниже:

Куча оставшихся элементов

На следующем шаге мы повторяем тоже самое.

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

Меняем местами корневой элемент

После замены мы удаляем элемент 12 из кучи и перемещаем его в отсортированный массив:

Удаляем элемент 12

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

Создаем максимальную кучу

Теперь мы меняем местами корень и последний элемент, т.е. 9 и 3. После замены элемент 9 удаляется из кучи и помещается в отсортированный массив:

Меняем местами корень и последний элемент

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

Три элемента в куче

Мы меняем местами 6 и 3 и удаляем элемент 6 из кучи и добавляем его в отсортированный массив:

Меняем местами 6 и 3

Теперь мы создаем кучу оставшихся элементов, а затем меняем их местами друг с другом:

Создаем кучу оставшихся элементов

После замены 4 и 3 мы удаляем элемент 4 из кучи и добавляем его в отсортированный массив. Теперь у нас остался только один узел в куче, как показано ниже:

Удаляем элемент 4 из кучи

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

Остался только один узел

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

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

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

Читать также:  Дружественные функции в C++

Далее мы реализуем пирамидальную сортировку на языках C ++ и Java.

Наиболее важной функцией в обеих реализациях является функция “heapify”. Эта функция вызывается основной процедурой сортировки кучи для перестановки поддерева после удаления узла или при создании максимальной кучи.

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

Ниже приведен код программы на C ++ для реализации сортировки кучи:

Вывод данных:

Входной массив
4 17 3 12 9 6
Сортированный массив
3 4 6 9 12 17

Далее мы реализуем сортировку кучи на языке Java:

Вывод данных:

Входной массив:
4 17 3 12 9 6
Сортированный массив:
3 4 6 9 12 17

Итог

Пирамидальная сортировка или сортировка кучи — это метод сортировки на основе сравнения с использованием двоичной кучи.

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

Сортировка кучи использует max-heap или min-heap для сортировки массива. Первым шагом в сортировке кучи является создание минимальной или максимальной кучи из данных массива, а затем рекурсивное удаление корневого элемента и увеличение кучи до тех пор, пока в куче не останется только один узел.

Сортировка кучи — эффективный алгоритм, и он выполняется быстрее, чем сортировка по выбору. Он может использоваться для сортировки почти отсортированного массива или поиска k самых больших или самых маленьких элементов в массиве.

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

С Уважением, МониторБанк

Добавить комментарий