Блог

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

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

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

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

В 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 в документах heap python .

Вот еще один вариант, основанный на Sedgewick

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

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

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

 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]

это немного измененная версия кода, найденного здесь : 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

Ваша путаница может быть вызвана тем фактом, что модуль Python heapq не определяет кучу как тип данных (класс) со своими собственными методами (например, как в a deque или a list ). Вместо этого он предоставляет функции, которые вы можете запускать на Python list .

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

Давайте посмотрим на это на примере. Начиная с простого списка Python:

 >>> my_list = [2, -1, 4, 10, 0, -20]
  

Чтобы создать кучу с heapq помощью from my_list , нам просто нужно вызвать heapify , который просто переупорядочивает элементы списка, чтобы сформировать минимальную кучу:

 >>> import heapq
>>> # NOTE: This returns NoneType:
>>> heapq.heapify(my_list)
  

Обратите внимание, что вы все еще можете получить доступ к списку, лежащему в основе кучи, поскольку все heapify , что было сделано, это изменить значение, на которое ссылается my_list :

 >>> my_list
[-20, -1, 2, 10, 0, 4]
  

Выталкивание элементов из кучи, удерживаемой my_list :

 >>> [heapq.heappop(my_list) for x in range(len(my_list))]
[-20, -1, 0, 2, 4, 10]