c - 如何从C中的最小堆中删除第一个元素？

Question

我不太明白为什么我的removeEntry 函数不起作用。我正在尝试为优先级队列 ADT 实现最小堆。它使用 void * 的数组。我已经验证向队列添加元素是有效的。由于某种原因，它无法正确堆积。

/* Removes the root element from the queue */
void *removeEntry(PQ *pq)
{   
    assert(pq != NULL);

    if(pq->count == 0)
        return NULL;

    /* idx is 0 since we're only deleting the first element */
    int idx = 0;
    int left = L_CHILD(idx), right, child;

    void * min = pq->data[0];

    pq->data[0] = pq->data[pq->count-1];

    pq->count--;

    while(left <= pq->count-1)
    {
        left = L_CHILD(idx);
        right = R_CHILD(idx);

        child = left;

        /* Check if right child exists */
        if(right <= pq->count-1)
        {
            /* Set child to the smaller child */
            if(pq->compare(pq->data[right], pq->data[left]) < 0)
                child = right;
        }

        /* If the data at idx is greater than it's child, then switch    them */
        if(pq->compare(pq->data[idx], pq->data[child]) > 0)
        {
            swap(pq->data[idx], pq->data[child]);
            idx = child;
        }
        else
            break;
        }

        return min;

}

这是我用来获取左右“子项”索引的宏

#define L_CHILD(id) ((2*(id))+1)
#define R_CHILD(id) ((2*(id))+2)

这里还有交换功能，以防有人好奇

static void swap(void *a, void *b)
{
    void * temp;
    temp = a;
    a = b;
    b = temp;
}

这是添加函数

void addEntry(PQ *pq, void *entry)
{
    assert(pq != NULL);

    int idx = pq->count;

    if(pq->count == pq->length)
        pq = realloc(pq, sizeof(PQ *) * (pq->length * 2));

    pq->data[idx] = entry;

    /* If the last element is greater than its parents, then swap them */
    while(idx != 0 && pq->compare(pq->data[PARENT(idx)], pq->data[idx]) > 0)
    {
        swap(pq->data[PARENT(idx)], pq->data[idx]);

        idx = PARENT(idx);
    }

    pq->count++;
    return;
}

Answer 1

1. 您的返回条件在 while 循环的范围内。因此，该函数在第一次迭代中返回并且未正确堆化。
2. 处理 left<= pq->count-1 但 L_CHILD(left)>=pq->count-1 的情况。