Руководство по кучам в Python

Введение

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

В этом руководстве мы отправимся в путешествие, чтобы понять кучу вещей с нуля. Мы начнем с выяснения того, что такое кучи и присущие им свойства. Далее мы углубимся в собственную реализацию куч в Python, heapq модуль и изучите его богатый набор функций. Итак, если вы когда-нибудь задавались вопросом, как эффективно управлять динамическим набором данных, где часто требуется элемент с самым высоким (или самым низким) приоритетом, вас ждет удовольствие.

Что такое куча?

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

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

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

По мере продвижения мы глубже углубимся в то, как эти присущие кучам свойства обеспечивают эффективные операции и как Python heapq модуль легко интегрирует кучу в наши усилия по кодированию.

Характеристики и свойства отвалов

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

Прежде всего, это кучи по своей сути эффективный. Их древовидная структура, в частности полный формат двоичного дерева, гарантирует, что такие операции, как вставка и извлечение элементов приоритета (максимального или минимального), могут выполняться за логарифмическое время, обычно O (журнал n). Такая эффективность является благом для алгоритмов и приложений, которым требуется частый доступ к приоритетным элементам.

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

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

Кроме того, кучи разносторонний. Хотя двоичные кучи (где каждый родитель имеет не более двух дочерних элементов) являются наиболее распространенными, можно обобщить, что кучи имеют более двух дочерних элементов, известные как d-арные кучи. Такая гибкость позволяет осуществлять тонкую настройку в зависимости от конкретных случаев использования и требований к производительности.

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

По мере того, как мы углубляемся в реализацию и практическое применение Python, перед нами раскроется истинный потенциал куч.

Типы куч

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

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

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

Помимо этих основных категорий, кучи также можно различать по их коэффициенту ветвления:

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

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

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

Реализация кучи в Python – куча Модули

Python предлагает встроенный модуль для операций с кучей – heapq модуль. Этот модуль предоставляет набор функций, связанных с кучей, которые позволяют разработчикам преобразовывать списки в кучи и выполнять различные операции с кучей без необходимости специальной реализации. Давайте углубимся в нюансы этого модуля и в то, как он дает вам возможности кучи.

Ассоциация heapq модуль не предоставляет отдельный тип данных кучи. Вместо этого он предлагает функции, которые работают с обычными списками Python, преобразуя и обрабатывая их как двоичные кучи.

Этот подход эффективно использует память и легко интегрируется с существующими структурами данных Python.

Что означает, что кучи представлены в виде списков in heapq. Прелесть этого представления в его простоте: индексная система списка, начинающаяся с нуля, служит неявным двоичным деревом. Для любого данного элемента в позиции i, это:

• Левый ребенок находится в позиции 2*i + 1
• Правый ребенок находится на позиции 2*i + 2
• Родительский узел находится в позиции (i-1)//2

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

Важно отметить, что heapq модуль по умолчанию создает минимальную кучу. Это означает, что самый маленький элемент всегда находится в корне (или на первой позиции в списке). Если вам нужна максимальная куча, вам придется инвертировать порядок, умножив элементы на -1 или используйте собственную функцию сравнения.

Python heapq Модуль предоставляет набор функций, которые позволяют разработчикам выполнять различные операции с кучей над списками.

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

Как преобразовать список в кучу

Ассоциация heapify() Функция является отправной точкой для многих задач, связанных с кучей. Он принимает итерируемый объект (обычно список) и переупорядочивает его элементы на месте, чтобы удовлетворить свойства минимальной кучи:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)

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

[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

Как добавить элемент в кучу

Ассоциация heappush() Функция позволяет вставить новый элемент в кучу, сохраняя при этом свойства кучи:

import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

Запуск кода даст вам список элементов, поддерживающих свойство минимальной кучи:

[3, 5, 7]

Как удалить и вернуть самый маленький элемент из кучи

Ассоциация heappop() функция извлекает и возвращает наименьший элемент из кучи (корень в минимальной куче). После удаления он гарантирует, что список останется допустимой кучей:

import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)

Это выведет наименьший элемент и оставшийся список:

1
[3, 7, 5, 9]

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

Как отправить новый элемент и вытащить самый маленький элемент

Ассоциация heappushpop() Функция — это комбинированная операция, которая помещает новый элемент в кучу, а затем извлекает и возвращает самый маленький элемент из кучи:

import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)

Это будет выводить 3, самый маленький элемент, и распечатайте новый heap список, который теперь включает 4 сохраняя при этом свойство кучи:

3
[4, 5, 7, 9]

Как заменить самый маленький элемент и добавить новый элемент

Ассоциация heapreplace() Функция извлекает наименьший элемент и помещает новый элемент в кучу, и все это за одну эффективную операцию:

import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)

Это печатает 1, самый маленький элемент, и список теперь включает 4 и сохраняет свойство кучи:

1
[4, 5, 7, 9]

Поиск нескольких крайностей в куче Python

nlargest(n, iterable[, key]) и nsmallest(n, iterable[, key]) Функции предназначены для извлечения нескольких наибольших или наименьших элементов из итерируемого объекта. Они могут быть более эффективными, чем сортировка всей итерации, когда вам нужно всего лишь несколько крайних значений. Например, предположим, что у вас есть следующий список и вы хотите найти в нем три наименьших и три наибольшего значения:

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

Здесь, nlargest() и nsmallest() функции могут пригодиться:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data)) 

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

[9, 6, 5]
[1, 1, 2]

Как создать свою собственную кучу

В то время как Python heapq предоставляет надежный набор инструментов для работы с кучами, существуют сценарии, в которых поведение минимальной кучи по умолчанию может оказаться недостаточным. Если вы хотите реализовать максимальную кучу или вам нужна куча, которая работает на основе пользовательских функций сравнения, создание пользовательской кучи может быть ответом. Давайте рассмотрим, как адаптировать кучи к конкретным потребностям.

Реализация Max Heap с использованием heapq

По умолчанию heapq создает мин кучи. Однако с помощью простого трюка вы можете использовать его для реализации максимальной кучи. Идея состоит в том, чтобы инвертировать порядок элементов, умножив их на -1 прежде чем добавлять их в кучу:

import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]

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

Кучи с пользовательскими функциями сравнения

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

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

import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj

С помощью этой настройки вы можете определить любую пользовательскую функцию сравнения и использовать ее с кучей.

Заключение

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

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

• SEO-контент и PR-распределение. Получите усиление сегодня.
• PlatoData.Network Вертикальный генеративный ИИ. Расширьте возможности себя. Доступ здесь.
• ПлатонАйСтрим. Интеллект Web3. Расширение знаний. Доступ здесь.
• ПлатонЭСГ. Углерод, чистые технологии, Энергия, Окружающая среда, Солнечная, Управление отходами. Доступ здесь.
• ПлатонЗдоровье. Биотехнологии и клинические исследования. Доступ здесь.
• Источник: https://stackabuse.com/guide-to-heaps-in-python/