.NET中是否存在排序队列？ [英] Does a sorted queue exist in .NET?

问题描述

我需要一个相当专门的集合.NET，我不认为BCL可以帮助我，但我想我会抛出它，如果任何人知道类似的东西。

I have a need for a fairly specialised collection .NET, and I don't think that the BCL can help me, but I thought I'd throw it out there for if anyone knew of something similar.

基本上，我的要求是：

• 我有一个值对的列表，例如作为：（3,10），（5,10），（3,7），（5，5）


• 顺序很重要， （3，10）！=（10，3）


• 重复的单个值是正确的，但重复的对应该删除（最好是静默）。


• 踢球者是，我需要这个列表所有的时间。我只对任何时候的排序算法定义的列表中的第一个值感兴趣。

• I have a list of pairs of values, such as: (3, 10), (5, 10), (3, 7), (5, 5)
• Order is important, ie. (3, 10) != (10, 3)
• Duplicates of individual values are fine, but duplicate pairs should be dropped (preferably silently).
• The kicker is, I need this list sorted all the time. I'm only ever interested in the first value in the list as defined by the sort algorithm at any one time.

示例代码，我想要能够做的（因为我设想它可能会被实现，其他适合上面的实现是适当的）：

So, some example code of what I want to be able to do (as I envision it would probably be implemented, other implementations that fit the above are fine to):

public class Pair
{
    public Pair(int first, int second)
    { First = first; Second = second; }
    public int First { get; set; }
    public int Second { get; set; }
}

SortedQueue<Pair> foo = new SortedQueue<Pair>((left, right) => {
    return right.First - left.First;
});

foo.Add(new Pair(10, 3));
foo.Add(new Pair(4, 6));
foo.Add(new Pair(6, 15));
foo.Add(new Pair(6, 13)); // This shouldn't cause a problem

Pair current = foo.Shift(); // current = (4, 6)

推荐答案

：

我需要这个列表。
我只对任何一次的
排序算法定义的列表中的第一个
值感兴趣。

I need this list sorted all the time. I'm only ever interested in the first value in the list as defined by the sort algorithm at any one time.

这听起来像你不想要一个排序队列，但优先级队列。如果性能是一个问题，那么PQ肯定会更快，O（log n）vs O（n）。但是drop-duplicates问题需要你保持一个并行HashSet<>。

This sounds like you do not want a Sorted Queue but a Priority Queue. If performance is an issue then a PQ will certainly be faster, O(log n) vs O(n). But the drop-duplicates issue would require you to keep a parallel HashSet<> as well.

这篇关于.NET中是否存在排序队列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！