The values of my array are changing in an unexpected way

Question

#define HEAP_MAX_SIZE 100
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

int size;
int heap[HEAP_MAX_SIZE];
int printcounter=0;

void swap(int *a, int *b)
{
    int temp = *b;
    *b = *a;
    *a = temp;  
}
/*
*max_heap() performs creates a max heap. (the printf in comments were used for debugging)
*/
void max_heap(int key)
{
    int leftkey = (2*key) +1;
    int rigtkey = (2*key) +2;
    //printf("key is: %d left child index is: %d right child index is: %d \n", key, leftkey, rigtkey);  
    //printf("value at key is: %d left child is: %d right child is: %d \n", heap[key], heap[leftkey], heap[rigtkey]);
    if (key >= 0){
        if (leftkey < size && leftkey != size){
            if (heap[leftkey] > heap[key]){ printf("If %d > %d\n", heap[leftkey], heap[key]);

                    printf("Swap %d and %d\n", heap[leftkey], heap[key]); 
                    swap(&heap[leftkey], &heap[key]);
                    max_heap(key+1);
            }
        }
        if (rigtkey < size && rigtkey != size){ 
            if (heap[rigtkey] > heap[key]){ printf("If %d > %d\n", heap[rigtkey], heap[key]);       

                    printf("Swap %d and %d\n", heap[rigtkey], heap[key]);                   
                    swap(&heap[rigtkey], &heap[key]);
                    max_heap(key+1);
            }
        }
        if (heap[leftkey] < heap[key] && heap[rigtkey] < heap[key]){
            max_heap(key-1);
        }

    }
}

/**
 * heapDelete() removes the biggest integer in the heap and returns it.
 *
 */
int heapDelete()
{
    int largest;    
    int i;  

    max_heap(size/2);
    largest = heap[0];

    ///Shifting the array so the first value is gone. (Should have used a link list instead of an array)
    for (i=0;i<size;i++){
        heap[i] = heap[i+1];
    }       
    size--; 
    printf("Just deleted: %d\n", largest);
    return largest;
}


/**
 *  addHeap(thing2add) adds the "thing2add" to the Heap.
 *
 */
void addHeap(int thing2add)
{   
    if (size == HEAP_MAX_SIZE)
    {
        fprintf(stderr, "Inputing too many values, increase HEAP_MAX_SIZE in intHeap.ca\n");
    }
    else
    {  
        heap[size] = thing2add;
        size++; 
    }
}

the heap array is {1 5 68 56 2 13 8 5 4 6 3 58 4 3 21 5}

Just deleted: 1

If 21 > 5

Swap 21 and 5

If 58 > 13

Swap 58 and 13

If 4 > 2

Swap 4 and 2

.... (you get the idea)....

Just deleted: 4

Just deleted: 4

Just deleted: 3

Just deleted: 3

Just deleted: 2

The swaps are fine, the deletes are fine. However the 1 is being ignored. Plus the program should finish max_heap() before saying its first "deleted:" printf. Why is it doing the printf first? Does it have something to do with stdder?

this doesn't happen all the time though. If I enter a small set like:1 5 89 23 4 or 100 5 9 4 56 8 the program works as it should.

Here's the main:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h> 

extern int pop();
extern void push(int);
extern void addHeap(int);
extern int heapDelete();
extern void printHeap();

int main(int argc, char * argv[])
{
    int value;
    int size=0;
    int i=0;
    while (scanf("%d\n", &value) != EOF) {
        fprintf(stderr, "READING INPUT: %d\n", value);
        size++;
        addHeap(value); 
    }
    /*to print the heap in XML format*/

    printHeap();

    /*Print ends here*/

    /*print the heap in descending order, followed by ascending order (by pushing and popping from a stack)*/
    for (i=0;i<size;i++){
        push(heapDelete());
    }
    for (i=0;i<size;i++){
        printf("%d ", pop());
    }

    exit(0);
    /*Decsending and Ascending order ends here*/
}

Answer 1

I have played arround with your code and one thing to notice is the parent, left child and right child must be continuous to work:

parent      at position  i
left child  at position  i + 1
right child at position  i + 2

Also in your example {1 2 3} the output must be sorted also {3 2 1} not {3 1 2}.

So, if you change

int leftkey = (2 * key) + 1;
int rigtkey = (2 * key) + 2;

to

int leftkey = key +1; 
int rigtkey = key +2;

it works as expected

valter