.NET中的堆类

Question

可能重复：
在C#中有类似堆的类吗？

.NET中是否有像堆这样的类？ 我需要一种集合，可以从中检索最小元素。 我只需要3种方法：

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

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

- Tomek Tarczynski

---

因为键必须是唯一的，所以我无法使用已排序的列表。.Net 4.0现在有一个SortedSet。 - BlueRaja - Danny Pflughoeft

请参见https://dev59.com/-nVD5IYBdhLWcg3wE3Jo。 - Colonel Panic

您可能会对这个NuGet包感兴趣，它实现了一个基于堆的优先队列。与SortedSet不同的是，它支持重复项。 - ChaseMedallion

@BlueRaja-DannyPflughoeft SortedSet 也不允许重复。 - Atario

.NET 6目前处于预览阶段，其中System.Collections.Generic中实现了PriorityQueue<TElement,TPriority>，它被实现为最小堆。 - bodhizero

Answer 1

你可以使用 SortedList 或者一个带有自定义键的 SortedDictionary（下面会讨论）来实现。如果你用了一个具有引用相等性的类型，但是可以基于你所关心的值进行比较，那么这个方法就可行。 类似这样：

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的工作示例，它具有二叉堆性能特征：

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；获取最小元素所需比较次数：0

元素数量：100；删除最小元素所需比较次数：8

元素数量：1000；获取最小元素所需比较次数：0

元素数量：1000；删除最小元素所需比较次数：10

元素数量：10000；获取最小元素所需比较次数：0

元素数量：10000；删除最小元素所需比较次数：13

元素数量：100000；获取最小元素所需比较次数：0

元素数量：100000；删除最小元素所需比较次数：14

元素数量：1000000；获取最小元素所需比较次数：0

元素数量：1000000；删除最小元素所需比较次数：21

- codekaizen

---

SortedList 过于复杂，而且性能特征更差。 - Matthew Flaschen

@codek，一个 SortedList 的性能为 O(n) 或 O(nlog(n))，一个 PQ 的添加/删除操作时间为 O(log(n))。 - H H

一个堆不是二叉（搜索）树的实现。请参见http://en.wikipedia.org/wiki/Priority_queue#Simple_implementations。 - H H

codekaizen，不是所有的二叉树都是相同的。SortedList具有O(n)的插入和删除（http://msdn.microsoft.com/en-us/library/ms132319%28VS.85%29.aspx）。二叉堆在最坏情况下具有O(log n)的插入或deleteMin/Max。 - Matthew Flaschen

我并不是说二叉堆适用于所有应用程序。我的意思是，当你想要堆的性能特征（正如OP所需）时，SortedList是错误的。我认为在这里使用SortedDictionary也是错误的。它没有使用二叉堆实现，也没有声称使用。相反，它使用了二叉搜索树。其中一个基本区别是SortedDictionary无法在常数时间内执行getMinElement。 - Matthew Flaschen

Answer 2

优先队列看起来是解决你的问题的好选择：.Net中的优先队列

搜索"C#优先队列"以获取更多实现。

- Ed Power

---

这是一个 .Net 实现 - https://code.msdn.microsoft.com/windowsdesktop/Net-Implementation-of-a-d3ac7b9d#content - u8it