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

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，最后循环可以运行。

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

---

至于为什么它不起作用，主要问题是您忘记在循环中更改 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);
}