C 语言中的堆化问题

Question

我有一个反向排序的堆。我正在尝试构建最大堆：

我有代码：

    int main(int argc, char *argv[])
{
int heapArray[] = {0, 1, 2, 3, 4, 5, 6 , 7, 8 ,9 ,10 , 11, 12, 13 ,14 ,15};
int n = sizeof(heapArray)/sizeof(int);

printTree(heapArray, n);
buildHeap(heapArray, n);
printTree(heapArray, n);
}

void buildHeap(int array[], int n)
{
printf("buildHeap\n");
int i = (n-1)/2;
while(i > 0) heapify(array, n, i--);
}

void heapify(int array[], int n,  int i)
{
printf("heapify [%i] = %i\n", i, array[i]);
int childLeft = 0, childRight = 0;
int largest = i;
// printf("largest init: %i\n", largest);
if(array[2*i]) childLeft = 2*i; 
if(array[2*i + 1]) childRight = 2*i + 1;
printf("child left [%i] = %i  child right [%i] = %i\n", childLeft, array[childLeft], childRight, array[childRight]);
if(array[childLeft] > array[i]) largest = childLeft;
// printf("largest after cL compare: %i\n", array[largest]);
if(array[childRight] > array[largest]) largest = childRight;
// printf("largest after cR compare: %i\n", array[largest]);
if(largest != i)
{
    swap(array, i,largest);
    heapify(array, n, i);
}


}

void swap(int array[], int indexA, int indexB)
{
printf("swap [%i] %i with [%i] %i\n", indexA, array[indexA], indexB, array[indexB]);
int temp = array[indexA];
array[indexA] = array[indexB];
array[indexB] = temp;
}

目前，对 heapify 的递归调用并未对堆进行完全排序。我需要多次调用 maxheap 吗？这似乎是获得最大堆的唯一方法

Answer 1

很微妙的问题！除了各种小烦恼，这意味着你的代码在我修复一些东西（函数原型和#includes，以及缺少 printTree() 函数）之前不会运行，你真正的问题在于

while(i > 0) heapify(array, n, i--);

这永远不会调用heapifywith i==0，因为您使用post-increment运算符 (i--而不是--i。因此，对 heapify 的最后一次调用具有 i==1。

所以你需要的第一个改变是：

i = n / 2;
while(i > 0) heapify(array, n, --i);

你的heapify代码也有问题。首先，当你寻找孩子的时候，你测试数组元素是否为零；如果是，则将子节点设置为节点 0（实际上是一个有效节点）。我稍微改变了一些东西，所以你首先将左右孩子初始化为-1，这样你就可以区分“有效”和“无效”之间的区别。

最后 - 当您进行交换时，您需要向下递归树；并且您正在查看错误的腿（您正在重新检查刚刚交换的腿，而不是向下钻取）：

swap(array, i,largest);
heapify(array, n, i);

代替

swap(array, i,largest);
heapify(array, n, largest);

综合起来，代码变成如下：

#include <stdio.h>

void buildHeap(int array[], int n);
void heapify(int array[], int n,  int i);
void swap(int array[], int indexA, int indexB);
void printTree(void);

int* TREE; // global variable used for printing the entire tree

int main(int argc, char *argv[])
{
int heapArray[] = {0, 1, 2, 3, 4, 5, 6 , 7, 8 ,9 ,10 , 11, 12, 13 ,14 ,15};
int n = sizeof(heapArray)/sizeof(int);
TREE = heapArray;

printTree();
buildHeap(heapArray, n);
printTree();
return 0;
}

void printTree(void)
{
// lazy way to print the entire tree...
  int* array = TREE;
  printf("                        %3d\n ", array[0]);
  printf("            %3d                     %3d\n", array[1], array[2]);
  printf("      %3d         %3d         %3d         %3d\n", array[3], array[4], array[5], array[6]);
  printf("   %3d   %3d   %3d   %3d   %3d   %3d   %3d   %3d\n", array[7], array[8], array[9], array[10], array[11], array[12], array[13], array[14]);
  printf("%3d\n", array[15]);

  printf("\n");
}

void buildHeap(int array[], int n)
{
  printf("buildHeap\n");
  // changed starting condition
  int i = n/2;
  // changed from i-- to --i so we get to zero
  while(i > 0) heapify(array, n,--i);
}

void heapify(int array[], int n,  int i)
{
  printf("heapify [%i] = %i\n", i, array[i]);
  printTree();
  // mark nodes initially as -1 to distinguish from "valid" zero
  int childLeft = -1, childRight = -1;
  int largest = i;

  // changed the way we check for valid nodes:
  if(2*i+1<n) childLeft = 2*i+1;
  if(2*i + 2<n) childRight = 2*i + 2;

  // see if any nodes are invalid now:
  if(childLeft < 0 && childRight < 0) return;
  if(childLeft < 0) childLeft = childRight;
  if(childRight < 0) childRight = childLeft;

  printf("child left [%i] = %i  child right [%i] = %i\n", childLeft, array[childLeft], childRight, array[childRight]);
  if(array[childLeft] > array[i]) largest = childLeft;
  if(array[childRight] > array[largest]) largest = childRight;
  if(largest != i)
  {
    swap(array, i,largest);
    heapify(array, n, largest);
  }
}

void swap(int array[], int indexA, int indexB)
{
  printf("swap [%i] %i with [%i] %i\n", indexA, array[indexA], indexB, array[indexB]);
  int temp = array[indexA];
  array[indexA] = array[indexB];
  array[indexB] = temp;
}

最后的排序树是

                         15
              10                      14
        8           9          12          13
     7     1     0     4    11     5     2     6
  3

现在每个节点的头部都比它下面的孩子大——正如你对这个算法所期望的那样。