c - 堆排序中的数组索引

Question

在阅读 Jon Bentley 的“Programming Pearls”第 2 版第 14 章时，我了解到堆使用基于 1 的数组，而 C 中最简单的方法是声明 x[n+1] 并浪费元素 x[0 ](第 148 页)。

在第 157 页，Jon 列出了完整的堆排序伪代码:

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

Here是C中的实现。但是，数组索引从0开始，而不是1。

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 开头时才成立。

令我印象深刻的是 implementation 中的分析部分使用从索引1开始的数组，而实现部分使用从索引0开始的数组并且没有浪费第一个元素。

我在这里遗漏了什么吗？

已编辑在 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 .万岁!

Answer 1

堆元素可以从索引 0 或索引 1 开始存储，使用哪个由您决定。

如果根元素位于索引 1，则父索引和子索引之间的数学关系很简单，如上所示，因此许多书籍都选择以这种方式进行教学。

如果根在索引 0 处，您将得到这些关系:

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

只要您始终如一，选择哪个并不重要。

您显示的 C 代码对我来说似乎不正确。它从数组索引 0 开始，但使用适合从索引 1 开始的父/子关系。