Очередь приоритетов удаляет элементы с таким же приоритетом, как первый - PullRequest
Новая
       34

Очередь приоритетов удаляет элементы с таким же приоритетом, как первый

0 голосов
/ 26 февраля 2019

У меня создана и работает очередь с приоритетами, которая вводит элементы по порядку и удаляет их по порядку.Даже если два числа имеют одинаковый приоритет, он удаляет тот, который был введен первым.

Если есть три числа с одинаковым приоритетом, он не удаляет первый.Как бы я поступил так или иначе?

Функция удаления из очереди: 

public void deQueue(Animal item)
{
    item = items.elements[0];
    items.elements[0] = items.elements[numItems - 1];
    numItems--;
    items.ReheapDown(0, numItems - 1);
}

Функция ReheapDown: 

public void ReheapDown(int root, int bottom)
{
    int maxchild, rightchild, leftchild;
    leftchild = root * 2 + 1;
    rightchild = root * 2 + 2;

    if (leftchild <= bottom)
    {
        if (leftchild == bottom)
            maxchild = leftchild;
        else
        {
            if (elements[leftchild].priority <= elements[rightchild].priority)
                maxchild = rightchild;
            else
                maxchild = leftchild;
        }

        if (elements[root].priority < elements[maxchild].priority)
        {
            Swap(elements, root, maxchild);
            ReheapDown(maxchild, bottom);
        }
    }
}

1 Ответ

0 голосов
/ 28 февраля 2019

В этой строке 

if (elements[leftchild].priority <= elements[rightchild].priority)

вы меняете элементы, если они равны.Допустим, вы вводите цифры [2, 2, 1, 3] в указанном порядке.Давайте назовем второе 2, 2*, чтобы отличить его от первого.В результате получается куча: 

      1
    /   \
   2     2*
  /
 3

Теперь вы удалите 1.Затем вы заменяете 1 на 3: 

      3
    /   \
   2     2*

В вашем методе ReheapDown у родителя есть два дочерних элемента, и вы выбираете наименьший дочерний элемент.Когда вы сравниваете два 2, у вас есть этот код: 

if (elements[leftchild].priority <= elements[rightchild].priority)
    maxchild = rightchild;
else
    maxchild = leftchild;

Поскольку 2 == 2, он устанавливает maxchild = rightchild, поэтому новый корень становится 2* - вторым 2 это было введено.Ваша куча теперь выглядит следующим образом: 

      2*
    /   \
   2     3

И следующая вещь, которая будет удалена, будет 2*.

Тогда вы можете подумать, что если вы измените это <= на<, это решит вашу проблему.Но это не так.

Когда вы рассматриваете все различные способы изменения кучи, невозможно гарантировать, что равные элементы будут удалены в том же порядке, в котором они были вставлены, если вы не предоставите дополнительную информацию.Рассмотрим, что произойдет, если вы введете элементы в порядке [1, 3, 2, 2*].В результате получается куча: 

      1
    /   \
   2*    2
  /
 3

Если вы удалите 1, вы получите: 

      3
    /   \
   2*    2

В этом случае <= поможет вам.Но в предыдущем случае это не так.

Способ only , гарантирующий порядок удаления одинаковых предметов, заключается в добавлении второго условия к вашему сравнению - в основном, вы должны сделатьэти равные предметы неравны.Вам необходимо добавить отметку даты или порядковый номер к ключу, чтобы можно было определить порядок вставки.

...