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

Question

我按照这个问题中给出的指示(Jason的答案)来编写我的PriorityQueue<T>使用a SortedList.我知道count这个类中的字段用于确保唯一的优先级并保持相同优先级的排队顺序.

但是,当count达到其最大值并且I加1时,后者将从0开始,因此后续项的优先级将高于先前项的优先级.使用这种方法我可能需要一种"安全"重置计数器的方法count......实际上,假设有以下队列状态(格式为priority | count | item):

0 | 123 | A
0 | 345 | B
1 | 234 | C
2 | 200 | d

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

0 | 123 | A
0 | 345 | B
1 | 000 | 新元素
1 | 234 | C
2 | 200 | d

优先级的问题可以通过实现堆来解决:我创建了一个Heap类,然后我使用Heap<KeyValuePair<TPriority, TElement>了一个自定义PriorityComparer以便按元素排序TPriority.给定TPriority作为a int和TElement作为a 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());

...

更新 通过这种方式(使用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

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

您可以使用 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);
    }
}