heapsort à Matlab

Question

Salut les gars. Im essayant d'écrire un algorithme pour heapsort dans Matlab. Ça ne fonctionne pas. Le tas construit bien. Le remplissage du vecteur trié ne fonctionne pas. Voici le code et merci!

function [xs,h]= heap(x) 
N = length(x); 
h = zeros(1,N); 
N_h = 0; 
for i=1:N 
    N_h = N_h +1; 
    child = N_h; 
    h(child) = x(i); 
    while child>1 
     parent = floor(child/2); 
     if h(child)>h(parent) 
      tmp = h(parent); 
      h(parent) = h(child); 
      h(child) = tmp; 
      child = parent; 
     else 
      break 
     end 
    end 

end 
xs = zeros(1,N); 
    parent = 1; 

for i = N:-1:1 
    xs(i) = h(1); 
    h(1) = h(i); 

    child1 = 2*parent; 
    child2= 2*parent+1; 

    if child1 <= i-1 


     if h(child1)>h(child2) 
      cchild = child1; 
     else 
      cchild = child2; 
     end 

     if h(parent) < h(cchild) 
      tmp = h(parent); 
      h(parent) = h(child); 
      h(child) = tmp; 
      parent = child; 
     else 
      break 
     end 

    end 

end 

Answer 1

Votre code extrait du premier article est erroné (vous avez probablement deviné que puisqu'il est le bit qui ne fonctionne pas :-)) - il semble que vous faites une seule étape de la boucle vous avoir besoin. Vous devez remplacer la racine de l'arbre par le "dernier" élément du tas (vous le faites), puis descendre de l'arbre jusqu'à la feuille fixant la propriété tas (vous faites seulement un pas de cette). En outre, vous initialisez "parent" en dehors de la boucle de saut de tas; À moins que je ne comprenne entièrement ce que vous essayez de faire, vous voulez le réinitialiser à chaque fois que vous extrayez un élément.