Heap Sort: comment trier?
Je suis en train de mettre en œuvre des Tas de Tri en Python, mais je n'arrive pas à obtenir ce droit. J'ai essayé de mettre en œuvre cette le pseudo-codemais mon code ne permet pas de trier! Il vient de eipd en effet ridicule. Je suis enclin à penser que le problème vient de cette ligne:
swap de la racine(valeur maximale) du segment de mémoire avec le dernier élément de la pile
Comment puis-je obtenir le maximum de valeur?
C'est ce que j'ai:
def my_heap_sort(sqc):
def heapify(count):
start = (count-2)/2
while start >= 0:
sift_down(start, count-1)
start -= 1
def swap(i, j):
sqc[i], sqc[j] = sqc[j], sqc[i]
def sift_down(start, end):
root = start
while (root * 2 + 1) <= end:
child = root * 2 + 1
temp = root
if sqc[temp] < sqc[child]:
temp = child+1
if temp != root:
swap(root, temp)
root = temp
else:
return
count = len(sqc)
heapify(count)
end = count-1
while end > 0:
swap(end, 0)
end -= 1
sift_down(0, end) Et j'ai trouvé un exemple avec presque le même problème:
def heap_sort_example(a):
def heapify(a):
start = (len(a) - 2) / 2
start -= 1
def sift_down(a, start, end):
root = start
while root * 2 + 1 <= end:
child = root * 2 + 1
if child + 1 <= end and a[child] < a[child+1]:
child += 1
if child <= end and a[root] < 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]
sift_down(a, 0, end-1)
end -= 1 Les résultats sont différents, mais les deux sont ridicules:
>>> my_heap_sort(sqc)
[2, 7, 1, -2, 56, 5, 3]
>>> heap_sort_example(sqc)
[-2, 1, 7, 2, 56, 5, 3]source d'informationauteur I159 | 2012-12-20
Vous devez vous connecter pour publier un commentaire.
Comment puis-je obtenir le maximum de valeur? Vous n'avez pas besoin de "get". La racine est exactement le maximum, c'est une propriété définie d'un segment.
Si vous vous sentez difficile de comprendre tas de tri, ce chapitre sera extrêmement utile.
J'ai réécrit votre code:
Il donne:
Si vous avez push et pop, ou à l'aide intégrée dans heapq lib, essayez de solution documentée:
tri de la sélection est une procédure relativement simple algorithme de tri:
parcourir un tableau, extrait de la durée minimum des n premiers éléments , puis d'en extraire min de la prochaine n-1 éléments ......
Maintenant, ce serait O(n^2) l'algorithme.
Puisque vous êtes toujours à l'extraction d'une min, vous devriez penser à utiliser un minimum de Tas. il extrait un min en O(log n) fois. l'extraction de la min n fois conduit à O(n*log n).
donc, pour des tas de tri, il suffit de construire un segment (heapify O(n)) et la traverse de la matrice et de l'extrait de la min n fois.
vous pouvez utiliser le python tas pour construire un segment ou créer votre propre.
Je trouve que les différentes implémentations de heapify, le "cœur" des tas de tri ne sont pas claires sur les internetz. Voici mon humble tentative pour aider la communauté par l'ajout d'une simple mais clair exemple de "heapify". J'ai utiliser des vecteurs pour éviter la confusion supplémentaire de la matrice de manipulation.
Cette méthode heapifies 1 cellule de la matrice.
Pour heapify l'ensemble de la baie vous avez besoin d'une boucle,
exécuter à partir de milieu de tableau, se déplaçant vers le début.
Le vecteur renvoyé DOIT être le même que celui que nous envoyons dans la prochaine itération,
sinon c'est un gâchis.
par exemple:
Je l'ai trouvé et près compris comment cela fonctionne:
edit:
Cette mise en œuvre est rédigé sur la base de ma propre compréhension de l'algorithme. Il est plus long, mais pour moi, cet algorithme est beaucoup plus claire dans cette mise en œuvre. Long de nommage est de l'aide lorsque vous avez besoin de comprendre l'algorithme, alors je l'ai laissé intacts tous les noms longs.
edit:
Et version optimisée:
Tas de tri exemple avec l'exemple du comment d'abord construire un tas