我有一个反向排序的堆。我正在尝试建立一个最大堆:
我有的代码:
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 吗?这似乎是获得最大堆的唯一方法