6

しばらく前に、d-ary max-heap (各ノードが最大 d 個の子を持つヒープ) を使用して n 個の数値の配列をソートする ac プログラムを作成する割り当てが与えられました。プログラムは、2 から配列のサイズまでの値である d の値を入力するようユーザーに要求する必要がありました。プログラムをチェックしているときに、誤って d の値として 1 を入力してしまい、アルゴリズムが 1-ary ヒープを使用して配列を正しくソートすることに成功しましたが、d の通常の値よりも多くの時間がかかりました。

そんなことがあるものか？1-ary ヒープは単なるリストのようなヒープではなく、すべてのノードには 1 つの子しかありません。この並べ替えがどのように発生するかを説明できる人はいますか?

4

1 に答える 1

8

1-ary ヒープは依然としてヒープであり、ヒープ ソートに必要なすべての不変条件を満たします。

  • 最初の要素は最大の要素です。
  • パーコレーションは、上部要素を正しい位置に移動できます。

実際には、1-ary ヒープは、すべてのノードが 1 つの子を持つツリーです。これは、単方向リンク リストとも呼ばれます。また、ヒープ制約は、子ノードが親ノードよりも小さいことを意味します。つまり、簡単に言えば、1-ary ヒープは、逆順にソートされた単一リンク リストです。

最初にヒープを構築することは、挿入ソート (すべての項目を 1 つずつリストにパーコレートする) と同等です。これが完了すると、最初の要素を削除すると、すべての要素の中で最大の要素が生成され、その後のパーコレーションにより、リスト内のすべての項目が 1 レベル上に移動します。

于 2010-12-12T11:53:40.830 に答える