c - 使用数组创建堆时出错

Question

我正在尝试创建一个 Binary Min Heap在C中使用数组。我编写了代码并多次尝试用“笔和纸”执行它，它似乎有效。您能帮我理解为什么它会失败吗？

这是库代码:

#include <stdlib.h>

void swapInt(int *a, int *b) {
    int aux = *a;
    *a = *b;
    *b = aux;
}

typedef struct intHeapArray {
    int *array;
    int size;
} IntHeapArray;

IntHeapArray newIntHeapArray (int dim) {
    IntHeapArray new;
    new.array = (int*) malloc(sizeof(int)*dim);
    new.size = 0;
    return new;
}

int findFather (int index) {
    return (index - 1) / 2;
}

int findLeftChild (int index) {
    return index * 2 + 1;
}

int findRightChild (int index) {
    return index * 2 + 2;
}

int minFatherChilds (IntHeapArray h, int index) {
    int leftchild = findLeftChild(index);
    int rightchild = findRightChild(index);
    if (rightchild >= h.size)
        rightchild = leftchild;
    if (h.array[index] > h.array[leftchild])
        index = leftchild;
    if (h.array[index] > h.array[rightchild])
        index = rightchild;
    return index;
}

void reorganizeIntHeapArray (IntHeapArray *h, int index) {
    int father, leftchild, child;
    father = findFather(index);
    while (index > 0 && h->array[index] < h->array[father]) {
        swapInt(&h->array[index], &h->array[father]);
        index = father;
    }
    leftchild = findLeftChild(index);
    while (leftchild < h->size && index != minFatherChilds(*h, index)) {
        child = minFatherChilds(*h, index);
        swapInt(&h->array[index], &h->array[child]);
        index = child;
    }
}

void enqueueIntHeapArray (IntHeapArray *h, int val) {
    h->array[h->size] = val;
    h->size++;
    reorganizeIntHeapArray(h, h->size - 1);
}

这是主脚本的调用:

#include <stdio.h>
#include "heap.h"

void printIntArray (int *a, int dim) {
    int i;
    printf("[");
    for (i = 0; i < dim - 1; i++)
        printf("%d, ", a[i]);
    printf("%d]\n", a[dim-1]);
}

int main () {
    IntHeapArray h;
    int n, i, val;

    printf("How many value would you like to add to the heap? ");
    scanf("%d", &n);

    h = newIntHeapArray(n);

    printf("Insert values:\n");
    for (i = 0; i < n; i++) {
        scanf("%d", &val);
        enqueueIntHeapArray(&h, val);
    }

    printf("This is your heap:\n");
    printIntArray(h.array, h.size);

    return 0;
}

代码可以编译。尝试使用以下输入:6 3 8 9 2 0。 它将打印: [3, 2, 0, 9, 6, 8] 这显然是错误的。但我真的不明白我错在哪里。

Answer 1

我发现了错误。重组堆函数必须更改为:

void reorganizeIntHeapArray (IntHeapArray *h, int index) {
    int father, leftchild, child;
    father = findFather(index);
    while (index > 0 && h->array[index] < h->array[father]) {
        swapInt(&h->array[index], &h->array[father]);
        index = father;
        father = findFather(index);
    }
    leftchild = findLeftChild(index);
    while (leftchild < h->size && index != minFatherChilds(*h, index)) {
        child = minFatherChilds(*h, index);
        swapInt(&h->array[index], &h->array[child]);
        index = child;
        leftchild = findLeftChild(index);
    }
}

我只更新索引值，而不更新父索引值。因此，在第一次切换之后，它将 h->array[index] 与其自身进行比较，而不是与它的新父亲进行比较。

编辑:它仍然是错误的。我在第二个中犯了与第一个中相同的错误。我没有更新 leftchild 值。现在应该是正确的了。