кучи в 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

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

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