Рубрики
Без рубрики

heapq – алгоритм сортировки кучи

Автор оригинала: Doug Hellmann.

Цель:

Heapq реализует алгоритм сортировки min-heap, подходящий для использования с Списки Python.

Куча – это древовидная структура данных, в которой дочерние узлы имеют отношение порядка сортировки с родителями. Двоичные кучи могут быть представлены с помощью списка или массива, организованного так, чтобы дочерние элементы элемента N находились в позициях 2 * N + 1 и 2 * N + 2 (для индексов с нуля). Этот макет позволяет переупорядочивать кучи на месте, поэтому нет необходимости перераспределять столько памяти при добавлении или удалении элементов.

Максимальная куча гарантирует, что родитель больше или равен обоим его дочерним элементам. Минимальная куча требует, чтобы родитель был меньше или равен его дочерним элементам. Модуль Python 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_width36, 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 () .

heapq_heappush.py

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)

Когда используется heappush () , порядок сортировки элементов в куче сохраняется по мере добавления новых элементов из источника данных.

$ python3 heapq_heappush.py

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
------------------------------------

Если данные уже находятся в памяти, более эффективно использовать heapify () для изменения порядка элементов списка на месте.

heapq_heapify.py

import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data

print('random    :', data)
heapq.heapify(data)
print('heapified :')
show_tree(data)

Результат построения списка в порядке кучи по одному элементу за раз такой же, как при построении неупорядоченного списка с последующим вызовом heapify () .

$ python3 heapq_heapify.py

random    : [19, 9, 4, 10, 11]
heapified :

                 4
        9                 19
    10       11
------------------------------------

Доступ к содержимому кучи

Как только куча будет правильно организована, используйте heappop () , чтобы удалить элемент с наименьшим значением.

heapq_heappop.py

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)

В этом примере, адаптированном из документации stdlib, используются heapify () и heappop () .

$ python3 heapq_heappop.py

random    : [19, 9, 4, 10, 11]
heapified :

                 4
        9                 19
    10       11
------------------------------------


pop      4:

                 9
        10                19
    11
------------------------------------

pop      9:

                 10
        11                19
------------------------------------

Чтобы удалить существующие элементы и заменить их новыми значениями за одну операцию, используйте heapreplace () .

heapq_heapreplace.py

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)

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

$ python3 heapq_heapreplace.py

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 также включает две функции для проверки итерации и поиска диапазона

heapq_extremes.py

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])

Использование nlargest () и nsmallest () эффективно только для относительно небольших значений n 

$ python3 heapq_extremes.py

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]

Эффективное слияние отсортированных последовательностей

Объединение нескольких отсортированных последовательностей в одну новую последовательность легко для небольших данных

list(sorted(itertools.chain(*data)))

Для больших наборов данных этот метод может использовать значительный объем памяти. Вместо сортировки всей объединенной последовательности merge () использует кучу для создания новой последовательности по одному элементу за раз, определяя следующий элемент с помощью

heapq_merge.py

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()

Поскольку реализация merge () использует кучу, она потребляет память в зависимости от количества объединяемых последовательностей, а не количества элементов в

$ python3 heapq_merge.py

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

Смотрите также

Читайте ещё по теме: