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.
精彩评论