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

Answer 2

It's not the size of the set causes the problem, for example, your code didn't work for {1 2 5 2}. The heapsort is done by two steps generally:

• build a heap
• swap the max into its correct position, the swap disrupts the heap, then heapify the rest.

your max_heap() just performs heapifying (can't understand your implementation fully), not creating a max heap. It seems you are using a "siftUp" version of heapify which has O(n log n) time complexity, while the "siftDown" version of heapify only has O(n) time complexity.
Add the procedure of building the heap, your heapsort will work with correct heapify operation.

//build a heap first!
for (i=0; i<size; i++){
    push(heapDelete());
}