heapsort in Matlab

Question

Эй, ребята. Я пытаюсь написать алгоритм для heapsort в Matlab. Это не работает. Куча строится отлично. Заполнение отсортированного вектора не работает. Вот код и спасибо!

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

Ваш код приточно-первых, элемент неправильно (вы, наверное, догадались, что так как это бит, который не работает :-)) - это выглядит, как вы делаете только один шаг цикла вы необходимость. Вам нужно заменить корень дерева на «последний» элемент кучи (вы это делаете), а затем перемещаться вниз по дереву оттуда, чтобы лист фиксировал свойство кучи (вы делаете только один шаг что).

Кроме того, вы инициализируете «родительский» за пределами цикла «куча»; если я полностью не понимаю, что вы пытаетесь сделать, вы хотите сбросить его до 1 при каждом извлечении элемента.