8

Jon Bentley の「Programming Pearls」第 2 版の第 14 章を読んで、ヒープは 1 ベースの配列を使用し、C で最も簡単な方法は x[n+1] を宣言して要素 x[0] を破棄することだと理解しています (page 148)。

157 ページで、Jon は完全なヒープソート擬似コードをリストしました。

for i = [2, n]
    siftup(i)
for (i = n; i >= 2; i--)
    swap(1, i)
    siftdown(i - 1)

これは C での実装です。ただし、配列のインデックスは 1 ではなく 0 から始まります。

void heapSort(int numbers[], int array_size)
{
  int i, temp;

  // Qiang: shouldn't the stop-condition be i >= 1?
  for (i = (array_size / 2)-1; i >= 0; i--)
    siftDown(numbers, i, array_size);

  for (i = array_size-1; i >= 1; i--)
  {
    // Qiang: shouldn't the swap be done with numbmers[1], instead of numbers[0]?
    temp = numbers[0];
    numbers[0] = numbers[i];
    numbers[i] = temp;
    siftDown(numbers, 0, i-1);
  }
}

void siftDown(int numbers[], int root, int bottom)
{
  int done, maxChild, temp;

  done = 0;
  while ((root*2 <= bottom) && (!done))
  {
    if (root*2 == bottom)
      maxChild = root * 2;
    else if (numbers[root * 2] > numbers[root * 2 + 1])
      maxChild = root * 2;
    else
      maxChild = root * 2 + 1;

    if (numbers[root] < numbers[maxChild])
    {
      temp = numbers[root];
      numbers[root] = numbers[maxChild];
      numbers[maxChild] = temp;
      root = maxChild;
    }
    else
      done = 1;
  }
}

私の心配は、配列がインデックス 0 で始まる場合、次のプロパティが保持されないことです (Jon の本の 148 ページに書かれているように)。

leftchild(i) = 2*i
rightchild(i) = 2*i+1
parent(i) = i/2

ここのプロパティは、i が 1 で始まる場合にのみ保持されるように見えます。

印象的なのは、実装の分析部分ではインデックス 1 で始まる配列が使用されていたのに対し、実装部分ではインデックス 0 で始まる配列が使用され、最初の要素が無駄になっていないことです。

ここで何か不足していますか？

Edited interjay の助けを借りて、元の実装に含まれていたエラーを認識しました。これは、{66,4,23,4,78,6,44,11,22,1,99} のテスト入力配列で表示できます。

siftDown()親のインデックスとその子のインデックスの関係を調整するために、元の関数を少し変更しました。

void siftDown(int numbers[], int root, int bottom)
{
  int done, maxChild, temp;

  done = 0;
  while ((root*2 + 1 <= bottom) && (!done))
  {
    if (root*2 + 1 == bottom ||
        numbers[root * 2 + 1] > numbers[root * 2 + 2])
      maxChild = root * 2 + 1;
    else
      maxChild = root * 2 + 2;

    if (numbers[root] < numbers[maxChild])
    {
      temp = numbers[root];
      numbers[root] = numbers[maxChild];
      numbers[maxChild] = temp;
      root = maxChild;
    }
    else
      done = 1;
  }
}

クレジットは interjay に送られます:-)

あとがき: wikibooksとalgorithmistの実装では同じエラーが表示されないようです。万歳！

4

3 に答える 3

12

ヒープ要素は、インデックス 0 またはインデックス 1 から格納できます。どちらを使用するかはユーザー次第です。

ルート要素がインデックス 1 にある場合、上で示したように、親インデックスと子インデックスの間の数学的関係は単純です。そのため、多くの本がそのように教えることを選択しています。

ルートがインデックス 0 にある場合、代わりに次の関係が得られます。

leftchild(i) = 2*i+1
rightchild(i) = 2*i+2
parent(i) = (i-1) / 2

一貫性がある限り、どちらを選んでも構いません。

あなたが示した C コードは、私には正しくないようです。配列インデックス 0 から始まりますが、インデックス 1 から始まるのに適した親子関係を使用します。

于 2012-10-22T13:25:16.867 に答える
2

heapsort の再利用可能な実装では、ユーザーが通常の (0 ベースの) 配列を使用できるように、ルート インデックス 0 から開始する必要があります。ヒープソート関数を使用できるようにするためだけに、ユーザーに追加のメンバーを割り当ててインデックス 1 で配列を開始するよう要求したくないでしょう。@interjay が示す変更された親子計算を使用する必要があります。

于 2012-10-22T13:45:48.410 に答える