ヒープソートアルゴリズムの普及チュートリアル

[[121962]]

この記事の参考文献: アルゴリズム入門、第 2 版。

この記事では、ヒープソートアルゴリズムについて説明します。私の知る限り、アルゴリズムを本当に徹底的に理解するには、そのアルゴリズムの原著論文または関連文献を見つけるのが最善の方法です。

さて、このセクションを始めましょう。

1. ヒープソートアルゴリズムの基本特性

時間計算量: O(nlgn)...

// マージソートと同等

最悪の場合: O(nlgn)

空間計算量: O(1)。

不安定。

2. ヒープと***ヒープの確立

ヒープ ソート アルゴリズムを紹介するには、まずヒープの紹介から始め、次に *** ヒープを構築し、最後にヒープ ソート アルゴリズムについて説明する必要があります。

2.1. ヒープの紹介

以下に示すように、

a) はヒープであり、完全な二分木とみなすことができます。

各ヒープは配列bに対応します。ヒープの配列Aを仮定します。

配列内の要素数を表すためにlength[A]を使用し、Aに格納されているヒープ自体の要素数を表すためにheap-size[A]を使用します。

もちろん、heap-size[A]<=length[A]です。

木の根はA[1]であり、iはノードの添え字を表し、

親ノードはPARENT(i)、左の子はLEFT[i]、右の子はRIGHT[i]であり、次の関係があります。

親(i)

戻り値 |_i/2_|

左(i)

2iを返す

権利(i)

2i + 1を返す

バイナリ ヒープは、ルート ノードとその子ノードのサイズ比較に基づいて、最小ヒープと最小ヒープに分割されます。

***ヒープ：

ルート以外の各ノードiはルートノードより大きくない、つまりルートは***要素であり、最上位には

A[PARENT(i)] (ルート) ≥ A[i]、

最小ヒープ:

ルート以外の各ノードiはルートノードより小さくない、つまりルートは最小の要素であり、その頂点には

A[PARENT(i)] (ルート) ≤ A[i] 。

このセクションのヒープ ソート アルゴリズムでは、最小ヒープを使用します。最小ヒープは通常、最小優先度キューを構築するときに使用されます。

前述のように、ヒープはツリーとして見ることができるため、ヒープの高さはツリーの高さ、O(lgn) になります。

したがって、一般的な操作の場合、実行時間は O(lgn) になります。

具体的には、次のようになります。

MAX-HEAPIFY: O(lgn) これは *** ヒープを維持するための鍵です。

BUILD-MAX-HEAP: 線形時間。順序付けられていない入力配列に基づいてランダムヒープを構築します。

HEAPSORT: O(nlgn) 時間で、ヒープ ソート アルゴリズムは配列をその場でソートします。

MAX-HEAP-INSERT、HEAP-EXTRACT-MAX、HEAP-INCREASE-KEY、HEAP-MAXIMUM: O(lgn)。

ヒープは最小優先度キューとして使用できます。

2.2.1. ヒープのプロパティの維持 (O(lgn))

ヒープ特性を維持するために、MAX-HEAPIFY 操作を使用して調整を行い、この操作を再帰的に呼び出して、i をルートとするサブツリーをヒープにします。

MAX-HEAPIFY アルゴリズムは次のとおりです (コア):

 MAX-HEAPIFY(A, i)
 l ← 左(i)
 r ← 右(i)
 l ≤ heap-size[A]かつA[l] > A[i]の場合
    最大 ← l
そうでなければ最大 ← i
 r ≤ heap-size[A]かつA[r] > A[largest]の場合
    最大 ← r
最大≠iの場合
    次にA[i] <-> A[最大]を交換する
         MAX-HEAPIFY(A、最大)

上記のように、まず最初のステップを実行し、対応する配列要素 A[i]、左の子 A[LEFT(i)]、右の子 A[RIGHT(i)] の中で最大のものを見つけて、その添字を largest に格納します。 A[i]がすでに***要素である場合、プログラムは直接終了します。それ以外の場合、i の子ノードが最大要素である場合は、それを A[largest] と A[i] と交換して、i とその子が最大ヒープ プロパティを満たすことができるようにします。添字 largest が指す要素は A[i] の値となり、*** ヒープ プロパティに違反するため、largest が指す要素に対して MAX-HEAPIFY が呼び出されます。以下は、MAX-HEAPIFY プロセスのデモンストレーションです (次の図では、*** レイヤーに 4 が調整されていますが、これは 1 回限りの操作ですが、探索時間は LogN です)。

上の図から、*** ヒープの初期構築後、要素 A[i]、つまり 16 がその 2 つの子ノード 4 と 10 よりも大きく、*** ヒープ プロパティを満たしていることが簡単にわかります。したがって、i は 4 を指しており、これは左の子 14 よりも小さいため、MAX-HEAPIFY が呼び出され、4 は子 14 と位置を交換します。しかし、4 が元の位置 14 になった後、4 は右の子 8 よりも小さくなり、*** ヒープの特性に違反するため、MAX-HEAPIFY が再帰的に呼び出され、4 と 8 の位置が入れ替わります。したがって、*** ヒープ プロパティが満たされ、プログラムは終了します。

2.2.2 MAX-HEAPIFYの実行時間

MAX-HEAPIFYをノードiをルートとするサイズnのサブツリーに適用する場合、その実行時間は要素A[i]、A[LEFT(i)]、A[RIGHT(i)]の関係を調整するのにかかる時間（O(1)）に、iの子の1つをルートとするサブツリーでMAX-HEAPIFYを呼び出すのに必要な時間を加えたものとなり、ノードiのサブツリーのサイズは最大2n/3であるため、MAX-HEAPIFYの実行時間は次のようになる。

