.NET中的堆类 [英] Heap class in .NET

问题描述

可能重复:
C#中的斐波那契，二进制或二项式堆?

.NET中是否有类似堆的类? 我需要一些可以从中检索分钟的集合.元素.我只想要3种方法:

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:

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

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

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

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

推荐答案

您可以使用

You could use SortedList or 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.

类似这样的东西:

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

这是使用具有二进制堆性能特征的SortedDictionary的有效示例:

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

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

结果:

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

Element count: 100; Compare count for getMinElement: 0

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

Element count: 100; Compare count for deleteMinElement: 8

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

Element count: 1000; Compare count for getMinElement: 0

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

Element count: 1000; Compare count for deleteMinElement: 10

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

Element count: 10000; Compare count for getMinElement: 0

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

Element count: 10000; Compare count for deleteMinElement: 13

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

Element count: 100000; Compare count for getMinElement: 0

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

Element count: 100000; Compare count for deleteMinElement: 14

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

Element count: 1000000; Compare count for getMinElement: 0

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

Element count: 1000000; Compare count for deleteMinElement: 21

这篇关于.NET中的堆类的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！