为什么我的数据结构堆排序中断在5761个数字排序？

Question

我被要求用堆排序、气泡排序和选择排序对5万个随机整数进行排序(从0到1000)，以查看哪种方法最有效。我的冒泡和选择排序工作得很好，但我注意到堆排序没有正确排序。我从另一个程序中重复使用我的堆排序，它在原来的程序中工作，所以我对它为什么不在这里工作感到困惑。然后，我用一个较低的整数进行了测试，结果成功了。-我确定堆排序工作在5760和更少的数字，但不是5761的数字和更多，我不知道为什么.可以帮助吗？

注意:排序的数组被打印到名为"heap.txt“的项目文件夹中的txt文件中，在输出屏幕中打印的数字是程序对数据排序所需的迭代次数。

我试图找到数字5761的任何数字相关性，但没有找到为什么这个数字，特别是会破坏程序。

注意:我将只包含堆函数和主函数的那个部分。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX 5761 //50000 integers to sort
int heapcount = 0;
int last = MAX - 1;

void reheapUp(int heap[], int newNode);
void reheapDown(int heap[], int root, int last); //the 4 heap function declarations needed for this program.
void buildHeap(int heap[]);
int deleteHeap(int heap[], int last);


int main() {
    int i;
    int arraytochange[MAX];
    for (i = 0; i < MAX; i++) {
        arraytochange[i] = rand() % 1001; // copy the random numbers in the unchanged array

    }
    buildHeap(arraytochange);
    printf("%d \n", heapcount); // number of iterations
    char* nameoffile3 = "heap.txt"; //text file name
    FILE *HeapSort; //pointer to file type
    HeapSort = fopen(nameoffile3, "w+"); //opens the file in read and write mode, creates the file if it doesn't exist
    if (HeapSort == NULL) {
        printf("Could not open file. \n"); // if couldn't open file
        system("pause");
        return 0;
    }
    else {
        printf("Heap File Opened Successfully.\n"); //print that the file opened successful
    }
    for (i = 0; i < MAX; i++) {
        fprintf(HeapSort, "%d \n", deleteHeap(arraytochange, last));
        last--;
    }

    fclose(HeapSort);
    system("pause");
    return 0;
}

void buildHeap(int heap[]) {
    int walker = 1;
    while (walker < MAX) {
        reheapUp(heap, walker);
        walker++;
    }

}

void reheapUp(int heap[], int newNode) {
    heapcount++;
    int parent = 0;
    int temp = 0;
    if (newNode != 0) {
        parent = ((newNode - 1) / 2);
        if (heap[newNode] < heap[parent]) {
            temp = heap[newNode];
            heap[newNode] = heap[parent];
            heap[parent] = temp;
            reheapUp(heap, parent);
        }
    }

}

void reheapDown(int heap[], int root, int last) {
    heapcount++;
    int leftKey; // value of left subtree, not index
    int rightKey; // value of right subtree, not index
    int largeSubtree; // value not index
    int temp;
    int index;
    if (((2 * root + 1) <= last) && (heap[2 * root + 1] > 0)) {
        leftKey = heap[2 * root + 1];
        if (((2 * root + 2) <= last) && (heap[2 * root + 2] > 0)) {
            rightKey = heap[2 * root + 2];
        }
        else {
            rightKey = NULL;
        }
        if (leftKey < rightKey) {
            largeSubtree = heap[2 * root + 1];
            index = (2 * root + 1);
        }
        else {
            largeSubtree = heap[2 * root + 2];
            index = (2 * root + 2);
        }
        if (heap[root] > largeSubtree) {
            temp = heap[index];
            heap[index] = heap[root];
            heap[root] = temp;
            reheapDown(heap, index, last);
        }
    }
    //printf("Last: %d \n", last);
}

int deleteHeap(int heap[], int last) {
    int dataOut;
    dataOut = heap[0];
    heap[0] = heap[last];
    reheapDown(heap, 0, last);
    return dataOut;
}

注意：_CRT_SECURE_NO_WARNINGS在那里，所以我可以在没有警告的情况下使用所有的系统函数，MAX是一个常量，带有随机数。它设置在程序的顶部，目前设置为5761

Answer 1

我们大学的一位助教解决了这个问题，尽管我们不知道为什么这会打破密码，为什么会在5761被打破。

无论如何，在reheapDown函数中，代码更改为

if (((2 * root + 1) <= last) && (heap[2 * root + 1] > 0)) {

至

if (((2 * root + 1) <= last) && (heap[2 * root + 1] >= 0)) {

在deleteHeap函数中，代码更改为

reheapDown(heap, 0, last);

至

reheapDown(heap, 0, last-1);

对我来说，这两个变化只是相互抵消，所以我不知道为什么这会修正代码.有人有主意吗？

顺便说一句谢谢你的帮助。一个很奇怪的问题。