我不太明白为什么我的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;
}
最佳答案
- 您的返回条件在 while 循环的范围内。因此,该函数在第一次迭代中返回并且未正确堆化。
- 处理 left<= pq->count-1 但 L_CHILD(left)>=pq->count-1 的情况。
关于c - 如何从C中的最小堆中删除第一个元素?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54994035/