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

非常微妙的問題！除了各種小煩惱，這意味着你的代碼將無法運行，直到我固定的幾件事情（函數原型和＃包括，以及缺乏一個printTree（）函數），你真正的問題是在該行

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

這永遠不會調用heapify與i==0，因爲你使用post-increment運營商（i--而不是--i因此，爲了heapify最後一次通話有我== 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 

現在每個節點的頭部比它下面的孩子大 - 就像你從這個算法期望的那樣。