时间戳

首页 > 解决方案 > 优先级队列删除具有相同优先级的项目第一个进入

c# - 优先级队列删除具有相同优先级的项目第一个进入

问题描述

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

如果存在三个具有相同优先级的数字，则不会删除第一个。我将如何去做，或者它应该这样做？

出队功能：

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

标签： c#queuepriority-queue

解决方案

在这一行

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

如果它们相等，则交换元素。因此，假设您[2, 2, 1, 3]按顺序输入 numbers 。让我们称第二个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

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

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

推荐阅读