heapsort中的数组索引

Question

在阅读Jon Bentley的"Programming Pearls"第2版的第14章中,我理解堆使用基于单的数组,C中最简单的方法是声明x [n + 1]和废弃元素x [0](页面148).

在页157,Jon列出了完整的heapsort伪代码:

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

这是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开头时才有效.

是什么打动我的是,在分析部分执行用于从索引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开始的父/子关系.