C# .NET 中的堆类

Heap class in .NET

提问by Tomek Tarczynski

Possible Duplicate:
Fibonacci, Binary, or Binomial heap in c#?

可能的重复：
c# 中的斐波那契、二进制或二项式堆？

Is there any class like heap in .NET? I need some kind of collection from which I can retrieve min. element. I just want 3 methods:

.NET 中是否有类似堆的类？我需要某种可以从中检索分钟的集合。元素。我只想要3种方法：

• Add()
• RemoveMinElement()
• GetMinElement()

• 添加（）
• 移除最小元素()
• 获取最小元素()

I can't use sorted list because there keys has to be unique, and I might have several identical elements.

我不能使用排序列表，因为键必须是唯一的，而且我可能有几个相同的元素。

采纳答案by codekaizen

You could use SortedListor a SortedDictionary(see discussion below) with a custom key. If you used a type with referential equality, but could be compared based on the value you care about, then this could work.

您可以使用带有自定义键的SortedList或SortedDictionary（参见下面的讨论）。如果您使用了具有引用相等性的类型，但可以根据您关心的值进行比较，那么这可以工作。

Something like this:

像这样的东西：

class HeapKey : IComparable<HeapKey>
{
    public HeapKey(Guid id, Int32 value)
    {
        Id = id;
        Value = value;
    }

    public Guid Id { get; private set; }
    public Int32 Value { get; private set; }

    public int CompareTo(HeapKey other)
    {
        if (_enableCompareCount)
        {
            ++_compareCount;
        }

        if (other == null)
        {
            throw new ArgumentNullException("other");
        }

        var result = Value.CompareTo(other.Value);

        return result == 0 ? Id.CompareTo(other.Id) : result;
    }
}

Here is a working example of using a SortedDictionary which has binary-heap performance characteristics:

这是一个使用具有二元堆性能特征的 SortedDictionary 的工作示例：

using System;
using System.Collections.Generic;
using System.Linq;

namespace SortedDictionaryAsBinaryHeap
{
    class Program
    {
        private static Boolean _enableCompareCount = false;
        private static Int32 _compareCount = 0;

        static void Main(string[] args)
        {
            var rnd = new Random();

            for (int elementCount = 2; elementCount <= 6; elementCount++)
            {
                var keyValues = Enumerable.Range(0, (Int32)Math.Pow(10, elementCount))
                    .Select(i => new HeapKey(Guid.NewGuid(), rnd.Next(0, 10)))
                    .ToDictionary(k => k);
                var heap = new SortedDictionary<HeapKey, HeapKey>(keyValues);

                _compareCount = 0;
                _enableCompareCount = true;
                var min = heap.First().Key;
                _enableCompareCount = false;
                Console.WriteLine("Element count: {0}; Compare count for getMinElement: {1}",
                                  (Int32)Math.Pow(10, elementCount),
                                  _compareCount);   

                _compareCount = 0;
                _enableCompareCount = true;
                heap.Remove(min);
                _enableCompareCount = false;
                Console.WriteLine("Element count: {0}; Compare count for deleteMinElement: {1}", 
                                  (Int32)Math.Pow(10, elementCount),  
                                  _compareCount);   
            }

            Console.ReadKey();
        }

        private class HeapKey : IComparable<HeapKey>
        {
            public HeapKey(Guid id, Int32 value)
            {
                Id = id;
                Value = value;
            }

            public Guid Id { get; private set; }
            public Int32 Value { get; private set; }

            public int CompareTo(HeapKey other)
            {
                if (_enableCompareCount)
                {
                    ++_compareCount;
                }

                if (other == null)
                {
                    throw new ArgumentNullException("other");
                }

                var result = Value.CompareTo(other.Value);

                return result == 0 ? Id.CompareTo(other.Id) : result;
            }
        }
    }
}

Results:

结果：

Element count: 100; Compare count for getMinElement: 0

Element count: 100; Compare count for deleteMinElement: 8

Element count: 1000; Compare count for getMinElement: 0

Element count: 1000; Compare count for deleteMinElement: 10

Element count: 10000; Compare count for getMinElement: 0

Element count: 10000; Compare count for deleteMinElement: 13

Element count: 100000; Compare count for getMinElement: 0

Element count: 100000; Compare count for deleteMinElement: 14

Element count: 1000000; Compare count for getMinElement: 0

Element count: 1000000; Compare count for deleteMinElement: 21

元素数：100；比较 getMinElement 的计数：0

元素数：100；比较 deleteMinElement 的计数：8

元素数：1000；比较 getMinElement 的计数：0

元素数：1000；比较 deleteMinElement 的计数：10

元素数：10000；比较 getMinElement 的计数：0

元素数：10000；比较 deleteMinElement 的计数：13

元素数：100000；比较 getMinElement 的计数：0

元素数：100000；比较 deleteMinElement 的计数：14

元素数：1000000；比较 getMinElement 的计数：0

元素数：1000000；比较 deleteMinElement 的计数：21

回答by Ed Power

Priority Queues look like a good fit to your problem: Priority queue in .Net

优先队列看起来很适合您的问题： .Net 中的优先队列

Google for "C# priority queues" for more implementations.

谷歌搜索“C# 优先级队列”以获得更多实现。