Программа будет сортировать список методом пирамидальной сортировки (Heapsort).
heapsort
, которая принимает на вход список.build_max_heap
c параметром alist
для представления листа в виде пирамиды (heap).max_heapify
, учитывая что новая пирамида имеет размер на единицу меньше. Установим index=0
для удовлетворения параметрам пирамиды.parent
, которая принимает index
и возвращает индекс родителя.left
, которая принимает index
и возвращает индекс левого дочернего элемента.right
, которая принимает index
и возвращает индекс правого дочернего элемента.build_max_heap
, которая принимает список аргументов и переставляет их в соостветсвии с max heap
.build_max_heap
вызывает max_heapify
на каждом родительском ноде и проходит до вершины.max_heapify
, которая принимает индекс и изменяет структуру пирамиды на ноде и снизу от индекса так, чтобы удовлетворять правилам пирамиды.def heapsort(alist): build_max_heap(alist) for i in range(len(alist) - 1, 0, -1): alist[0], alist[i] = alist[i], alist[0] max_heapify(alist, index=0, size=i) def parent(i): return (i - 1)//2 def left(i): return 2*i + 1 def right(i): return 2*i + 2 def build_max_heap(alist): length = len(alist) start = parent(length - 1) while start >= 0: max_heapify(alist, index=start, size=length) start = start - 1 def max_heapify(alist, index, size): l = left(index) r = right(index) if (l < size and alist[l] > alist[index]): largest = l else: largest = index if (r < size and alist[r] > alist[largest]): largest = r if (largest != index): alist[largest], alist[index] = alist[index], alist[largest] max_heapify(alist, largest, size) alist = input('Enter the list of numbers: ').split() alist = [int(x) for x in alist] heapsort(alist) print('Sorted list: ', end='') print(alist)
Pydantic - это мощная библиотека проверки данных и управления настройками для Python, созданная для повышения…
Python предлагает набор библиотек, удовлетворяющих различные потребности в визуализации, будь то академические исследования, бизнес-аналитика или…
В Python для представления данных в двоичной форме можно использовать байты. Из этой статьи вы…
В этой статье рассказывается о том, что такое Werkzeug и как Flask использует его для…
При работе с датами часто возникает необходимость прибавлять к дате или вычитать из нее различные…
В этом руководстве мы рассмотрим, как добавить социальную аутентификацию с помощью GitHub и Google в…