Javaでのヒープソートアルゴリズムの解析例

この記事では主に Java ヒープ ソート アルゴリズムの関連コードを詳しく紹介します。興味のある方は参考にしてください。

「ヒープ」の概念と操作を理解します。ヒープソートを迅速に習得するのに役立ちます。

ヒープの概念

ヒープは特別な完全なバイナリツリーです。完全なバイナリ ツリー内のすべてのノードの値がその子ノードよりも小さくない場合、それはラージ ルート ヒープ (またはラージ トップ ヒープ) と呼ばれます。小さなルート ヒープ (または小さなトップ ヒープ)。

配列 (ルート ノードは添字 0 に格納されます) では、次の式を簡単に取得できます (これら 2 つの式は非常に重要です):

1. 添字 i を持つノード、親ノードの座標は次のとおりです。 (i- 1)/2;

2. 添え字が i のノードの場合、左側の子ノードの座標は 2*i+1 であり、右側の子ノードは 2*i+2 です。

ヒープの作成とメンテナンス

ヒープはさまざまな操作をサポートできますが、ここでは次の 2 つの問題だけを考慮します。

2. ヒープの先頭要素を削除した後、配列を新しいヒープに調整するにはどうすればよいですか?

まず 2 番目の質問を見てみましょう。すでに大きな根の山が準備できていると仮定します。これでルート要素は削除されましたが、他の要素は移動していません。何が起こるかを考えてください。ルート要素は空ですが、他の要素は依然としてヒープの性質を維持しています。最後の要素 (コード名 A) をルート要素の位置に移動できます。特殊な場合ではない場合、ヒープの性質は破壊されます。しかし、これは単に A がその子の 1 つよりも小さいためです。したがって、A とこのサブ要素の位置を交換できます。 A がそのすべてのサブ要素よりも大きい場合はヒープが調整され、それ以外の場合は上記のプロセスが繰り返され、適切な位置に到達するまで A 要素がツリー構造内に「沈み込み」続け、配列がヒープを取り戻します。プロパティ。上記のプロセスは一般に「スクリーニング」と呼ばれますが、その方向性は明らかにトップダウンです。

要素を削除する場合も同様であり、新しい要素を挿入する場合も同様です。違いは、新しい要素を最後に配置してからその親ノードと比較すること、つまりボトムアップ フィルタリングであることです。

では、最初の問題を解決するにはどうすればよいでしょうか?

私が読んだデータ構造の本の多くは、最初の非リーフノードからルート要素がフィルタリングされるまでフィルタダウンします。この方法は「スクリーニング方法」と呼ばれ、n/2 個の要素をスクリーニングするループが必要です。

しかし、「何もないところから何かを生み出す」という考え方からも学ぶことができます。最初の要素をヒープとして扱い、そこに新しい要素を追加し続けることができます。この方法は「挿入方法」と呼ばれ、ループ内に (n-1) 個の要素を挿入する必要があります。

スクリーニング方法と挿入方法が異なるため、同じデータに対して作成されるヒープは通常異なります。

ヒープについて一般的に理解したら、ヒープのソートは当然のことです。

アルゴリズムの概要/アイデア

昇順シーケンスが必要ですが、どうすればよいですか?最小ヒープを構築して、毎回ルート要素を出力できます。ただし、この方法には追加のスペースが必要です (そうしないと、多数の要素が移動され、複雑さが O(n^2) まで上昇します)。その場で並べ替える必要がある場合 (つまり、O(n) 空間の複雑さが許可されない場合) はどうすればよいでしょうか?

方法はあります。最大のヒープを構築し、それを逆方向に出力し、最後の位置で最大値を出力し、最後の位置で 2 番目に大きい値を出力します。毎回出力される最大の要素によって最初のスペースが解放されるため、このような要素には追加のスペースは必要ありません。なかなかいいアイデアですね。

りー

以上がJavaでのヒープソートアルゴリズムの解析例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。