コース内容#
復習 [完全二分木]#
-
-
完全二分木はデフォルトで 1 から番号付けされます
- これにより、左の子、右の子の番号が簡潔になります
- [そうでない場合] 左の子の番号は 2 * i + 1、右の子の番号は 2 * i + 2 にする必要があります
-
番号付けの性質→順序構造で保存することができ、次のノードのアドレスを保存する必要はありません
-
- 二分木→配列の変換
- レベル順で配列に保存し、各レベルのノードの保存は連続しています
- ここでは 0 番から保存されていますが、それも構いませんが、好ましくありません
-
ヒープ [優先キュー]#
本質的な考え方は優先キューですが、ヒープは完全二分木を基にしています
構造の定義#
- 構造は完全二分木と同じですが、もう 1 つの性質を維持しています👇
- 大きなヒープ：任意の三つ組において、ルートノードの値が最大です
- 小さなヒープ：任意の三つ組において、ルートノードの値が最小です
構造の操作#
すべての操作は自分自身の性質を維持する必要があります！
- 末尾に挿入【+ 調整】
- 末尾に要素を挿入し、下から上に自己調整し、ルートノードまで調整します
- 三つ組で調整し、順番に親ノードと比較し、交換するたびに止まりません、ルートノードに到達するまで続けます
- 比較する番号は実際には i と i / 2 です
- 時間の複雑さ：O (log [2] N)、つまり木の高さ
- 末尾に要素を挿入し、下から上に自己調整し、ルートノードまで調整します
- 先頭を取り出す【+ 調整】
- 最後の要素をヒープの先頭に持ってきて、上から下に自己調整し、子ノードがなくなるまで調整します
- 三つ組で調整し、順番に子ノードと比較し、交換するたびに止まりません、子ノードがなくなるまで続けます
- なぜ最後の要素をヒープの先頭に持ってくるのですか？
- なぜなら、他の位置の要素を持ってきた場合、この要素のギャップを埋めるものは誰ですか
- 比較する番号は実際には i、2 * i、2 * i + 1 です
- 時間の複雑さ：木の高さと同じです
- 最後の要素をヒープの先頭に持ってきて、上から下に自己調整し、子ノードがなくなるまで調整します
- [PS]
- 大きなヒープ：最大の要素と 2 番目に大きな要素を見つけるのが簡単です [ルートノード、第 2 層]
- 3 番目、4 番目の要素を見つけるのは簡単ではありません、層の位置を特定するのが簡単ではありません
- ❗ 上記のプロセス
- キューの末尾に要素を追加し、キューの先頭から要素を取り出す👉キューとも呼ばれる優先キュー
- キューから取り出される要素は最大値です👉優先キューとも呼ばれます
- 大きなヒープ：最大の要素と 2 番目に大きな要素を見つけるのが簡単です [ルートノード、第 2 層]
ヒープソート#
- 性質に基づいて、すべての要素を取り出すと、ソートされたシーケンスが得られます
- ⭐思考の転換：ヒープの先頭要素の取り出し操作 ==> ヒープの先頭要素とヒープの末尾要素の交換
- 【この操作を行う】
- 大きなヒープの要素をすべて取り出す👉元の配列には小さい順でソートされたシーケンスが格納されています
- [ここで、大きなヒープから特別な小さなヒープを得るため、通常は取り出された要素を元の配列の末尾に置きます]
- 時間の複雑さ：O (NlogN)
- 時間の消費は調整操作にかかりますが、各調整の時間の複雑さは O (logN) であり、N 個の要素があり、N - 1 回調整する必要があります
- 取り出し操作の時間の複雑さは O (1) です
- 時間効率は必ずしも低下しません
ヒープの構築#
【ヒープソートを使用する場合、まずヒープを維持する必要があります。つまり、通常のシーケンスでヒープを作成する必要があります。以下に 2 つのアプローチがあります】
通常のアプローチ#
または、挿入によるヒープの構築法
- 前述の末尾に挿入する調整方法に従って：下から上に
- 0 層 [デフォルトではルートノードが 0 層にある] から始めて、各層の最大調整回数を計算します：
-
- 第 i 層の要素の調整回数は i であり、第 i 層のノード数は 2 ^ i です→第 i 層の総調整回数は i * (2 ^ i) です
- 最悪のヒープ構築の時間の複雑さは O (NlogN) であり、計算過程は次のとおりです：
- 総調整回数 S = (n - 1) * 2 ^ (n + 1) + 1、過程は次のとおりです：
-
- 分数の項を相殺するために分割項を使用します
-
- 上記の n は【層数 - 1】に対応します [0 層から n 層まで、層数は n + 1 です]、総ノード数を N とすると、n ≈ log [2] N です
- ❗【層数 n→ノード数 N の変換】n ≈ log [2] N を S に代入すると、S ≈ Nlog [2] N です
- つまり、最悪の時間の複雑さは：O (NlogN) です
- 総調整回数 S = (n - 1) * 2 ^ (n + 1) + 1、過程は次のとおりです：
線形アプローチ⭐#
または、【線形構築法】
-
-
図のように
- 通常のアプローチ：下に行くほど、必要な調整回数が増え、重みが大きくなります
- ❗ では、思考を反転させて、重みの大きいものを前に持ってきて、下のノード数が多い層の重みを減らすことはできませんか
- 線形アプローチ：できます！最後から 2 番目の層から並べ替え、【上から下に】調整します
-
🆒最悪のヒープ構築の時間の複雑さは O (N) です
- 同様に、分数の項を相殺するために分割項を使用して、総調整回数 S = 2 ^ (n + 1) - 2 - n を得ます
- 層数 n をノード数 N に変換すると、S ≈ 2N - 2 - log [2] N です
- つまり、最悪の時間の複雑さは：O (N) です
-
⭐おすすめのビデオLinear Time BuildHeap——Youtube
- 通常のヒープ構築と線形ヒープ構築の 2 つのアプローチを比較し、直感的なアニメーションで示しています
コードデモ#
ヒープ [優先キュー]#
-
-
-
調整操作、巧妙な変数 ind、temp、l、r の使用
- ind が一定の条件に達すると、調整が停止します
- ind [ヒープに追加、ヒープから取り出す]、r [ヒープから取り出す] が存在するかどうかに注意してください
線形ヒープ構築法#
-
-
-
ここでは【ヒープソート】に【ヒープの構築】+【ソート】を考慮しています
- O(N) + O(NlogN) = O(NlogN)
-
ヒープ構造を定義せず、配列でヒープを模倣しています
-
33 行目：ヒープノードの番号を 1 から始めると便利なので、ここでは arr-1 は配列のインデックスを左に 1 つずらすためです
-
上から下への調整メソッドをカプセル化しました。下の図から最初に調整される位置がわかります。前述のおすすめのビデオLinear Time BuildHeap——Youtube
-
考えるポイント#
- ❌n 層のループに対応する時間の複雑さは O (N^n) ではありません。固定された思考を捨てて、本質を分析してください！
-
