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

Question

我被要求用堆排序、冒泡排序和选择排序对 50,000 个随机整数（从 0 到 1000）进行排序，看看哪种方法最有效。我的冒泡排序和选择排序工作正常，但我注意到我的堆排序没有正确排序。我从另一个程序中重新使用了我的堆排序并且它在原始程序中工作，所以我很困惑为什么它在这里不起作用。然后我用一个较小的整数进行测试，它起作用了。 我确定堆排序适用于 5760 及以下数字，但不适用于 5761 及以上数字，我不确定为什么.. 谁能帮忙？

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

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

注意：我将只包括堆函数和 main 函数的那部分。

#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);

对我来说，这两个变化只是相互抵消，所以我不确定为什么这会修复代码...有人有想法吗？

顺便感谢你的帮助。好奇怪的问题。

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

Why does my data structure heap sort break at 5761 numbers to sort?

c

sorting

heap

heapsort

data-structures