Opis sposobu tworzenia sterty w Pythonie

Question

Funkcja w Pythonie używa modułu heapq do zwracania na przykład liczby najczęstszych słów w pliku.

Prześledziłem przez plik heapq.py, ale mam trochę problemów ze zrozumieniem, w jaki sposób sterty są tworzone/aktualizowane w odniesieniu do słów powiedzmy.

Uważam, że najlepszym sposobem dla mnie, aby to zrozumieć, jest dowiedzieć się, jak utworzyć kupę od podstaw.

Czy ktoś może podać pseudokod do utworzenia sterty, która reprezentowałaby liczbę słów?

Answer 1

Jest to nieco zmodyfikowana wersja kodu znaleźć tutaj: 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 

Wyjście

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

można wizualizować program tutaj http://goo.gl/2a9Bh

Answer 2

w Pythonie 2.x oraz 3.x, stosy są obsługiwane przez importowalną bibliotekę heapq. Dostarcza wiele funkcji do pracy ze strukturą danych sterty modelowaną na liście Pythona. Przykład:

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

Możesz dowiedzieć się więcej o funkcjach Heap: heappush, heappop, heappushpop, heapify, heapreplace w heap python docs.

Answer 3

Oto inny wariant na podstawie Sedgewick

sterta jest reprezentowany wewnętrznie w tablicy gdzie jeśli węzeł jest K, to jest dzieci są 2 * K i 2 * k + 1. Pierwszy element tablicy nie jest używany, aby uczynić matematykę bardziej wygodną.

Aby dodać nowy element do sterty, należy dodać go do końca tablicy, a następnie wywoływać wielokrotnie, aż nowy element znajdzie swoje miejsce w stercie.

Aby usunąć root, zamień go na ostatni element w tablicy, usuń go, a następnie wywołaj sink, aż zamieniony element znajdzie swoje miejsce.

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 

Oto wizualizacji wkładki sterty wkładania 15 pierwszych liter alfabetu: [AO]