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

Question

我被要求使用堆排序，冒泡排序和选择排序对50,000个随机整数（从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)) {

to

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

并且在deleteHeap函数中，代码从以下位置更改

reheapDown(heap, 0, last);

到

reheapDown(heap, 0, last-1);

对我来说，这两个更改只是相互抵消，所以我不确定为什么要固定代码...有人有想法吗？

感谢您的帮助。相当奇怪的问题。