1

http://students.ceid.upatras.gr/~lebenteas/Heapsort-using-Multiple-Heaps-final.pdfHeapsortで複数のヒープを使用するバリアントを見つけました。このソリューションは、各スワップの後、現在のヒープの最大値をルートに持ってくるために別のアルゴリズムを実行する従来のアルゴリズムの代わりに、他のことを行うことができることを提案しています。しかし、「他のもの」とは正確には何を意味するのか、私には理解できません。Heapsortsiftdown

たとえば、ある時点で、当分の間、ルートの存在を「忘れる」と彼らは言います。これは、現在、ヒープの最上位要素と最後の要素の交換を停止していることを意味します。ただし、いくつかの行の直後に、これまでのところ、2 つの要素がヒープのソートされた部分に転送されています。、スワッピングがまだ行われていないという命題に反します。また、97 ページの図では、値 1 のノードがありません。方法がわかりません。

著者が正確に何を伝えようとしているのか、そしてそれがどれほど価値があるのか​​、誰か教えてもらえますか?

4

1 に答える 1

1

(あなたが尋ねた行はセクション 2.3 にあるので、セクション 2.3 で提案されているヒープソートのバリエーションについて説明します:)

root の存在を「忘れる」と作者が言うとき、これは彼らが最上位の要素の交換を失速させているという意味ではありません。スワップは完了しますが、ヒープの再構築が一時的に遅れます。最上位の要素をルート位置にスワップした後、2 つのサブヒープのルートを比較し、いずれかを次に上位の要素とスワップします。次に、 (1 回ではなく) 2 回のスワップを行った後、ヒープを再構築します。

次に、セクション 3 と 4 でこのアイデアをさらに一歩進め、複数のヒープを使用するヒープソートの別の変形を提案します。

配列に複数のヒープを保持するにはどうすればよいですか? (具体的にするために、2 つのヒープについて話しましょう。) では、単一のヒープをどのように保持するのでしょうか。ルートはインデックス 0 になり、その子は 1 と 2 になり、左側のサブヒープの子は 3 と 4 になります。

2 つのヒープを配列にまとめるには、2 つのルートを 0 と 1 に保持します。最初のルートの子は 2 と 3 に配置され、次に 2 番目のルートの子は 4 と 5 に配置されます...このような配置では、インデックスに対して単純な算術演算を実行することで、ツリーを上下にナビゲートすることは引き続き可能です。

標準のヒープソートは 2 つの手順を繰り返します。ルートを「ヒープ」領域の最後の要素と交換してsiftDownから、ヒープを再構築します。このsiftDownヒープソートは、次の 3 つの手順を繰り返します。2 つのルートを比較してどちらが大きいかを確認し、そのルートを「ヒープ」領域の最後の要素と交換してから、適切なヒープを呼び出します。

これには各ステップで追加の比較が必要ですが、siftDown操作はわずかに浅いヒープで機能するため、複数の比較を節約できます。

于 2012-09-26T10:51:58.467 に答える