优先级队列删除具有相同优先级的项目第一个进入 [英] Priority Queue remove items with same priority first one entered

问题描述

我创建了一个优先级队列，它可以按顺序输入项目并按顺序删除它们.即使两个数字具有相同的优先级，它也会删除第一个输入的数字.

I've got a priority queue created and working that enters items in order and removes them in order. Even if two numbers have the same priority, it removes the one that was entered first.

如果存在三个具有相同优先级的数字，则不会删除第一个.我将如何去做，还是应该这样做?

If there are three numbers that have the same priority, it does not remove the first one. How would I go about doing this, or should it do this?

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);
        }
    }
}

推荐答案

在这一行

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

如果它们相等，则交换元素.因此，假设您按顺序输入数字 [2, 2, 1, 3].让我们将第二个 2 称为2*"，以区别于第一个.结果堆是:

you swap elements if they're equal. So let's say you enter the numbers [2, 2, 1, 3], in that order. Let's call the second 2, "2*", to differentiate it from the first one. The resulting heap is:

      1
    /   
   2     2*
  /
 3

现在，您删除 1.那么你将 1 替换为 3:

Now, you remove 1. So then you replace the 1 with 3:

      3
    /   
   2     2*

在您的 ReheapDown 方法中，父母有两个孩子，您选择的是最小的孩子.当您比较两个 2 时，您会得到以下代码:

In your ReheapDown method, the parent has two children, and you're selecting the smallest child. When you compare the two 2's, you have this code:

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

由于2 == 2，它设置maxchild = rightchild，所以新的root变成2*——第二个2 输入.你的堆现在看起来像这样:

Since 2 == 2, it sets maxchild = rightchild, so the new root becomes 2*--the second 2 that was entered. Your heap now looks like this:

      2*
    /   
   2     3

接下来要移除的将是2*.

那么，您可能会想，如果您将 <= 更改为 <，它将解决您的问题.但它不会.

You might think, then, that if you change that <= to <, it'll solve your problem. But it won't.

当您考虑堆可能发生变异的所有不同方式时，除非您提供其他信息，否则无法保证相同的项目会按照插入的顺序被删除.考虑一下如果您按 [1, 3, 2, 2*] 的顺序输入项目会发生什么.结果堆是:

When you consider all the different ways that the heap can mutate, it's impossible to guarantee that equal items will be removed in the same order that they were inserted, unless you supply additional information. Consider what happens if you enter items in the order [1, 3, 2, 2*]. The resulting heap is:

      1
    /   
   2*    2
  /
 3

如果你删除 1，你最终会得到:

If you remove 1, you end up with:

      3
    /   
   2*    2

在这种情况下，<= 会帮助您.但在前一种情况下，它不会.

In this case, the <= would help you out. But in the previous case, it wouldn't.

唯一保证相等项目的移除顺序的方法是在比较中添加第二个条件——基本上，你必须使那些相等的项目不相等.您需要在密钥中添加日期戳或序列号，以便识别广告订单.

The only way to guarantee removal order of equal items is to add a second condition on your comparison--basically, you have to make those equal items unequal. You either need to add a date stamp or sequential number to the key so that you can identify the insertion order.

这篇关于优先级队列删除具有相同优先级的项目第一个进入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！