优先队列(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 属性和