HeapSort問題

Question

我的任務是根據僞代碼將代碼寫入heapsort。它應該排列輸入數組（4 3 2 5 6 7 8 9 12 1），然後使用printHeap方法打印它。我知道printHeap的工作原理，因爲我已經使用了一個名爲buildHeap的方法（構建最大堆二叉樹，但你們都已經知道:)），並且它的工作原理完美無誤，所以我的問題在於heapSort 。

它排序正確，並以它應該的方式打印它（父 - 子1，父 - 2等），唯一的問題是，最大值和最後一個值是12，突然變成24，我不知道爲什麼。

的代碼如下：

void heapSort(int a[], int n){ 
int x = n+1; 
int i; 
int temp; 
buildMaxHeap(a, n); 
for (i = n; i >= 1; i--){ 
    temp = a[i]; 
    a[i] = a [0]; 
    a [0] = temp; 
    x--; 
    heapify(a, 0, x); 
} 

void printHeap(int a[], int n){ 

int i; 
printf("graph g { \n"); 
for (i = 0; i < n/2; i++){ 
    printf("%d -- %d\n", a[i], a[left(i)]); 
    if (right(i) < n){ 
     printf("%d -- %d\n", a[i], a[right(i)]); 
    } 
} 
printf("}\n"); 

輸出爲以下內容：只要你知道究竟是什麼我也做

1 2 3 4 5 6 7 8 9 24 
graph g { 
1 -- 2 
1 -- 3 
2 -- 4 
2 -- 5 
3 -- 6 
3 -- 7 
4 -- 8 
4 -- 9 
5 -- 24 
} 

，我會附上而.C這裏提交： https://onedrive.live.com/redir?resid=8BC629F201D2BC63!26268&authkey=!AFqVlm9AptiZ_xM&ithint=file%2cc

真的非常感謝您的幫助！

乾杯 阿里克

Answer 1

嗯，你觀察一個未定義的行爲。 （我個人在網上IDE得到了0代替12（24）。）

嘗試：

void heapSort(int a[], int n) 
{ 
    int x = n; /* changed from n+1 */ 
    int i; 
    int temp; 

    buildMaxHeap(a, n); 
    for (i = n-1; i >= 0; i--){ /*<-- changed*/ 
     temp = a[i]; 
     a[i] = a[0]; 
     a[0] = temp; 
     x--; 
     heapify(a, 0, x); 
    } 
} 

你在今天幾乎所有的通用語言陣列開始指數0 [對於深入信息，請參閱wiki。]你錯誤地循環了你的數組for (i = n; i >= 1; i--)，並且由於堆是最大值，所以不要處理第一個元素並且與最後一個元素出界。儘管在標準中定義了nth元素的算術，但它並不意味着< n和某些指針的工作。

在附註上，您可以使用宏（#define s）作爲left，right等函數來提高性能並簡化讀取。

我希望能節省一天的時間和AlgoDat練習。