使用二叉堆设计基于.NET的泛型优先级队列  

Using Binary Heap to Design Generic Priority Queue Based on.NET

作　　者：黄明志 HUANG Ming-zhi(School of Information Science and Technology,Zhongkai University of Agriculture and Engineering,Guangzhou 510225)

机构地区：[1]仲恺农业工程学院信息科学与技术学院,广州510225

出　　处：《现代计算机》2018年第24期90-95,共6页Modern Computer

摘　　要：提出使用二叉堆作为元素的存储结构,设计基于.NET的优先级队列,实现根据元素的默认比较器或指定的比较器,将优先级别最高的元素首先出队的泛型集合类PriorityQueue<T>。类中的入队和出队操作的时间复杂度均为O(logN),Peek操作的时间复杂度为O(1)。且因其设计的框架结构、命名规则和风格等完全与.NET中System.Collec-tions.Generic命名空间的相关泛型集合类、特别是Queue<T>类的接口和使用方法相一致,故其具有良好的通用性和柔韧性。Proposes binary heap as the elements of storage structure, designs the priority queue for comparison according to the elements of the default or a specified comparer, highest priority element first output of a generic collection class named PriorityQueue<T> based on.NET. The time complexity of method for Enqueue and Dequeue in the class is O(logN), time complexity of Peek is O(1), and because of its design,frame structure, naming and style is completely consistent to the related generic collection classes, in particular Queue<T> in the namespace Sytem.Collections.Generic based on.NET, and therefore has good versatility and flexibility.

关 键 词：优先级队列 .NET 泛型 完全二叉树 二叉堆 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]