0

配列を使用して 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]それは明らかに間違っています。しかし、どこが間違っているのかよくわかりません。

4

1 に答える 1

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]をそれ自体と比較し、新しい父親とは比較しません。

編集：それはまだ間違っていた。私は2番目に行いましたが、最初のエラーと同じエラーが発生しました。左子の値を更新していませんでした。今では正しいはずです。

于 2012-06-10T13:44:18.577 に答える