堆排序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 */ 
} 

实际上排序数组。