Адрес столбца:Один модуль Python в неделю
В то же время, вы также можете обратить внимание на мой публичный аккаунт WeChat.AlwaysBeta, вас ждет еще больше захватывающего контента.
heapq реализует минимальный алгоритм пирамидальной сортировки для списков Python.
Куча — это древовидная структура данных, в которой дочерние узлы и родительские узлы принадлежат отсортированному отношению. Двоичные кучи могут быть представлены с помощью списков или массивов, так что дочерние элементы элемента N расположены в 2 *N+ 1 и 2 *N+ 2-я позиция (для индексации с нуля). Такой макет позволяет переупорядочивать кучу на месте, поэтому нет необходимости перераспределять память при добавлении или удалении данных.
max-heap гарантирует, что родитель больше или равен своим дочерним элементам. min-heap требует, чтобы родитель был меньше или равен его дочернему элементу. питонheapqМодуль реализует мини-кучу.
образец данных
В примерах в этом разделе используются данныеheapq_heapdata.py.
# heapq_heapdata.py
# This data was generated with the random module.
data = [19, 9, 4, 10, 11]
Вывод кучи с использованием печатиheapq_showtree.py.
# heapq_showtree.py
import math
from io import StringIO
def show_tree(tree, total_width=36, fill=' '):
"""Pretty-print a tree."""
output = StringIO()
last_row = -1
for i, n in enumerate(tree):
if i:
row = int(math.floor(math.log(i + 1, 2)))
else:
row = 0
if row != last_row:
output.write('\n')
columns = 2 ** row
col_width = int(math.floor(total_width / columns))
output.write(str(n).center(col_width, fill))
last_row = row
print(output.getvalue())
print('-' * total_width)
print()
создать кучу
Существует два основных способа создания кучи:heappush()а такжеheapify().
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data
heap = []
print('random :', data)
print()
for n in data:
print('add {:>3}:'.format(n))
heapq.heappush(heap, n)
show_tree(heap)
# output
# random : [19, 9, 4, 10, 11]
#
# add 19:
#
# 19
# ------------------------------------
#
# add 9:
#
# 9
# 19
# ------------------------------------
#
# add 4:
#
# 4
# 19 9
# ------------------------------------
#
# add 10:
#
# 4
# 10 9
# 19
# ------------------------------------
#
# add 11:
#
# 4
# 10 9
# 19 11
# ------------------------------------
когда используешьheappush()При добавлении новых элементов порядок наложения сохраняется.
Если данные уже находятся в памяти, используйтеheapify()для более эффективной перестановки элементов в списке.
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data
print('random :', data)
heapq.heapify(data)
print('heapified :')
show_tree(data)
# output
# random : [19, 9, 4, 10, 11]
# heapified :
#
# 4
# 9 19
# 10 11
# ------------------------------------
получить доступ к содержимому кучи
Как только куча будет правильно создана, используйтеheappop()Удалите элемент с наименьшим значением.
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data
print('random :', data)
heapq.heapify(data)
print('heapified :')
show_tree(data)
print()
for i in range(2):
smallest = heapq.heappop(data)
print('pop {:>3}:'.format(smallest))
show_tree(data)
# output
# random : [19, 9, 4, 10, 11]
# heapified :
#
# 4
# 9 19
# 10 11
# ------------------------------------
#
#
# pop 4:
#
# 9
# 10 19
# 11
# ------------------------------------
#
# pop 9:
#
# 10
# 11 19
# ------------------------------------
В этом примере используйтеheapify()а такжеheappop()приводить в порядок.
Чтобы удалить существующие элементы и заменить их новыми значениями за одну операцию, используйтеheapreplace().
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data
heapq.heapify(data)
print('start:')
show_tree(data)
for n in [0, 13]:
smallest = heapq.heapreplace(data, n)
print('replace {:>2} with {:>2}:'.format(smallest, n))
show_tree(data)
# output
# start:
#
# 4
# 9 19
# 10 11
# ------------------------------------
#
# replace 4 with 0:
#
# 0
# 9 19
# 10 11
# ------------------------------------
#
# replace 0 with 13:
#
# 9
# 10 19
# 13 11
# ------------------------------------
Замещающие элементы могут поддерживать кучу фиксированного размера, например очередь заданий, отсортированных по приоритету.
экстремумы данных кучи
heapqТакже включены две функции для проверки итерируемого объекта и поиска диапазона максимальных или минимальных значений, которые он содержит.
import heapq
from heapq_heapdata import data
print('all :', data)
print('3 largest :', heapq.nlargest(3, data))
print('from sort :', list(reversed(sorted(data)[-3:])))
print('3 smallest:', heapq.nsmallest(3, data))
print('from sort :', sorted(data)[:3])
# output
# all : [19, 9, 4, 10, 11]
# 3 largest : [19, 11, 10]
# from sort : [19, 11, 10]
# 3 smallest: [4, 9, 10]
# from sort : [4, 9, 10]
использоватьnlargest()а такжеnsmallest()только дляn > 1Относительно небольшое значение допустимо, но в некоторых случаях может пригодиться.
Эффективно объединяйте отсортированные последовательности
Объединение нескольких отсортированных последовательностей в новую последовательность легко для небольших наборов данных.
list(sorted(itertools.chain(*data)))
Для больших наборов данных это займет много памяти. Вместо сортировки всей комбинированной последовательности используйтеmerge()Генерирует новую последовательность по одному.
import heapq
import random
random.seed(2016)
data = []
for i in range(4):
new_data = list(random.sample(range(1, 101), 5))
new_data.sort()
data.append(new_data)
for i, d in enumerate(data):
print('{}: {}'.format(i, d))
print('\nMerged:')
for i in heapq.merge(*data):
print(i, end=' ')
print()
# output
# 0: [33, 58, 71, 88, 95]
# 1: [10, 11, 17, 38, 91]
# 2: [13, 18, 39, 61, 63]
# 3: [20, 27, 31, 42, 45]
#
# Merged:
# 10 11 13 17 18 20 27 31 33 38 39 42 45 58 61 63 71 88 91 95
потому чтоmerge()Используя реализацию кучи, он потребляет память в зависимости от количества объединяемых элементов последовательности, а не от количества элементов во всех последовательностях.
Связанные документы: