1

やあみんな。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
4

1 に答える 1

0

あなたのextract-first-itemコードは間違っています（おそらくそれは機能していないビットなので:-)）-必要なループの1つのステップだけを実行しているように見えます。ツリーのルートをヒープの「最後の」要素に置き換えて（これを実行します）、ツリーを下に移動して、ヒーププロパティを修正するリーフに移動する必要があります（1つのステップのみを実行します）。それ）。

また、ヒープポップループの外側で「親」を初期化しています。私があなたがやろうとしていることを完全に誤解していない限り、要素を抽出するたびにそれを1にリセットしたいと思うでしょう。

于 2011-02-05T23:40:07.107 に答える