开发者

heapsort in Matlab

Hey guys. Im trying to write an algorithm for heapsort in Matlab. Its not working. The heap is constructing fine. Filling the sorted vector is not working. Here is the code and thank you!

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);
    w开发者_如何学JAVAhile 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


Your extract-first-item code is wrong (you probably guessed that since it's the bit that isn't working :-)) -- it looks like you're doing only one step of the loop you need. You need to replace the root of the tree with the "last" element of the heap (you're doing that) and then travel down the tree from there to the leaf fixing up the heap property (you're only doing one step of that).

Also, you're initializing "parent" outside the heap-popping loop; unless I'm entirely misunderstanding what you're trying to do, you want to be resetting it to 1 every time you extract an element.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