簡述用C#實現優先隊列方法

　　優先隊列(priority queue) 是很重要的數據結構我在做 ACM 題時就經常要用到她C++ STL 就包括 priority_queue Java 也有 PriorityQueue 類遺憾的是NET Framework Base Class Library 中並不包括優先隊列於是我只好自己用 C# 語言寫一個如下所示

using　System;
using　SystemCollectionsGeneric;

namespace　SkyivUtil
{
　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(　comparer)　{　}

　　public　PriorityQueue(int　capacity　IComparer<T>　comparer)
　　{
　　　thiscomparer　=　(comparer　==　null)　?　Comparer<T>Default　:　comparer;
　　　thisheap　=　new　T[capacity];
　　}

　　public　void　Push(T　v)
　　{
　　　if　(Count　>=　heapLength)　ArrayResize(ref　heap　Count　*　);
　　　heap[Count]　=　v;
　　　SiftUp(Count++);
　　}

　　public　T　Pop()
　　{
　　　var　v　=　Top();
　　　heap[]　=　heap[Count];
　　　if　(Count　>　)　SiftDown();
　　　return　v;
　　}

　　public　T　Top()
　　{
　　　if　(Count　>　)　return　heap[];
　　　throw　new　InvalidOperationException(優先隊列為空);
　　}

　　void　SiftUp(int　n)
　　{
　　　var　v　=　heap[n];
　　　for　(var　n　=　n　/　;　n　>　　&&　comparerCompare(v　heap[n])　>　;　n　=　n　n　/=　)　heap[n]　=　heap[n];
　　　heap[n]　=　v;
　　}

　　void　SiftDown(int　n)
　　{
　　　var　v　=　heap[n];
　　　for　(var　n　=　n　*　;　n　<　Count;　n　=　n　n　*=　)
　　　{
　　　　if　(n　+　　<　Count　&&　comparerCompare(heap[n　+　]　heap[n])　>　)　n++;
　　　　if　(comparerCompare(v　heap[n])　>=　)　break;
　　　　heap[n]　=　heap[n];
　　　}
　　　heap[n]　=　v;
　　}
　}
}

　　如上所示這個

PriorityQueue<T>

　　泛型類提供四個公共構造函數第一個是無參的構造函數其余的構造函數允許指定優先隊列中包括的初始元素數(capacity)如何對鍵進行比較(comparer)

　　這個程序使用堆(heap)來實現優先隊列所以所需的空間是最小的Count 屬性和 Top 方法的時間復雜度是 O()Push 和 Pop 方法的時間復雜度都是 O(logN)

　　我曾經用 List<T> 泛型類實現過一個優先隊列請參見我的博客 Timus A Cube on the Walk 雖然更簡單程序代碼只有 行但是效率不高其 Push 和 Pop 方法的時間復雜度都是 O(N)

From:http://tw.wingwit.com/Article/program/net/201311/15388.html