更改自定义优先级队列中的优先级

Question

我按照这个问题（Jason的答案）中给出的指示来写我的<使用 SortedList 的 code>PriorityQueue。据我了解，此类中的 count 字段用于确保唯一的优先级并保留相同优先级之间的排队顺序。

但是，当 count 达到最大值并且我对其加 1 时，后者会再次从 0 开始，因此后续项目的优先级将高于前面项目的优先级。使用这种方法，我可能需要一种“安全”重置计数器 count 的方法...事实上，假设具有以下队列状态（格式为 priority | count | item< /em>):

0 | 123 | 123一个
0 | 345 | 345 B
1 | 234 | 234 C
2 | 200 | 200 D

现在假设计数器限制已达到，所以我必须将其重置为 0：因此，下一个插入的项目将具有计数器 0：例如，如果我插入一个优先级等于 1 的元素，它将被错误插入在 1 | 之前234 | 234 D

0 | 123 | 123一个
0 | 345 | 345 B
1 | 000 | 000新元素
1 | 234 | 234 C
2 | 200 | 200 D

优先级的问题可以通过实现堆来解决：我创建了一个 Heap 类，然后使用了 Heap 和一个自定义 >PriorityComparer 以便按 TPriority 对元素进行排序。 给定 TPriority 作为 int 和 TElement 作为 string，PriorityComparer 如下：

public class MyComparer : IComparer<KeyValuePair<int, string>>
{
    public int Compare(KeyValuePair<int, string> x, KeyValuePair<int, string> y)
    {
        return x.Key.CompareTo(y.Key);
    }
}

...

int capacity = 10;
Heap<KeyValuePair<int, string>> queue;
queue = new Heap<KeyValuePair<int, string>>(capacity, new PriorityComparer());

...

UPDATE 通过这种方式（使用PriorityComparer），我成功地实现了优先级队列。 现在我想添加支持以在运行时修改其行为，即从FIFO切换到优先级排序，反之亦然。由于我的优先级队列实现有一个 IComparer 字段，我认为添加一个 Comparer 属性来编辑该字段就足够了，如下所示

public IComparer
{
    set
    {
        this._comparer = value;
    }
}

：我会采取不同的方法：我可以包装不同的队列（每个队列引用给定的优先级），而不是使用二进制堆来管理优先级，如下所示。

public class PriorityQueue<T, int>
{
    private Queue<T> _defaultQueue;
    private bool _priority;
    private SortedList<int, Queue<T>> _priorityQueues;

    public PriorityQueue(int capacity)
    {
        this._defaultQueue = new Queue<T>(capacity);
        this._priority = false;
        this._priorityQueues = new SortedList<int, Queue<T>>(0);
    }

    public void PriorityEnable()
    {
        this._priority = true;
    }

    public void PriorityDisable()
    {

        this._priority = false;
    }

    public void Enqueue(T item)
    {
        if (this._priority)
        {
            // enqueue to one of the queues
            // with associated priority
            // ...
        }
        else this._defaultQueue.Enqueue(item);
    }

    public T Dequeue()
    {
        if (this._priority)
        {
            // dequeue from one of the queues
            // with associated priority and
            // return
            // ...
        }
        return this._defaultQueue.Dequeue();
    }
}

1. 当默认队列中仍有元素时，如何管理从FIFO模式到优先级模式的转换？我可以根据项目优先级将它们复制到优先级队列中...其他更好的解决方案？
2. 如何管理从优先级模式到FIFO模式的转换？在这种情况下，我会有几个优先级队列，其中可能包含元素，但不再需要根据优先级来管理它们，甚至不知道原始到达顺序......
3. 我如何管理不同队列的容量？
4. 上述两种方案的性能如何？哪个使用更多内存？

Answer 1

您可以“作弊”并使用 BigInteger 这样您就永远不会“数字用完”。这当然会导致性能随着时间的推移逐渐恶化，但可能还没有严重到足以产生影响。

