Понимание того, как создать кучу в Python

Функция collections.Count.most_common в Python использует модуль heapq, чтобы возвращать счетчик наиболее распространенного слова в файле, например.

Я прорисовывал файл heapq.py, но у меня возникли проблемы с пониманием того, как создается или обновляется куча в отношении слов.

Итак, я считаю, что лучший способ понять это - выяснить, как создать кучу с нуля.

Может ли кто-нибудь предоставить псевдокод для создания кучи, которая будет представлять количество слов?

Ответы

Ответ 1

это немного измененная версия кода, найденного здесь: http://code.activestate.com/recipes/577086-heap-sort/

def HeapSort(A,T):
    def heapify(A):
        start = (len(A) - 2) / 2
        while start >= 0:
            siftDown(A, start, len(A) - 1)
            start -= 1

    def siftDown(A, start, end):
        root = start
        while root * 2 + 1 <= end:
            child = root * 2 + 1
            if child + 1 <= end and T.count(A[child]) < T.count(A[child + 1]):
                child += 1
            if child <= end and T.count(A[root]) < T.count(A[child]):
                A[root], A[child] = A[child], A[root]
                root = child
            else:
                return

    heapify(A)
    end = len(A) - 1
    while end > 0:
        A[end], A[0] = A[0], A[end]
        siftDown(A, 0, end - 1)
        end -= 1


if __name__ == '__main__':
    text = "the quick brown fox jumped over the the quick brown quick log log"
    heap = list(set(text.split()))
    print heap

    HeapSort(heap,text)
    print heap

Выход

['brown', 'log', 'jumped', 'over', 'fox', 'quick', 'the']
['jumped', 'fox', 'over', 'brown', 'log', 'the', 'quick']

вы можете визуализировать программу здесь http://goo.gl/2a9Bh

Ответ 2

В Python 2.X и 3.x кучи поддерживаются через импортируемую библиотеку heapq. Он предоставляет множество функций для работы с структурой данных кучи, смоделированной в списке Python. Пример:

>>> from heapq import heappush, heappop
>>> heap = []
>>> data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
>>> for item in data:
        heappush(heap, item)

>>> ordered = []
>>> while heap:
        ordered.append(heappop(heap))

>>> ordered
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> data.sort()
>>> data == ordered
True

Вы можете узнать больше о функциях кучи: heappush, heappop, heappushpop, heapify, heapreplace в кучи python docs.

Ответ 3

Здесь другой вариант, основанный на Sedgewick

Куча представлена ​​внутри массива, где, если a node находится в k, он имеет 2 * k и 2 * k + 1. Первый элемент массива не используется, чтобы сделать математику более удобно.

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

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

swim(k):
  while k > 1 and less(k/2, k):
    exch(k, k/2)
    k = k/2

sink(k):
  while 2*k <= N:
    j = 2*k
    if j < N and less(j, j+1):
      j++
    if not less(k, j):
      break
    exch(k, j)
    k = j

Здесь визуализируется вставка кучи, вставляющая первые 15 букв алфавита: [a-o]

heap insert visualization