堆排序heapify排序

Question

我有一個女巫堆排序問題。我不知道我的代碼有什麼問題。這個程序只改變了表中的第二個和最後一個位置。這是我的代碼（沒有主要功能）：

#include<stdio.h> 
#define DUZO 100000000 
int heap_size; 
int tab[DUZO]; 

void heapify(int start){ 
    int l, r, largest, pom; 

    l = 2*start + 1; 
    r = 2*start + 2; 

    if((l < heap_size) && (tab[l] > tab[start])) 
     largest = l; 
    else 
     largest = start; 

    if((r < heap_size) && (tab[r] > tab[largest])) 
     largest = r; 
    if(largest != start){ 
     pom = tab[start]; 
     tab[start] = tab[largest]; 
     tab[largest] = pom; 

     heapify(largest); 
    } 
} 

void build_max(){ 
    int lenght, i; 
    lenght = heap_size; 

    for(i = ((lenght - 1)/2); i >= 0; --i){ 
     heapify(i); 
    } 
} 

void heap_sort(){ 
    int i; 
    build_max(); 


    for(i = heap_size-1; i > 0; --i) { 
     int tmp = tab[0]; 
     tab[0] = tab[i]; 
     tab[i] = tmp; 
     --heap_size; 
     heapify(0); 
    } 
} 

感謝您的一切幫助。

Answer 1

int heap_size = 6; 
int tab[5]; 

這要求寫入（和閱讀）過去的數組的末尾，導致與可能不好的後果不確定的行爲。

將堆大小和數組作爲全局變量是一個壞主意，它們應該是函數的參數。

l = 2*start + 1; 
r = 2*start + 2; 

這是因爲當你有堆的索引0處的頂部的索引，但

if((l <= heap_size) && (tab[l] > tab[start])) 

是檢查是否有堆的頂部索引1.對於指數將使用0，那應該是<（也在下一個檢查r）。

void build_max(){ 
    int lenght, i; 
    lenght = heap_size; 

    for(i = ((lenght - 1)/2); i > 0; i--){ 
     heapify(i); 
    } 
} 

忘記heapify頂部，所以它不一般的創建一個堆，條件應該是i >= 0。

void heap_sort(){ 
    int i, lenght; 
    build_max(); 
    lenght = heap_size; 

    for(i = lenght; i > 1; i--){ 
     heap_size -= 1; 
     heapify(i); 
    } 
} 

不交換最後一個位置的堆頂部，所以它根本不排序。循環應該看起來像

for(i = heap_size-1; i > 0; --i) { 
    /* swap top of heap in the last position */ 
    int tmp = tab[0]; 
    tab[0] = tab[i]; 
    tab[i] = tmp; 
    --heap_size; /* urk, but what can we do if heapify uses the global? */ 
    heapify(0); /* we need to heapify from the top, since that's where the leaf landed */ 
} 

實際上排序數組。