我的最小堆插入函数有什么问题？

Question

我正在尝试用 C 编写最小堆数据结构，但在实现 insert 函数时我运行遇到了一些问题。

看起来像这样：

void insert(MinHeap* minh , int key)
{
    if(minh->itemcount == minh->maxSize)
    { 
        printf("cant insert,heap is full\n");
        return;
    }
    minh->itemcount++;
    minh->HeapArray[minh->itemcount]=key;
    int parent=getParent(minh->itemcount);
    while(parent != 0 && minh->HeapArray[parent] > minh->HeapArray[minh->itemcount])
    {
        swap(&(minh->HeapArray[parent]), &(minh->HeapArray[minh->itemcount]));
        parent = parent/2;
    }
}

现在，如果我插入以下值，插入过程就会工作：

insert(minheap,5);
insert(minheap,3);
insert(minheap,2);
insert(minheap,4);

输出结果为：

2 4 3 5

这是一个有效的输出，因为它遵循最小堆属性。

但是一旦我开始添加更多值（如 1），输出为：

2 1 3 5 4

如您所见，出现了 1 的“冒泡”，但它似乎并没有一直上升，因为 1 应该是第一个元素，而不是 2。我不确定为什么会这样，因为我的插入代码与任何其他最小堆插入函数具有相同的逻辑。

如果有人能帮助解决这个问题，那就太好了。

一些旁注：

MinHeap是一个类型定义的结构，它的成员是：

typedef struct Heap
{
    int* HeapArray;
    int maxSize;
    int itemcount;
} MinHeap;

我在 main 函数中创建了该结构的“实例”（使用 malloc）。我还为 HeapArray 成员动态分配了内存。我还将 itemcount 成员设置为等于 0。

此外，我的最小堆数组的索引从 1 而不是 0 开始，所以 getParent 函数 returns 如下：

int getParent(int index)
{
    return floor(index/2);
}

Answer 1

主要问题是您总是与同一元素交换，即与 minh->HeapArray[minh->itemcount] 处的最后一个元素交换：在循环的第一次迭代中，这确实是 child 12=]，但是如果迭代次数多了，就不再代表child.

附带问题：您的循环中有 parent = parent / 2：您为什么不在此处使用 getParent 函数？

其次，getParent函数不需要使用floor：除法已经是整数除法

这里是对主要问题发生位置的更正：

    int child = ++minh->itemcount;
    minh->HeapArray[child] = key;
    int parent = getParent(child);
    while (parent != 0 && minh->HeapArray[parent] > minh->HeapArray[child]) {
        swap(&(minh->HeapArray[parent]) , &(minh->HeapArray[child]));
        child = parent;
        parent = getParent(child);
    }

我的最小堆插入函数有什么问题？

What is wrong with my insert function for min-heaps?

c

algorithm

heap

min-heap

data-structures