尝试从数组创建 minHeap 时出错

Question

我正在尝试从数组中获取 minHeap，但无法正确获取我试过的输入是：4 3 2 1 我得到的输出是：2 3 4 1

首先我尝试仅使用一个 int 数组来存储堆并且它起作用了，然后我更改并使用了一个结构节点数组，但最终的堆不是 minHeap

主要代码如下：

int main(){

    makeMinHeap(v,vSize-1); // v is the pointer to the array of struct node, and vSize is the 
                            // size of the array
}
    void makeMinHeap(struct node *h, int size) {
    for (int i = floor(size/2); i >= 0 ; i--) {
        heapify(h, i,size);
    }
}

void heapify(struct node *h, int i,int size) {
    int l = left(i);
    int r = right(i);

    int m = i;

    if (l < size && h[l].value < h[i].value) {
        m = l;
    }
    else if (r < size && h[r].value < h[i].value) {
        m = r;
    }

    if (m != i) {
        swap(&h[m].value, &h[i].value);
        heapify(h, m, size);
    }

}

int left(int i) { return 2 * i; }

int right(int i) { return (2 * i + 1); }

void swap(int *x, int *y) { 
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

Answer 1

以下是一些问题：

节点的第一个（左）child 不在 i*2，而是在 i*2+1。右边的 child 在 i*2+2.
heapify中的else if条件确实应该是一个单独的if，你不想与h[i].value比较而是与h[m].value比较，因为您想与目前为止的最小值进行比较（可能在左侧 child）
由于 vSize 是数组的大小，因此您不应使用 makeMinHeap(v, vSize-1) 进行初始调用，因为这样您将永远不会查看数组中的最后一个值。 -1 仅对 heapify 循环有意义，它确实可以从 i = floor((size-1)/2) 开始，因此应该只在此处应用减法。

以下是需要更正的相关函数：

int left(int i)  { return 2 * i + 1; } // corrected
int right(int i) { return 2 * i + 2; } // corrected

void heapify(struct node *h, int i, int size) {
    int l = left(i);
    int r = right(i);
    int m = i;

    if (l < size && h[l].value < h[i].value) {
        m = l;
    } // Not else-if here
    if (r < size && h[r].value < h[m].value) { // h[m]!
        m = r;
    }
    if (m != i) {
        swap(&h[m].value, &h[i].value);
        heapify(h, m, size);
    }
}

void makeMinHeap(struct node *h, int size) {
    for (int i = floor((size-1)/2); i >= 0 ; i--) { // -1 here
        heapify(h, i, size);
    }
}

int main(){
    int vSize = 4;
    struct node v[4] = {4, 3, 2, 1};
    makeMinHeap(v, vSize); // No -1 here! 
    for (int i = 0; i < vSize; i++) printf("%i ", v[i].value);
    printf("\n");    
}

尝试从数组创建 minHeap 时出错

error while trying to create a minHeap from array

c

heap

min-heap