コース内容#
復習 [完全二分木]#
-
-
完全二分木は 1 から番号付けされる
- これにより左の子、右の子の番号が簡潔になる
- [そうでなければ] 左の子の番号は 2 * i + 1、右の子の番号は 2 * i + 2
-
番号付けの性質→順序構造で保存でき、次のノードのアドレスを保存する必要がない
-
- 二分木→配列への変換
- 層順に遍歴した順序で配列に保存され、各層のノードの保存は連続している
- ここは 0 番から保存されているが、🆗でも🆒ではない
-
ヒープ [優先キュー]#
本質的な考え方は優先キューだが、ヒープは優先キューの一つの実装方法である；ヒープは完全二分木の基礎の上に維持される
構造定義#
- 構造は完全二分木と同じだが、もう一つの性質を維持する👇
- 大ヒープ：任意の三元組に対して、根ノードの値が最大
- 小ヒープ：任意の三元組に対して、根ノードの値が最小
構造操作#
すべての操作は自分の性質を維持しなければならない！
- 尾部挿入【+ 調整】
- 尾部にその要素を挿入し、下から上に調整し、最遠で根ノードまで調整する
- 三元組の中で繰り返し調整し、親ノードと比較し、交換があれば止まらず、根ノードに達するまで続ける
- 交換時には交換要素の相対的な大きさだけが変わり、全体の構造の相対的な大きさの関係は変わらない
- 比較の番号は実際には i と i / 2
- 時間計算量：O (log [2] N)、つまり木の高さ
- 尾部にその要素を挿入し、下から上に調整し、最遠で根ノードまで調整する
- 頭部ポップ【+ 調整】
- 最後の要素をヒープの頂点に持ってきて、上から下に調整し、その要素に子ノードがなくなるまで
- 三元組の中で繰り返し調整し、子ノードと比較し、交換があれば止まらず、子がなくなるまで続ける
- なぜ最後の要素をヒープの頂点に持ってくるのか？
- 他の位置の要素を取った場合、その要素の穴を誰が埋めるのか
- 比較の番号は実際には i、2 * i と 2 * i + 1
- 時間計算量：同じく木の高さ
- 最後の要素をヒープの頂点に持ってきて、上から下に調整し、その要素に子ノードがなくなるまで
- [PS]
- 大ヒープ：第 1 大と第 2 大の要素を簡単に探すことができる [根ノード、第二層の中]
- 第 3 大、第 4 大... はそれほど簡単ではなく、所在層数を特定するのが不便
- ❗ 上記のプロセス
- キューの尾に要素が入って、キューの先から要素が出る👉同じキュー
- そして出隊の要素は最値👉優先キューとも呼ばれる
- 大ヒープ：第 1 大と第 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、過程は以下の通り：
線形思考⭐#
つまり【線形ヒープ構築法】
-
-
図に示すように
- 通常の考え方：下の層に行くほど、必要な調整回数が多くなる、つまり重みが大きくなる
- ❗ では、思考を反転させて、大きな重みを前に置き、下のノード数が多い層の重みを減らすことはできるか
- 線形思考：できる！倒数第二層から始めて、【上から下に】調整する
-
🆒最悪のヒープ構築時間計算量 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 つ int サイズ左に偏移させる
-
上から下への調整方法をカプセル化し、下の図から最初に調整される位置が前の推奨動画Linear Time BuildHeap——Youtube から来ていることがわかる
-
考察点#
- ❌n 層のループに対応する時間計算量は O (N^n) であり、固定観念を捨て、本質を分析する必要がある！
-
