分享一个自己写的简单的最大优先队列。。。
最近在看算法导论，正好看到优先队列，于是想看看.net framework中的Priority Queue是怎样实现的，结果貌似找不到这个数据结构，于是就自己写了个简陋的最大优先队列，如果有什么错误或者不妥请大家指出。
- C# code
public sealed class PriorityQueue<T> where T : IComparable<T> { private T[] heap; public int Count { get; private set; } public PriorityQueue(int capacity) { if (capacity <= 0) { throw new InvalidOperationException("优先队列的初始容量必须大于0"); } heap = new T[capacity]; } public PriorityQueue() : this(32) { } public PriorityQueue(T[] array) { Count = array.Length; heap = array; BuildMaxHeap(heap); } /// <summary> /// 获取优先级最高的元素 /// </summary> /// <returns></returns> public T Top() { ThrowExceptionIfPriorityQueueIsNull(); return heap[0]; } /// <summary> /// 删除并返回优先级最高的元素 /// </summary> /// <returns></returns> public T ExtractTop() { ThrowExceptionIfPriorityQueueIsNull(); T top = heap[0]; heap[0] = heap[this.Count - 1]; heap[this.Count - 1] = default(T); this.Count--; //保持堆的性质 HeapifyDown(0); return top; } private void ThrowExceptionIfPriorityQueueIsNull() { if (Count <= 0) throw new InvalidOperationException("优先队列为空"); } /// <summary> /// 增加索引位置元素的优先级 /// </summary> /// <param name="index">当前元素的索引</param> /// <param name="newValue">新的优先级元素</param> public void IncreasePriority(int index, T newValue) { if (index < 0 || index >= Count) { throw new IndexOutOfRangeException("当前索引超出队列范围"); } if (newValue.CompareTo(heap[index]) < 0) { throw new InvalidOperationException("新值必须大于当前值"); } heap[index] = newValue; HeapifyUp(index); } /// <summary> /// 从指定位置向下调整堆，保证堆的性质 /// </summary> /// <param name="current"></param> private void HeapifyDown(int current) { //当前元素的左子元素的索引 int left = (current + 1) * 2 - 1; //当前元素的右子元素的索引 int right = left + 1; int largest; if (left < Count && heap[left].CompareTo(heap[current]) > 0) { largest = left; } else { largest = current; } if (right < Count && heap[right].CompareTo(heap[largest]) > 0) { largest = right; } //如果单前值得优先级不为最高，则继续向下调整 if (largest != current) { Swap(ref heap[current], ref heap[largest]); HeapifyDown(largest); } } /// <summary> /// 给优先队列添加新的元素 /// </summary> /// <param name="key"></param> public void Insert(T key) { if (Count == heap.Length) { EnsureCapacity(Count); } heap[Count++] = key; HeapifyUp(Count - 1); } /// <summary> /// 将数组调整为最大堆 /// </summary> /// <param name="array"></param> private void BuildMaxHeap(T[] array) { int count = array.Length / 2 - 1; for (; count >= 0; count--) { HeapifyDown(count); } } private void EnsureCapacity(int min) { int num = min * 2; T[] detisnationArray = new T[num]; Array.Copy(this.heap, detisnationArray, heap.Length); heap = detisnationArray; } private static void Swap(ref T value1, ref T value2) { T temp = value1; value1 = value2; value2 = temp; } /// <summary> /// 从指定位置开始向上调整，保证堆的性质 /// </summary> /// <param name="current"></param> private void HeapifyUp(int current) { //当前元素的父元素 int parent = (current - 1) / 2; while (current > 0 && heap[parent].CompareTo(heap[current]) < 0) { Swap(ref heap[parent],ref heap[current]); current = (current - 1) / 2; parent = (parent - 1) / 2; } } }
[解决办法]
赞一个~~~~~~~
[解决办法]
不错……
[解决办法]
谢谢。另外一些建议：
1、IncreasePriority(int index, T newValue)可以不要。
...a) 这个index用户几乎没有办法使用（他如何知道要调整的元素在那个位置？）
...b) 缺乏对称的DecreasePriority
...c) int index泄露了内部实现。
2、既然名称叫PriorityQueue，
...a) 添加最好叫Enqueue，而不是Insert。
...b) 取出叫Dequeue，而不是ExtractTop。
3、EnsureCapacity中文为确保容量，因此条件语句最好写在函数内。如果已经事先判断是否要增加容量，函数名字可以叫做IncreaseCapacity了。
4、T[] heap可以用List<T> heap来替代，就不需要显式调整容量了。
5、如果一定要动态调整Priority，可以让T实现IPropertyChangeNotification。
6、我可能只会公开以下函数：
- C# code
public sealed class PriorityQueue<T> where T : IComparable<T>{ public PriorityQueue(); public PriorityQueue(IEnumerable<T>); public Enqueue(T value); public T Dequeue(); public T Peek();}
[解决办法]
[解决办法]
赞一个～～～
[解决办法]
赞一个～～～
[解决办法]
学习了 不错
[解决办法]
.NET中已有类似功能的类，使用起来非常方便，根本不需要自己实现，不过还是鼓励下。
请自行查看SortedList<T>的用法。
[解决办法]
Queue 的话一般用 pop 和 push 吧，呵呵
[解决办法]
[解决办法]
[解决办法]
好东西哦
[解决办法]
牛人呀， 这么厉害， 我也得像你学习
[解决办法]
看算法的都是牛人
[解决办法]
太强大了！学习了！！
[解决办法]
不错不错 学习了
[解决办法]
MSMQ就有优先队列哦
[解决办法]
[解决办法]
看上去是这么个意思
[解决办法]
我顶了，挺好
[解决办法]
楼上这个混淡打广告的 去死！！
[解决办法]
要大赞一下
[解决办法]
赞一下赞一下