1-aryヒープソート？

Question

私たちは、d-ary max-heap（各ノードが最大d個の子を持つヒープ）を使ってn個の数値の配列をソートするcプログラムを書くという割り当てを与えられました。プログラムは、ユーザーにdの値、2と配列のサイズの間の値を入力するように要求する必要がありました。私は自分のプログラムをチェックしていたのですが、誤ってdの値として1を入力しました。そして、何らかの形でアルゴリズムは1-aヒープを使って配列を正しくソートすることに成功しました。

どうすれば可能ですか？ 1-aryヒープはヒープでもリストのようなものではなく、すべてのノードには1つの子しかありません。どのようにこの並べ替えが起こることができるか誰も説明できますか？

Answer 1

1進ヒープは依然としてヒープであり、そして満足ヒープソートによって必要とされるすべての不変量：

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

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

最初にヒープを作成することは、挿入ソート（すべての項目を1つずつリストにペルコレートする）と同じです。これが完了すると、最初の要素を削除するとすべての要素が最大になり、その後のパーコレーションによってリスト内のすべての項目が1つ上のレベルに移動します。