Как удалить первый элемент из минимальной кучи в C? - PullRequest
Новая
       16

Как удалить первый элемент из минимальной кучи в C?

0 голосов
/ 05 марта 2019

Я не могу понять, почему моя функция 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;
}

1 Ответ

0 голосов
/ 05 марта 2019
  1. Ваше возвращаемое условие находится в пределах цикла while.В результате функция возвращается в первой итерации и не выделяется должным образом.
  2. Обрабатывает случай, когда слева <= pq-> count-1, но L_CHILD (left)> = pq-> count-1.
...