Comprendre comment créer un tas en Python
collections.Count.most_common la fonction en Python utilise le heapq module pour renvoyer le nombre de la plupart des mots courants dans un fichier, par exemple.
j'ai tracé à travers la <!-Mais j'ai un peu de mal à comprendre comment un tas est créé/mis à jour en ce qui concerne les mots, disons.
donc, je pense que le meilleur moyen pour moi de le comprendre, est de trouver comment créer un tas à partir de zéro.
est-ce que quelqu'un peut fournir un pseudo pour créer un tas qui représenterait mot compte?
3 réponses
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
Sortie
['brown', 'log', 'jumped', 'over', 'fox', 'quick', 'the']
['jumped', 'fox', 'over', 'brown', 'log', 'the', 'quick']
En Python 2.X et 3.x, les tas sont pris en charge par une bibliothèque importable, heapq. Il fournit de nombreuses fonctions pour travailler avec la structure de données tas modélisée dans une liste Python. Exemple:
>>> 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
vous pouvez en savoir plus sur les fonctions de tas:heappush, heappop, heappushpop, heapify, heapreplacetas python docs.
Voici une autre variation basée sur Sedgewick
le tas est représenté en interne dans un tableau où si un noeud est à k, ses enfants sont à 2*k et 2*k + 1. Le premier élément du tableau n'est pas utilisé, pour rendre les mathématiques plus pratique.
Pour ajouter un nouvel élément au tas, vous l'ajouter à la fin du tableau et ensuite appeler nager à plusieurs reprises jusqu'à ce que le nouvel élément trouve sa place dans le tas.
pour supprimer la racine, vous l'échangez avec le dernier élément du tableau, supprimez-le et appelez l'évier jusqu'à ce que l'élément échangé trouve sa place.
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
Voici une visualisation de l'encart de tas, insérant les 15 premières lettres de l'alphabet: [A-o]
