1

Есть алгоритм сортировки кучей по возрастанию:

  1. Вставлять элементы, делая min-heap
  2. Удалять элементы (root), оставляя свойства

У меня есть вопросы к этому коду:

def heap_sort(arr, size):
    for i in range(size // 2 - 1, -1, -1):
        heapify(arr, size, i)

    for i in range(size - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

    print(arr)


def heapify(array, size, index):
    done = False

    while not done:
        largest = index
        left = 2 * index + 1
        right = 2 * index + 2

        if left < size and array[largest] < array[left]:
            largest = left

        if right < size and array[largest] < array[right]:
            largest = right

        if largest != index:
            array[index], array[largest] = array[largest], array[index]
            index = largest
        else:
            done = True
  1. Как получается сортировка по возрастанию, если куча max-heap
  2. Я понимаю, что в heap_sort первый цикл строит кучу, второй удаляет элементы, знаю, как работает удаление и добавление в куче. Но я не понимаю, почему отсчет идет к концу с size // 2 - 1. Почему во втором цикле тоже идет отсчёт к концу
  3. Почему это все работает, если где-то пишут, что левый элемент считается по формуле 2i, а здесь 2i + 1. Я тестил свою сортировку кучей с 2i + 1 на левый элемент и все ломалось

При этом я не до конца понимаю условий в heapify. Буду благодарен, если кто-нибудь понятным языком и подробно объяснит, как работает алгоритм сверху

5
  • Первый же вопрос: "а где вы алгоритм взяли, и почему уверены, что он совершенно верно написан?" 21 апр 2022 в 15:40
  • @Сергей я передавал в него 4 разных массива - сортирует по возрастанию 21 апр 2022 в 15:44
  • Я писал не "выдаёт верный результат", а "совершенно верно работает" (т.е. алгоритм совпадает на 100% с описанным). Но не важно, ответ дали уже ниже. 21 апр 2022 в 16:21
  • @Сергей так видно, что он делает - билдит кучу из массива (вставляет элементы) и вынимает элементы 21 апр 2022 в 16:41
  • 1
    Традиционно такую структуру данных на русском называют пирамидойкучей именуют область памяти для ее динамического (malloc, new и т.п.) выделения)
    – avp
    21 апр 2022 в 21:37

1 ответ 1

2

1.. Вот эта операция

arr[i], arr[0] = arr[0], arr[i]

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

2.. "Отсчёт" идёт к началу, за это отвечает шаг -1 в range. Почему с size // 2 - 1? - да потому что это индекс последнего родителя в куче, у элементов с большим номером нет деток.

3.. Левый элемент считается по формуле 2i, если индексация идёт с единицы, а здесь использована индексация с нуля.

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.