Matlab中的堆排序 [英] heapsort in Matlab

问题描述

大家好.我试图在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);
    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

推荐答案

您的提取第一项代码是错误的(您可能已经猜到了，因为这是行不通的:-))-看起来像您仅执行您需要的循环的一个步骤.您需要用堆的"last"元素替换树的根(您正在执行此操作)，然后从那里沿着树向下移动到固定堆属性的叶子(您只需要执行以下操作之一) ).

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).

此外，您正在初始化堆弹出循环之外的父级".除非我完全误解了您要做什么，否则您希望在每次提取元素时将其重置为1.

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.

这篇关于Matlab中的堆排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！