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

Question

I was asked to sort 50,000 random integers (from 0 to 1000) with heap sort, bubble sort, and selection sort, to see which method is most efficient. My bubble and selection sort works fine, but I noticed my heap sort did not sort correctly. I re-used my heap sort from another program and it worked in the original program, so I was confused as to why it wasn't working here. I then tested with a lower number integers, and it worked. I determined that the heap sort works at 5760 and less numbers, but not 5761 numbers and beyond, and I'm not sure why.. can anyone help?

Note: The sorted array is printed to a txt file in the project folder named "heap.txt", the number that prints in the output screen is the number of iterations the program took to sort the data.

I tried to find any numerical relevance of the number 5761 but could not find why this number in particular would break the program.

Note: I will only include the heap functions and that section of the main function.

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

Note: _CRT_SECURE_NO_WARNINGS is there so i can use all system functions present without warnings MAX is a constant with the number of random numbers. It's set at the top of the program and is currently set at 5761

Answer 1

A teaching assistant at my university solved the issue, although we aren't sure why this broke the code and why it broke at 5761.

Anyways, in reheapDown function, the code changes from

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

to

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

and in the deleteHeap function, the code changes from

reheapDown(heap, 0, last);

to

reheapDown(heap, 0, last-1);

To me, the two changes simply counteract each other, so i'm not sure why this fixed the code... Anyone have an idea?

Thanks for your help by the way. Quite a weird issue.