用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<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)。