T(n)≤T(2n/3)+Θ(1)である。

この式の再帰解はT(n)=O(lgn)であることが証明できます。具体的な証明については、ここでは省略しますが、「アルゴリズム入門」の第 6 章のセクション 6.2 を参照してください。

2.3.1. ヒープの構築 (O(N))

ビルドマックスヒープ(A)

ヒープサイズ[A] ← 長さ[A]
 i ← |_length[A]/2_| から 1 まで
do MAX-HEAPIFY(A, i) //ヒープ構築。列の構築方法は？MAX-HEAPIFY(A, i) は、*** ヒープ構築のために継続的に呼び出されることがわかります。  

BUILD-MAX-HEAP は、他の各ノードに対して MAX-HEAPIFY を 1 回呼び出します。

配列A[1...n]に対応する***ヒープを作成します。 A[(|_n/2_|+1) ・・・・・ n]の要素はすべてツリーの葉です。

したがって、当然、各ノードは 1 つの要素のみを含むヒープと見なすことができます。

このプロセス BUILD-MAX-HEAP(A) の正確さについては、『アルゴリズム入門』の第 6 章のセクション 6.3 を参照してください。

次の図は、このプロセスの例です (次の図では、ヒープ プロパティに違反するすべての数値を調整するために MAX-HEAPIFY 操作が継続的に呼び出され、合計 N 回の操作が行われますが、探索時間は最終的に正確に O(N) になります)。

2.3.2. BUILD-MAX-HEAPの実行時間

MAX-HEAPPIFY の各呼び出しには O(lgn) かかり、合計で O(n) 回の呼び出しがあるため、BUILD-MAX-HEAP の単純な上限は O(nlgn) です。 『アルゴリズム入門』という本には、この時間制限は正しいものの、漸近的な意味では十分に正確ではないと書かれています。

では、より正確な時間境界にはいくつの列があるのでしょうか?

MAX-HEAPIFYはツリー内の異なる高さのノードで実行するのに異なる時間がかかり、ほとんどのノードは比較的低い高さであるため、

n 個の要素のヒープの高さは |_lgn_| (切り捨て) であり、任意の高さ h では最大で |-n/2^h+1-| (切り上げ) 個のノードがあることがわかっています。

したがって、高さ h のノードに対して MAX-HEAPIFY が作用するのにかかる時間は O(h) なので、BUILD-MAX-HEAP の上限は O(n) になります。具体的な導出過程は省略します。

3. ヒープソートアルゴリズム

いわゆるヒープソートは、ヒープ構築操作 BUILD-MAX-HEAP と最大ヒープ維持操作 MAX-HEAPIFY の 2 つのプロセスを呼び出すことです。詳細なアルゴリズムは次のとおりです。

HEAPSORT(A) //n-1回のMAX-HEAPIFY呼び出しなので、O(n*lgn)

 BUILD-MAX-HEAP(A) //*** ヒープを構築、O(n)  
 i ←長さ[A] が 2 になるまで
A[1] <-> A[i]を交換する
      ヒープサイズ[A] ← ヒープサイズ[A] - 1
      MAX-HEAPIFY(A, 1) // ヒープのプロパティを維持する、O (lgn)  

上記のように、これはヒープソートアルゴリズムの完全な記述です。次に、上記のヒープ ソート アルゴリズムにおける 2 つのヒープ構築および維持操作を投稿します。

 BUILD-MAX-HEAP(A) //ヒープを構築する 
  ヒープサイズ[A] ← 長さ[A]
 i ← |_length[A]/2_| から 1 まで
MAX-HEAPIFY(A, i)を実行する
MAX-HEAPIFY(A, i) //***ヒープを保持 
 l ← 左(i)
 r ← 右(i)
 l ≤ heap-size[A]かつA[l] > A[i]の場合
    最大 ← l
そうでなければ最大 ← i
 r ≤ heap-size[A]かつA[r] > A[largest]の場合
    最大 ← r
最大≠iの場合
    次にA[i] <-> A[最大]を交換する
         MAX-HEAPIFY(A、最大)

以下は、ヒープ ソート アルゴリズムのデモンストレーションです (最上位の要素と最後の要素を常に交換し、次に MAX-HEAPIFY を呼び出してヒープのプロパティを維持し、大きいものから小さいものまで 1 つずつヒープ内のすべての要素をクリアして、順序付けられたシーケンスを形成します。これがヒープ ソートの全体のプロセスです)。

上図では、a->b、b->c、... の間に、最上位の最大要素と最小要素を交換した後、MAX-HEAPIFY を呼び出すプロセスがあります。この MAX-HEAPIFY の実行時間は O(lgn) であることがわかっており、ヒープソートプロセス全体を完了するには、合計 O(n) 回のこのような MAX-HEAPIFY 操作が必要です。したがって、ヒープソートアルゴリズムの実行時間は O (n*lgn) です。

補足: ヒープは一種のツリー、バイナリ ツリーなどと考えてください。したがって、ヒープを使用してデータを検索および削除する場合の時間計算量は O (logN) です。 では、それはどのような二分木なのでしょうか? 最小ヒープと最小ヒープに分かれた特殊な二分木です。 *** 山は上部が大きく、下部が小さいです。最小のヒープには、小さな上部と大きな下部があります。

著者: 7月