优先队列删除优先顺序相同的项目 [英] 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 ，因此新的根成为 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 ，则结果为:

      3
    /   \
   2*    2

在这种情况下，< = 会帮助您.但是在以前的情况下，不会.

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

保证相同项目的移除顺序的 only 方法是在比较中添加第二个条件-基本来说，您必须使这些相等项目不相等.您需要在密钥上添加日期戳或序列号，以便标识插入顺序.

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屋！