Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняГлава 21 алгоритмов и структур данных, поговорим о новой структуре данных -куча(куча).
По сравнению с популярными структурами данных, такими как связанные списки, двоичные деревья и массивы, кучи относительно непопулярны. Если у вас нет глубокого понимания структур данных, вы можете редко слышать об этом. Но мы часто его используем, даже если вы не обязательно это чувствуете. Напримерприоритетная очередь, мы используем его часто. Нам нужно использовать такую структуру данных, которую можно сортировать в соответствии с приоритетом данных, которые мы храним, и более высокий приоритет будет ранжироваться первым. В некоторых системах и алгоритмах, связанных с планированием, обязательно должны использоваться приоритетные очереди. Но мало кто знает, что приоритетная очередь называется очередью, а на самом деле реализуется через кучу.
Так что же такое структура данных кучи?
Определение кучи
Суть кучи на самом делебинарное дерево, и это не обычное бинарное дерево, а специальное бинарное дерево.
В частности, все узлы этого бинарного дерева, кроме листьев, «заполнены». Так называемый полный означает, что вакансий нет.
Как видно из рисунка выше, если удалить последний слой, то бинарное дерево будет полным. Последний слой конечных узлов также требуется, и листовые узлы должны бытьВыровнять по левому краю. Двоичное дерево, удовлетворяющее этим двум условиям, становитсяполное бинарное дерево(полное бинарное дерево). Неважно, если вы не можете вспомнить это понятие, я, кажется, встречал его только в куче.
Кучи — это полные бинарные деревья, но, очевидно, не все полные бинарные деревья — это кучи.Кучи также обладают особым свойством, котороетранзитивность размера.
Куча делится на разные размеры в соответствии с транзитивностьюБольшие и маленькие верхние сваи, так называемая куча с большой вершиной означает, что элемент в верхней части кучи, то есть элемент в корне дерева, является самым большим. Если это небольшая верхняя куча, верно обратное, и верхний элемент кучи является наименьшим. Таким образом, они в основном одинаковы, давайте в качестве примера возьмем кучу с большой вершиной. Эту транзитивность на самом деле очень легко понять, на самом деле она только одна, т.Значение всех узлов больше, чем значения двух его дочерних элементов. То есть каждый путь от корня к листьям уменьшается.
Мы можем посмотреть на эту картинку:
100 имеет два дочерних узла, 19 и 36, а 100 больше, чем 19 и 36. У 19 двое детей 17 и 3, 19 старше их обоих. Это следует хорошо понимать. В чем гениальный смысл кучи? Гениальный смысл в том, что мы можемиспользуйте массив для хранения этой структуры, без необходимости строить его самостоятельно. Метод хранения в массиве также очень прост, мы можем индексировать точки на графике, чтобы получить:
Мы находим правило, мы можем найти его для узла на дереве, предполагая, что его индекс в массиве равен i. Тогда его левый дочерний элемент имеет индекс i * 2 + 1, его правый дочерний элемент имеет индекс i * 2 + 2, а его родитель имеет индекс (i - 1) // 2.
С этим правилом, пока мы знаем координаты определенной точки, мы можем знать координаты ее отца и двух детей. Это также очень аккуратный и удобный момент использования массивов для хранения кучи.
Вставка кучи
Какая польза от этого имущества? На самом деле, это очень полезно, мы можем использовать его для очень удобного обслуживания кучи.
Во-первых, представьте, что вставка элемента в конец кучи не нарушает свойства полного бинарного дерева. Поскольку листовые узлы полного бинарного дерева выровнены по левому краю, вставляемые элементы также должны быть крайними левыми, поэтому независимо от того, насколько велико значение вставляемых элементов, это не повлияет на свойство полного бинарного дерева. бинарное дерево. Но очевидно, что размер вставляемого значения повлияет на правильность структуры кучи, например, если мы вставим 9, вставленная позиция не будет удовлетворять свойствам большой верхней кучи.
В это время, чтобы сохранить природу кучи, мыданные, которые необходимо скорректировать. Так что на самом деле процесс вставки элементов в кучу это процесс корректировки порядка.Как настроить это на самом деле очень просто.Это сравнение элемента который мы вставили вверх.Если он больше своего родительского элемента узла,то сравните его с элементом родительского узла.Меняйте местами до тех пор, пока он не станет меньше родительского или не будет называться вершиной кучи.
Предположим, что элемент, который мы вставили, не 9, а 105, тогда конечный результат должен быть таким:
Это процесс вставки кучи, потому что мыТолько вставленные позиции могут привести к повреждению структуры кучи, поэтому нам нужно только поддерживать вверх от вставленной позиции. Остальные местоположения не затрагиваются, и для узлов на всей линии связи, которые могут быть затронуты,Они могут стать только больше, а не меньшеНовое поколение не удовлетворяет свойству кучи и поэтому не будет заменено позже.
Поскольку этот процесс вставки восходящий, весь процесс также называетсяОбновление.
Давайте взглянем на восходящий код обслуживания, который очень прост и состоит всего из нескольких строк:
def maintain(self):
# 因为向上更新出现在插入元素之后，所以从最后一个位置开始维护
n = self._size - 1
# cmp是自定义比较函数，用来自定义大顶堆还是小顶堆
while n > 0 and self.cmp(self.items[n], self.items[(n-1)//2]):
# 如果当前节点比父节点“大”，则交换
self.items[n], self.items[(n-1)//2] = self.items[(n-1)//2], self.items[n]
n = (n - 1) // 2
После понимания вставки кучи следует также хорошо понять ее создание. Так называемый процесс построения кучи на самом делеВставлять элементы в кучу один за другимпроцесс в нем.
Мы используем метод поддержания, чтобы легко реализовать процесс построения кучи.
def push(self, item):
if self._size_limit is not None and self._size > self._size_limit:
raise IndexError('Heap is full')
# array_size是数组的长度
# 由于允许弹出元素，所以会导致数组的长度大于当前元素的数量的情况
if self._size < self.array_size:
self.items[self._size] = item
self._size += 1
# 如果数组长度等于元素数量，那么append到数组末尾
else:
self.items.append(item)
self._size += 1
self.array_size += 1
# 调用maintain，维护堆性质
self.maintain()
@staticmethod
def heapify(elements, min_or_max='min', compare_function=None):
# 初始化， min_or_max表示是大顶堆还是小顶堆，允许传入自定义比较函数
heap = HeapQueue(min_or_max=min_or_max, compare_function=compare_function)
for i in elements:
heap.push(i)
return heap
Запрос кучи и поп
В отличие от других структур данных, куча очень ограничена для запросов данных.Разрешается запрашивать только элементы в верхней части кучи.. Если это большая верхняя куча, разрешается запрашивать максимальный элемент, в противном случае разрешается запрашивать минимальный элемент. Так же, такжеРазрешить удаление элементов только из вершины кучи, также известный как «всплывающие», потому что удаление элементов в верхней части кучи похоже на выдавливание элементов, как зубной пасты.
Просто запрос понятен, мы можем вернуть элемент с индексом 0 массива, но что, если это всплывающее окно? Разве верхний элемент кучи не пуст после появления? Что делать после появления вакансии?
Один из способов состоит в том, чтобы выбрать одного из потомков корневого узла в качестве замены, но после того, как замена будет создана, будет создана новая вакансия, так что свойства полного бинарного дерева могут не сохраниться, если будет произведена настройка. Так что есть только один способ, и он очень интуитивен, т.Возьмите элемент в конце в качестве замены и поместите его на вершину кучи. Но очевидно, что элемент в конце не самый большой, поэтому после этой операции его нужно скорректировать.
Как настроить?
Разумеется, он сравнивается с левым и правым дочерними элементами из вершины кучи.Если есть больший левый и правый дочерние элементы, чем он, то меняем местами и передаем этот элемент вниз. Например, на рисунке ниже мы выталкиваем вверху кучи элемент 100. Согласно логике алгоритма, мы будем использовать последние 7 в качестве замены.
В первый раз, когда мы сравниваем его с 19 и 36, мы выбираем самый большой из них, 36, для обмена из-за природы большой верхней кучи. Итак, мы передаем 7 вниз к исходной позиции 36 и продолжаем сравнивать ее с двумя дочерними узлами. Мы обнаружили, что 25 больше 7, поэтому продолжили обмен, а в это время достигли листового узла и остановились.
Оглядываясь назад на результаты после обслуживания, мы по-прежнему удовлетворяем свойствам большой верхней кучи, ипо-прежнему является полным бинарным деревом. По сравнению с обслуживанием при вставке только что, мы обнаружим, что весь процесс на самом деле представляет собой процесс нисходящего обновления. Ядро структуры данных кучи на самом деле находится в этих двух обновлениях.Обновлять вверх при вставке, обновлять вниз при извлечении.
Код тоже очень простой:
def pop(self):
front = self.items[0]
# 弹出下标为0的节点之后，将末尾元素插入头部
self.items[0] = self.items[self._size-1]
self._size -= 1
self.downward_maintain()
return front
def downward_maintain(self):
n = 0
while n * 2 + 1 < self._size:
# 计算左右孩子的下标
left_child = n * 2 + 1
right_child = n * 2 + 2
# 判断左右孩子的大小关系，只会和其中大的发生交换
if self.cmp(self.items[left_child], self.items[right_child]):
# 如果左孩子大于右孩子也大于父节点，则交换
if self.cmp(self.items[left_child], self.items[n]):
self.items[n], self.items[left_child] = self.items[left_child], self.items[n]
n = left_child
else:
break
# 如果右孩子最大，也交换
elif self.cmp(self.items[right_child], self.items[n]):
self.items[n], self.items[right_child] = self.items[right_child], self.items[n]
n = right_child
else:
break
Куча и приоритетная очередь
На этом основная часть всей кучи завершена. Весь процесс относительно интуитивно понятен и не сложен.Достаточно запомнить два обновления.
Поняв, что такое куча, давайте посмотрим на очередь с приоритетом.Когда мы используем очередь с приоритетом, мы надеемся каждый раз извлекать данные с наивысшим приоритетом, а затем, когда мы заполняем данные, очередь автоматически сортирует данные в соответствии с к установленному нами приоритету. Разве это не то, что делает куча? Так что через кучу мы можем легко реализовать приоритетную очередь.Конечно, нам этого делать не нужно, потому что готовая куча инкапсулируется за нас в Python.Нам нужно только вызвать ее, и мы легко инкапсулируем очередь с приоритетом.
import heapq
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
# 传入两个参数，一个是存放元素的数组，另一个是要存储的元素，这里是一个元组。
# 由于heap内部默认由小到大排，所以对priority取负数
heapq.heappush(self._queue, (-priority, self._index, item))
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1]
Вы также можете добавить некоторые другие вспомогательные функции в этот класс, если хотите. Конечно, я по-прежнему предлагаю, чтобы каждый мог реализовать свою собственную очередь приоритетов с кучами с нуля и испытать чувство выполненного долга от реализации структур данных вручную. Если вы хотите сослаться на мой код, вы можете ответить в официальном аккаунте"куча", я посылаю вам мой код.
Куча очень практична и несложна в написании.Я надеюсь, что каждый может испытать радость от ручного проката структур данных.
Сегодняшняя статья здесь, оригинальность не из легких,Отсканируйте код, чтобы следоватьМеня, для большего количества больших статей.