c - 检查泛型数组是否为 MaxHeap 的算法

Question

这是我的代码。我对 c 和指针很陌生，所以可能是指针上的错误。

#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 是一个 MaxHeap，但我不知道为什么我的代码返回 No。(printf 在这里只是为了 try catch 错误)

谢谢

Answer 1

您不应该将数组转换为 void **。如果您有一个指针数组，那将是合适的，但您只有一个数据数组。

您需要将每个数组元素的大小传递给函数。然后该函数需要将数组指针转换为 char * 以访问数组元素。它需要将大小乘以数组索引以获得它传递给比较器函数的数组元素的 offsdet(这是当您索引类型化数组时自动发生的事情，但您必须在您的函数中模拟它，因为它在通用数组)。

您还为子节点使用了错误的索引。左 child 位于 index * 2 + 1，右 child 位于 index * 2 + 2。

在最后进行递归调用时，不需要为 index == 0 设置特殊情况。

调用 isMaxHeap() 时不需要使用 &array，因为数组在用作函数参数时会自动衰减为指针。

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