甜橘子，专注成都网站制作网站设计与营销型网站建设与优化

QQ :532337155
电话：028-86922220
 
成都网站建设设计

将想法与焦点和您一起共享

简述用C#实现优先队列方法

优先队列(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
      
       
  {
       
    IComparer
       
         comparer;
        
    T[] heap; 
       
     
    public int Count { get; private set; }

    public PriorityQueue() : this(null) { }
    public PriorityQueue(int capacity) : this(capacity, null) { }
    public PriorityQueue(IComparer
      
        comparer) : this(16, comparer) { } 
     
    public PriorityQueue(int capacity, IComparer
      
        comparer)
       
    {
       
      this.comparer = (comparer == null) ? Comparer
       
        .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 泛型类提供四个公共构造函数，第一个是无参的构造函数，其余的构造函数允许指定优先队列中包括的初始元素数(capacity)、如何对键进行比较(comparer)。

这个程序使用堆(heap)来实现优先队列。所以，所需的空间是最小的。Count 属性和 Top 方法的时间复杂度是 O(1)，Push 和 Pop 方法的时间复杂度都是 O(logN)。

我曾经用 List 泛型类实现过一个优先队列，请参见我的博客 Timus1016. A Cube on the Walk 。虽然更简单，程序代码只有 23 行，但是效率不高，其 Push 和 Pop 方法的时间复杂度都是 O(N)。

【编辑推荐】

  1. 详解C#编程中的反射机制与方法
  2. C#中使用扩展方法对调用进行验证
  3. 详解C#代码文件生成扩展代码文件

网站名称：简述用C#实现优先队列方法
当前地址：https://chengdu.cdxwcx.cn/article/dpiehjj.html

其他资讯