HeapSort — сортировка перед заменой

Я работал с алгоритмами и, в частности, с пирамидальной сортировкой. Насколько я понимаю, алгоритм heapsort включает в себя подготовку списка, сначала превращая его в максимальную кучу.

Поворачивая мой

[2, 8, 5, 3, 9, 1]

В
[9, 8, 5, 3, 2, 1]

С heapsort я должен поменять местами 9 на 1. Но, глядя на массив сразу после максимальной кучи, я вижу отсортированный список в порядке убывания. Зачем нужна подкачка, когда список уже отсортирован в порядке убывания?

Это были просто мысли, которые у меня возникли после просмотра: https://www.youtube.com/watch?v=2DmK_H7IdTo


sorting algorithm heapsort max-heap
person Rainoa    schedule 13.06.2017    source источник

Ответы (2)


arrow_upward
5
arrow_downward

После создания кучи она не обязательно сортируется в порядке убывания.

Куча только требует, чтобы каждый узел был больше (или меньше, для минимальной кучи), чем его дочерние элементы, но ничего не говорит ни о порядке дочерних элементов, ни об отношении узлов на разных уровнях (где один не является прямым потомком другой, см. 5 и 6 ниже). Это означает, что это также будет допустимой кучей:

     9
   /   \
  5     8
 / \   /
1   2 6

[9, 5, 8, 1, 2, 6]
person Bernhard Barker    schedule 13.06.2017

arrow_upward
1
arrow_downward

На ваш вопрос

Зачем нужна подкачка, когда список уже отсортирован в порядке убывания?

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

Функция heapify() гарантирует создание кучи. И в вашем случае это произошло в порядке убывания. Другой случай указан в ответе Dukeling, который не в порядке убывания.

В куче сортировки после первого вызова heapify() мы знаем только одно. Корень кучи (1-й элемент в массиве) — это элемент Max в массиве. Таким образом, переместите его на свое место (последнее место) и уменьшите размер массива на 1 и повторите те же действия для всех элементов.

Операция heapify() будет O(log n) и, следовательно, общая сложность O(n log n)

Надеюсь, поможет!

person arunk2    schedule 14.06.2017