ПРИМЕЧАНИЕ. Это для людей, которые уже знают, как реализовать структуру данных кучи без использования какой-либо библиотеки. Если нет, я рекомендую изучить его и понять внутреннюю работу кучи.
Куча - это древовидная структура данных, в которой все узлы дерева расположены в определенном порядке. По сути, это полное двоичное дерево, удовлетворяющее таким свойствам кучи, как min-heap и max-heap.
Кучи используются во многих известных алгоритмах, таких как алгоритм Дейкстры для поиска кратчайшего пути, алгоритм сортировки кучи, реализующий приоритетные очереди и многое другое. По сути, кучи - это структура данных, которую вы будете использовать, когда хотите очень быстро получить доступ к минимальному или максимальному элементу.
- Минимальная куча: это свойство кучи, в котором родительский элемент является наименьшим среди его левого и правого дочерних элементов, а корневой элемент - наименьшим среди всех элементы.
- Max-heap: в этом свойстве родительский элемент самый большой среди его левого и правого дочерних элементов, , а корневой элемент является самым большим среди всех элементов.
Библиотека для реализации min-heap и max-heap:
«heapq» с помощью этой библиотеки мы можем обрабатывать операции, выполняемые в куче.
heapq.heapify(listForTree) Используйте для создания минимальной кучи, он принимает список в качестве параметра.
heapq._heapify_max(listForTree) Используйте для создания максимальной кучи, он принимает список в качестве параметра.
heapq.heappop(minheap) используется для извлечения элемента из минимальной кучи, разница между обычным pop() и heappop() заключается в том, что после функции heappop свойство кучи данного списка сохраняется. Он возвращает наименьший, то есть корневой элемент дерева.
heapq._heappop_max(maxheap) эта функция pop выталкивает корневой элемент, т.е. самый большой элемент в дереве, и после функции pop сохраняется свойство кучи.
Чтобы увидеть все методы, которые вы можете использовать с heapq, ознакомьтесь с документацией Python по heapq.
Спасибо за прочтение!
