matlab - 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 代码是错误的（您可能已经猜到了，因为它是不工作的位 :-)） - 看起来您只执行了您需要的循环的一个步骤。您需要用堆的“最后一个”元素替换树的根（您正在这样做），然后从那里沿着树向下移动到修复堆属性的叶子（您只需执行一步那）。

此外，您正在堆弹出循环之外初始化“父级”；除非我完全误解了您要执行的操作，否则每次提取元素时都希望将其重置为 1。