C中的最小堆删除

Question

我正在尝试对最小堆执行删除功能，但是由于某种原因，该堆中的数字一直更改为0。如何解决此问题？

#include<stdio.h>

int heap[100]; //max 99 element, root starts with index 1
int count = 0;

int getParentIdx (int index)
{
    return index/2;
}

int getLeftChildIdx (int index)
{
    return index*2;
}

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

void upheapmin(int index)
{
    if(index <= 1) return;

    int parentIdx = getParentIdx(index);

    if(heap[index]  < heap[parentIdx])
    {
        int temp = heap[index];
        heap[index] = heap[parentIdx];
        heap[parentIdx] = temp;

        upheapmin(parentIdx);
    }
}

void downheapmin(int index)
{
    int leftIdx = getLeftChildIdx(index);
    int rightIdx = getRightChildIdx(index);
    //if left child is smaller
    if(heap[index] > heap[leftIdx] && heap[leftIdx] < heap[rightIdx]) {
        int temp = heap[index];
        heap[index] = heap[leftIdx];
        heap[leftIdx] = temp;
        downheapmin(leftIdx);
    //if right child is smaller 
    } else if(heap[index] > heap[rightIdx] && heap[leftIdx] > heap[rightIdx]) {
        int temp = heap[index];
        heap[index] = heap[rightIdx];
        heap[rightIdx] = temp;
        downheapmin(rightIdx);
    }
}

void pop()
{
    if(count==0) return;
    heap[1] = heap[count];
    count--;
    downheapmin(1);
}

void push(int value)
{
    count++;
    heap[count] = value;
    upheapmin(count);
}

void view()
{
    for(int i=0; i<count; i++)
    {
        printf("%2d ", heap[i]);
    }
    printf("\n\n");
}

int main()
{
    push(10);
    push(45);
    push(20);
    push(40);
    push(70);
    push(63);
    push(54);
    push(15);

    view();
    pop();
    view();

    return 0;
}

第一个view（）之后的输出：0 10 15 20 40 70 63 54

为什么45变为0，我该如何解决？

pop（）之后的预期输出（第二个view（））：0 15 40 20 45 70 63

pop（）之后的实际输出（第二个view（））：0 15 40 20 0 70 63

Answer 1

您的downheap函数没有绑定检查，您可以使用不存在的子代调用downheap（），首先使用count检查索引！

编辑：

您的视图功能从0开始计数，而堆从1开始计数，因此它打印的第一个元素可以是任何元素！以i = 1开头，并将支票从i < count更改为i <= count