首页 / C# / 用 C# 实现优先队列
用 C# 实现优先队列
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了用 C# 实现优先队列,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1924字,纯文字阅读大概需要3分钟。
内容图文
优先队列(priority queue) 是很重要的数据结构。我在做 ACM 题时就经常要用到她。C++ STL 就包括 priority_queue 。Java 也有 PriorityQueue 类。遗憾的是,.NET Framework Base Class Library 中并不包括优先队列。于是,我只好自己用 C# 语言写一个,如下所示:
using System; using System.Collections.Generic; namespace Skyiv.Util { class PriorityQueue<T> { IComparer<T> comparer; T[] heap; public int Count { get; private set; } public PriorityQueue() : this(null) { } public PriorityQueue(int capacity) : this(capacity, null) { } public PriorityQueue(IComparer<T> comparer) : this(16, comparer) { } public PriorityQueue(int capacity, IComparer<T> comparer) { this.comparer = (comparer == null) ? Comparer<T>.Default : comparer; this.heap = new T[capacity]; } public void Push(T v) { if (Count >= heap.Length) Array.Resize(ref heap, Count * 2); heap[Count] = v; SiftUp(Count++); } public T Pop() { var v = Top(); heap[0] = heap[--Count]; if (Count > 0) SiftDown(0); return v; } public T Top() { if (Count > 0) return heap[0]; throw new InvalidOperationException("优先队列为空"); } void SiftUp(int n) { var v = heap[n]; for (var n2 = n / 2; n > 0 && comparer.Compare(v, heap[n2]) > 0; n = n2, n2 /= 2) heap[n] = heap[n2]; heap[n] = v; } void SiftDown(int n) { var v = heap[n]; for (var n2 = n * 2; n2 < Count; n = n2, n2 *= 2) { if (n2 + 1 < Count && comparer.Compare(heap[n2 + 1], heap[n2]) > 0) n2++; if (comparer.Compare(v, heap[n2]) >= 0) break; heap[n] = heap[n2]; } heap[n] = v; } } }
如上所示,这个 PriorityQueue<T>
泛型类提供四个公共构造函数,第一个是无参的构造函数,其余的构造函数允许指定优先队列中包括的初始元素数(capacity)、如何对键进行比较(comparer)。
这个程序使用堆(heap)来实现优先队列。所以,所需的空间是最小的。Count 属性和 Top 方法的时间复杂度是 O(1),Push 和 Pop 方法的时间复杂度都是 O(logN)。
我曾经用 List<T> 泛型类实现过一个优先队列,请参见我的博客 Timus1016. A Cube on the Walk 。虽然更简单,程序代码只有 23 行,但是效率不高,其 Push 和 Pop 方法的时间复杂度都是 O(N)。
版权声明:本文为博主http://www.zuiniusn.com原创文章,未经博主允许不得转载。
原文:http://blog.csdn.net/u013948187/article/details/47271001
内容总结
以上是互联网集市为您收集整理的用 C# 实现优先队列全部内容,希望文章能够帮你解决用 C# 实现优先队列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。