Y a-t-il un problème avec cet algorithme?

J'ai un problème avec cet algorithme pour Heap-SortY a-t-il un problème avec cet algorithme?

Heap_Sort(A) 
    Build_Heap(A) 
    for i<--n down to 2 
    swap (A[1],A[n]) 
    n<--n-1 
    MaxHeapify(A,1)

Je pense qu'au lieu de cet algorithme, nous devrions écrire:

Heap_Sort(A) 
    Build_Heap(A) 
    for i<-- n down to 1 
    Delete_Max(A)

Source

2010-07-14 user355002

Quelle est la nature exacte de votre problème avec heapsort? Pourquoi pensez-vous que vous devriez supprimer le maximum? – mcandre

Je vais stocker tous ces éléments supprimés dans un tableau qui sera trié – user355002

Si vous déplacez l'élément max à l'arrière de votre tableau de tas et puis supprimez-le, vous ne serez pas laissé avec quoi que ce soit dans votre tableau lorsque vous avez terminé. Ainsi, votre algorithme, qui supprime le maximum, ne va pas aboutir à un tableau trié de vos éléments d'origine.

mise à jour basée sur modifier OP:

Vous pouvez le faire de cette façon. La première méthode, cependant, vous permet de trier en place. Votre méthode nécessite O (N) stockage supplémentaire.

Une autre Edit:

Il est difficile de voir exactement quelles hypothèses vous faites sur le premier algorithme, mais comme je pense à mon commentaire fait ci-dessous, il semble probable que MaxHeapify(A,1) devrait probablement MaxHeapify(A, n). Vous passerez généralement un tableau et sa taille, ou dans ce cas, le nombre d'éléments que vous voulez organiser en tas. Cela peut être inutile si vous supposez que n est une variable globale.

Source

2010-07-14 15:35:33 andand

désolé j'ai édité mon message! J'ai eu une erreur – user355002

si je permets un [1] et un [n] alors qu'est-ce qui va arriver à la valeur max? – user355002

@ martin1234: Le swap permet à l'algorithme de trier en place. Le n <-n-1 dit simplement que la taille du tas a été réduite de sorte que l'élément max que vous avez trouvé ne soit pas réinséré dans le tas (c'est-à-dire qu'il diminue la taille du tas). – andand

Si vous faites une sorte en place ...

Heap_Sort(A) 
    B = Build_Heap(A) # Assuming maxheap 

    for i -> A.length to 0: 
     Remove top value from B (which is basically just A, but treated differently), 
     assuming the heap is modified to maintain partial ordering during this part 
     (as well as decreasing the noted size of the heap by 1) and add the removed 
     value to position A[i].

Fondamentalement, votre algorithme. Si vous ne le faites pas, vous pouvez simplement utiliser un minheap et faire apparaître toutes les valeurs dans un nouveau tableau.

Source

2010-07-14 15:47:18 JAB

avec votre version J'ai un problème avec votre version, je pense qu'il y a un problème – user355002

@matin: Oui, j'ai refait l'algorithme. J'ai fait quelques hypothèses quant à la façon dont le tas lui-même est censé fonctionner, cependant. – JAB

Y a-t-il un problème avec cet algorithme?

Répondre

Questions connexes