algorithm that checks if an array of generic type is a MaxHeap

Question

This is my code. I'm quite new to c and pointers so probably the mistake its on pointers.

#include<stdio.h>
#include <stdbool.h>

typedef int (*comparatorPtr)(void*, void*);
bool isMaxHeap(void **heap, int index, int length, comparatorPtr comparator);

/**
 * comparator with pointers (the mistake could be here)
 */
int comparator_integer(void* e1, void* e2) {
  int i1 = *(int *) e1;
  int i2 = *(int *) e2;

  //print 2 elements of array/heap
  printf("I1 heap: %d\n", i1);
  printf("I2 heap: %d\n", i2);
  printf("***************************\n");

  if (i1 == i2) return 0;
  else if (i1 > i2) return 1;
  else return -1;
}

/**
 * Function for check if the array is or isn't a maxHeap
 */
bool isMaxHeap(void **heap, int index, int length, comparatorPtr comparator) {
  if (index > length - 1) return true;

  printf("I'm calling comparator 1 \n%d value index1\n",index);
  if (length > index * 2 && comparator((heap + index), (heap + (index * 2))) < 0) return false;

  printf("I'm calling comparator 2 \n%d value index2\n",index);
  printf("Value lenght %d\n", length);
  if (length > index * 2 + 1 && comparator((heap + index), (heap + ((index * 2) + 1))) < 0) return false;

  printf("I'm calling comparator 3 \n");
  if (index == 0) return isMaxHeap(heap, 1, length, comparator) && isMaxHeap(heap, 2, length, comparator);

  else return isMaxHeap(heap, index * 2, length, comparator) && isMaxHeap(heap, index * 2 + 1, length, comparator);
}

int main() {
  int array[6] = {90, 15, 10, 7, 12, 2}; //maxHeap array
  int length = sizeof(array)/ sizeof(array[0]);
  int index = 0;

  printf("element in position 1: %d\n",*(array + (index*2)+1));
  printf("length %d\n", length);

  isMaxHeap((void **) &array, index, length, &comparator_integer) ? printf("Yes"): printf("No");
return 0;
}

array is a MaxHeap, but I don't know why my code returns No. (printf are here just for try to catch the error)

Thanks

Answer 1

You shouldn't be casting the array to void **. That would be appropriate if you had an array of pointers, but you just have an array of data.

You need to pass the size of each array element to the function. The function then needs to cast the array pointer to char * to access array elements. It needs to multiply the size by the array indexes to get the offsdet of array elements that it passes to the comparator function (this is what happens automatically when you index typed arrays, but you have to emulate it in your function because it's operating on a generic array).

You were also using the wrong indexes for the child nodes. The left child is at index * 2 + 1, the right child is at index * 2 + 2.

There's no need to have a special case for index == 0 when making the recursive calls at the end.

You don't need to use &array when calling isMaxHeap(), since arrays automatically decay to pointers when used as function arguments.

#include<stdio.h>
#include <stdbool.h>

typedef int (*comparatorPtr)(void*, void*);
bool isMaxHeap(void *heap, int index, int length, size_t size, comparatorPtr comparator);

/**
 * comparator with pointers (the mistake could be here)
 */
int comparator_integer(void* e1, void* e2) {
    int i1 = *(int *) e1;
    int i2 = *(int *) e2;

    //print 2 elements of array/heap
    printf("I1 heap: %d\n", i1);
    printf("I2 heap: %d\n", i2);
    printf("***************************\n");

    if (i1 == i2) return 0;
    else if (i1 > i2) return 1;
    else return -1;
}

/**
 * Function for check if the array is or isn't a maxHeap
 */
bool isMaxHeap(void *heap, int index, int length, size_t size, comparatorPtr comparator) {
    char *heapbase = heap;
    if (index >= length) {
        return true;
    }

    printf("I'm calling comparator 1 \n%d value index1\n",index);
    if (length > index * 2 + 1 && comparator(heapbase + index * size, heapbase + (index * 2 + 1) * size) < 0) {
        return false;
    }

    printf("I'm calling comparator 2 \n%d value index2\n",index);
    printf("Value lenght %d\n", length);
    if (length > index * 2 + 2 && comparator(heapbase + index * size, heapbase + (index * 2 + 2) * size) < 0) {
        return false;
    }

    printf("I'm calling comparator 3 \n");
    return isMaxHeap(heap, index * 2 + 1, length, size, comparator) && isMaxHeap(heap, index * 2 + 2, length, size, comparator);
}

int main() {
    int array[6] = {90, 15, 10, 7, 12, 2}; //maxHeap array
    int length = sizeof(array)/ sizeof(array[0]);
    int index = 0;

    printf("element in position 1: %d\n",*(array + (index*2)+1));
    printf("length %d\n", length);

    isMaxHeap(array, index, length, sizeof array[0], comparator_integer) ? printf("Yes\n"): printf("No\n");
    return 0;
}