Matlab中的堆排序

Question

嘿伙计们。我正在尝试在 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

你的 extract-first-item 代码是错误的（你可能猜到了，因为它不起作用:-)）——看起来你只做了你需要的循环的一个步骤。您需要用堆的“最后一个”元素替换树的根（您正在这样做），然后从那里沿着树向下移动到修复堆属性的叶子（您只做了以下一步）那）。

另外，您正在堆弹出循环之外初始化“parent”；除非我完全误解你想要做什么，否则每次提取元素时你都希望将其重置为 1 。