C：在空堆中插入元素

Question

我应该编写一个代码，将标准输入中的数字插入到一个最初为空的最大堆中。我发现我的代码只是没有得到正确的元素顺序，它甚至没有在第三个数字之前进入 while 循环。有人愿意帮忙吗？提前致谢！

int heap_insert(heap* h, int key) {

    if (h->size==MAX_HEAP_SIZE){  
        return(-1);
    }

    h->size=h->size+1;
    int i=h->size-1; 
    h->array[i]=key;                   
    int parent=(i-1)/2;

    while (i>1 && h->array[parent]< key) {
        h->array[i]= h->array[parent];
        i = parent;
        h->array[i]=key;
    }
return(0);
}

Answer 1

在第3个数字之前不会进入while循环，因为在第3个数字输入之前你的i不大于1。在第一个数字 i = 0，然后 1 然后 2.

对于循环，这是我解决问题的建议：假设您输入值 3、5、7。一旦输入 5，您就需要交换。 5 应该成为新的根，3 应该是 child。（所以 maxheap 属性被保留）然后，当输入 7 时，另一个交换是有序的。这次用5。7变成root，3和5是children。这告诉您有关索引的什么信息？如果我们也插入 10、16、1 会怎样？更多互换？如果你正确地回答了这些问题，while 循环应该很容易解决。（提示：您需要从 child 开始继续交换，然后移动到下一个 parent，直到一切正常）

Answer 2

it doesnt even enter the while loop before the third number

这部分可以回答。在 i 为 2 或更大之前，您的循环不会继续...

while (i > 1 && h->array[parent]< key) {
       ^^^^^

这是设置 i.

的代码

h->size = h->size+1;
int i   = h->size-1;

这样的代码更容易理解：

int i = h->size;
h->size++;

第一次通过时，i 将为 0（假设 h->size 初始化为 0，您没有显示堆初始化代码）。第二次是 1。第三次是 2，最后循环可以运行.

我猜你想要 i >= 1 在 while 循环中，这样它会继续第二次调用。

至于为什么它不起作用，主要问题是您忘记在循环中更改 parent。

/* i and parent initialized */
int i=h->size-1;
...
int parent=(i-1)/2;

while (i>1 && h->array[parent]< key) {
    h->array[i]= h->array[parent];

    /* i is changed, but where's parent? */
    i = parent;

    h->array[i]=key;
}

它应该是这样的。我已经将只应在循环索引中使用的 i 更改为更具描述性的 new.

/* new and parent initialized */
int new = h->size;
...
int parent = (new-1)/2;
while( new != 0 && h->array[parent] < key ) {
    h->array[new] = h->array[parent];
    h->array[parent] = key;

    /* new AND parent changed */
    new = parent;
    parent = (new-1)/2;
}

这是完整的代码，另外我将堆大小设置为动态的，因为固定大小的结构是最好避免的拐杖。

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int size;
    int max_size;
    int *array;
} heap;

#define INIT_HEAP_SIZE 4

static heap *heap_init() {
    heap *h = calloc(1, sizeof(heap));

    h->max_size = INIT_HEAP_SIZE;
    h->array = calloc(h->max_size, sizeof(int));

    return h;
}

static void heap_destroy(heap *h) {
    free(h->array);
    free(h);
}

static void heap_grow(heap *h) {
    h->max_size *= 2;
    h->array = realloc( h->array, h->max_size * sizeof(int) );
}

static void heap_insert(heap* h, int key) {
    if (h->size >= h->max_size) {
        heap_grow(h);
    }

    int new = h->size;
    h->size++;

    h->array[new] = key;

    int parent = (new-1)/2;
    while( new != 0 && h->array[parent] < key ) {
        h->array[new] = h->array[parent];
        h->array[parent] = key;

        new = parent;
        parent = (new-1)/2;
    }

    return;
}

int main(void) {
    heap *h = heap_init();

    heap_insert(h, 23);
    heap_insert(h, 11);
    heap_insert(h, 42);
    heap_insert(h, 5);
    heap_insert(h, 99);

    for( int i = 0; i < h->size; i++ ) {
        printf("%d: %d\n", i, h->array[i]);
    }

    heap_destroy(h);
}

C：在空堆中插入元素

C: insert element in empty heap

c

heap