将其与基于堆的优先级队列相结合，就可以了！

---

不要尝试“从 FIFO 切换到优先级排序，反之亦然” - 只需将元素放入适合该任务的两个数据结构中即可 (队列 和优先级队列）。

Answer 2

我会同时使用队列和优先级队列。
但如果你必须...

而不是一个键使用 2 个键作为一个元素。
第一个键优先级将是优先级。
第二个键time将是一个类似于时间戳的计数器。

对于常规行为，请使用priority键。

当堆已满时，按time 键HEAPIFY。
然后删除 n 需要的元素。
现在使用priority键再次HEAPIFY以返回到常规行为。

Answer 3

编辑：您通过编辑更改了您所要求的内容。你从提出一个问题转变为采用一种新方法并提出一个新问题。可能应该为您的新方法提出一个新问题，因为这个问题现在对于什么问题/评论的答案/响应是什么感到困惑。我相信您最初关于对同等优先级进行排序的问题已经得到解答。

您可以使用 long 来允许更多值。您最终总会到达终点，因此您需要对唯一值使用新模式，或者在达到最大值时“重新计数”项目（循环遍历每个项目并重置唯一计数值）。

也许可以为每个项目使用 GUID？

Guid.NewGuid()

编辑：

要在编辑后添加：如果您希望将新的 1 放置在现有的 1 之后，在比较覆盖中，当值是时返回大于结果 (1)平等的。这样就会发生以下情况：

1 > 0, return greater (1), continue
1 > 0, return greater (1), continue
1 == 1, return greater (1), continue
1 < 2, return less than (-1), insert

编辑 2：

如果第二个参数只是一个唯一值，您可以始终使用字符串并将该值设置为数字字符串。这样你就永远不会达到上限，只需要相应地解析字符串。您可以使用代表新集合的前导 alpha 值。

我还没有测试过这段代码，只是一个关于你可以做什么的想法。

static string leadingStr = "";
static char currentChar = 'a';
static Int32 currentId = Int32.MinValue;

static string getNextId()
{
    if (currentId >= Int32.MaxValue)
    {
        currentId = Int32.MinValue;
        if (currentChar >= 'z')
        {
            currentChar = 'a';
            leadingStr = leadingStr.Insert(0, "X");
        }
        else
            currentChar++;
    }
    else
        currentId++;

    return String.Format("{0}{1}-{2}", leadingStr, currentChar, currentId);
}

编辑 3：重置值

static Int64 currentValue = Int64.MinValue;
static void AddItem(object item)
{
    if (currentValue == Int64.MaxValue)
        RecountItems();

    item.counter = currentValue++;
    SortedList.Add(item);
}

static void RecountItems()
{
    currentValue = 0;
    foreach (var item in SortedList)
    {
        item.counter = currentValue++;
    }
}

编辑 4：对于第二个问题：

您可以像平常一样使用 FIFO 堆栈，但也有一个仅存储项目的唯一 ID 的优先级列表。但是，每次从 FIFO 堆栈中删除时，您都需要从列表中删除该项目。

static Object RemoveNextFIFO()
{
    if (fifoList.Count > 0)
    {
        var removedItem = fifoList[0];
        fifoList.RemoveAt(0);
        RemoveItemFromPriority(removedItem);
        return removedItem;
    }
}

static void RemoveItemFromPriority(Object itemToRemove)
{
    foreach (var counter in priorityQueue)
    {
        if (counter == itemToRemove.counter)
        {
            priorityQueue.remove(item);
            break;
        }
    }
}

static Object RemoveFromFIFO(int itemCounter)
{
    foreach (var item in fifoList)
    {
        if (item.counter == itemCounter)
        {
            fifoList.Remove(item);
            return item;   
        }
    }
}

static Object RemoveNextPriority()
{
    if (priorityQueue.Count > 0)
    {
        var counter = priorityQueue.Pop();
        return RemoveFromFIFO(counter);
    }
}