日常記録:「アルゴリズム導論」学習ノートの3-スタックソート

「アルゴリズム導論」の6章では,select sortとinsert sortアルゴリズムの利点を組み合わせたスタックソート(heapsort)について述べ,このデータ構造は完全なツリーに類似している.各ノードの親ノードと子ノードは、ノードの下付きスケールに基づいて、配列内のノード格納要素の下付きスケールを計算できます.ここで筆者が用いたデータ構造の理解について述べると,我々が利用する二叉堆データ構造は実際にこのような構造データを構築するのではなく,配列に基づいて抽象化されたものであり,各ノードに対する操作は,実際には元の配列に対する操作であり,本ではノードの下付き文字と配列の下付き文字を区別せず,デフォルト配列の1つの要素を1としている.私たちの普段の0ではないので、この学習ノートでは、筆者が自分の理解でいくつかの内容を変更し、修正した部分に間違いがあれば、批判して指摘してほしい.
配列の下付き文字をn,ノードの下付き文字をiで表す.ノードと配列の下付き文字の対応関係は次のとおりです.

      i    ，        ：n =  i - 1；
          ： n = 2 * i - 1;
          ： n = 2 * i;
           ： n = i / 2;

下から大きなシーケンスを得るには、最大スタック構造、すなわちノードの要素値が最大であり、その特徴はA[i/2]>A[i-1]であり、親ノードの数値は子ノードの数値よりも永遠に大きく、MAX_HEAPIFYはスタックの特性を保証し、その偽コードは以下の通りである.

l = LEFT(i)
r = RIGHT(i)
n = i - 1
largest = n
if  A[l] > A[n]
  largest = l
if r <= heap_size(A) and A[r] > A[largest]
  largest = r
if largest != n
  A[i] <-> A[largest]
  if (largest < heapsize(A) / 2
    MAX_HEAPIFY(A, largest + 1)

のノードは最大の要素値なので、下から上へMAX_を使います.HEAPIFYは配列を最大のスタックに変更し、プロセスBUILD_MAX_HEAPはループごとにiノードでMAX_を呼び出すHEAPIFY、その偽コードは以下の通りである.

heap_size(A) = length(A)
for i : length/2 to 1
  MAX_HEAPIFY(A, i)

は、最も大きな特徴であり、ルートノードは配列内の要素の最大値であり、ルートノードを配列の最後のビットから順に前に格納するだけで、A[0]とA[n]の値を交換し、heap_sizeは毎回1を減らしてMAX_を使いますHEAPIFYは最も多くの特性を維持し、最終的な答えを得ることができます.このプロセスは擬似コードで表されます.

for n : length(A)-1 to 1
  A[n] <-> A[0]
  heap_size(A)--
  if (i != 1)
    MAX_HEAPIFY(A, 1)

所与のインスタンスは、以下のようにC++でheapsortを実装する.
コードは「アルゴリズム導論」の偽コード構想を参考にし、他の人の実現過程を参考にしていない.その中には筆者に無視されている論理的な誤りがあるかもしれないが、批判を指摘したい.