使用阵列创建堆时出错

我试图在C中使用数组创建Binary Min Heap。我编写了代码并多次尝试用“笔和纸”来执行它，它似乎工作。你能帮我理解为什么它会失败吗？使用阵列创建堆时出错

这里是库代码：

#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]这显然是错误的。但我真的不明白我错在哪里。

来源

2012-06-09 Zagorax

要求陌生人通过检查发现代码中的错误并不富有成效。您应该使用调试器来逐步执行您的程序，并确定其行为与您期望的不同之处。 –

你认为应该打印什么？你为什么不在问题中这么说？准确地说，这是个好主意。 –

我没有写出它应该打印的内容，因为我链接了关于Binary Min Heap的页面。输出应该是：[0，3，2，9，6，8]。这是根据“笔和纸”执行（我希望它是正确的）。当然，我应该有0作为第一个值。最低值必须是该数据结构中的第一个值。 – Zagorax

我发现了错误。重新组织堆函数必须改为：

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]与自己进行比较，而不是与其新的父亲进行比较。

编辑：它仍然是错的。我在第二次做了同样的错误，我在第一次做了。我没有更新左值。现在应该是正确的。

来源

2012-06-10 13:44:18 Zagorax

非常好，感谢您的反馈！ – sarnold

使用阵列创建堆时出错

回答

相关问题