Skip to content
June 9, 2013 / windperson

C#實作支援foreach語法的Priority Queue

使用〝Binary Heap〞這種資料結構在C#上實作一個Priority Queue,程式碼如下:

public partial class BinaryHeapPriorityQueue<T> where T : IComparable<T>
{
    private List<T> _storeData;

    public BinaryHeapPriorityQueue()
    {
        _storeData = new List<T>();
    }

    public int Count
    {
        get { return _storeData.Count; }
    }

    #region Queue operation method
    public void Enqueue(T item)
    {
        _storeData.Add(item);
        var childIndex = _storeData.Count - 1;
        while (childIndex > 0)
        {
            var parentIndex = (childIndex - 1)/2;
            if (_storeData[childIndex].CompareTo(_storeData[parentIndex]) >= 0)
            {
                break;
            }

            _storeData.Swap(parentIndex, childIndex);

            childIndex = parentIndex;
        }
    }

    public T Dequeue()
    {
        if (_storeData.Count <= 0)
        {
            return default(T);
        }

        //fetch 1st item as return data
        //and move last one to front inorder to do heapify
        var retItem = _storeData[0];
        
        var lastIndex = _storeData.Count - 1;
        _storeData[0] = _storeData[lastIndex];
        _storeData.RemoveAt(lastIndex);

        Heapify();

        return retItem;
    }
    #endregion

    #region private method
    private void Heapify()
    {
        var lastIndex = _storeData.Count - 1;
        var parentIndex = 0;
        do
        {
            var leftChildIndex = parentIndex * 2 + 1;
            if (leftChildIndex > lastIndex) { break; }
            var rightChildIndex = leftChildIndex + 1;

            if (rightChildIndex <= lastIndex
                && _storeData[rightChildIndex].CompareTo(_storeData[leftChildIndex]) < 0)
            {
                leftChildIndex = rightChildIndex;
            }

            if (_storeData[parentIndex].CompareTo(_storeData[leftChildIndex]) <= 0)
            {
                break;
            }
            _storeData.Swap(parentIndex, leftChildIndex);

            parentIndex = leftChildIndex;
        } while (true);
    }
    #endregion
}

  • 第16行Enqueue()-將資料物件加入至Priority Queue,加入資料時執行〝bubble-up〞的動作:逐次和其Parent元素比較,如果發現插入的元素Priority比Parent元素高的話,就調換Parent-Child的元素,一直比較到最頂端的根部元素,如此以便讓Binary Heap的最根部元素為Priority最高(Priority權數最小)的成員元素。

  • 第34行Dequeue()-取出Binary Heap根部元素,也就是Priority最高(Priority權數最小)的成員元素並傳回,但在傳回之前須執行〝Heapify〞的動作,來『整理』整個Binary Heap結構,讓此Binary Heap的根部元素為移除掉原本做為傳回值的最高優先順序元素之後,擁有第二優先順序的成員元素。
  • 第56行Heapify()-由於原本在Dequeue()時,將最尾端的元素移到最根部當作暫時的根部元素,使得原本Binary Heap的特性(每個視為parent元素的成員需比其left child及right child元素在比較特性上大,在這邊就是Priority需比其left child和right child大)被破壞,需要從現在這個暫時的最高根部元素開始,比較其left child和right child元素,如果發現是目前這個parent元素的Priority已經和left child及right child比較起來是最高的,就不需繼續進行整理的動作而可以結束此函式;相反地,則須從這三者中最高Priority的元素和parent元素交換,然後再從剛剛交換的位置當作下一次比較的parent元素,繼續整理下去直到到達最後一個儲存在底層用array存的元素。

    在這裡有使用C# 3.0之後的”Extension Methods“語法,讓List這個類別在程式撰寫時的語法上可以額外支援一個自訂調換元素成員的Swap()擴充方法,程式碼如下:

    static class ListExtension
    {
        public static IList<T> Swap<T>(this IList<T> list, int indexA, int indexB)
        {
            T tmp = list[indexA];
            list[indexA] = list[indexB];
            list[indexB] = tmp;
            return list;
        }
    }
    

    由於這個ListExtension類別是寫在BinaryHeapPriorityQueue類別所在的.cs檔內的同一個namespace範圍底下,所以可以不用using語法宣告就直接使用。

此Priority Queue類別在使用時就可以呼叫Enqueue()的方法加入自訂類型的元素,然後要取出最高優先權的就用Dequeue()來得到,例如下面這個WorkItem類別:

class WorkItem : IComparable<WorkItem>
{
    public string ItemName { get; set; }
    public int Priority { get; set; }

    #region IComparable interface
    public int CompareTo(WorkItem other)
    {
        int ret;
        if (Priority < other.Priority)
        {
            ret = -1;
        }
        else if (Priority == other.Priority)
        {
            ret = 0;
        }
        else
        {
            ret = 1;
        }
        return ret;
    }
    #endregion

    public override string ToString()
    {
        return "(" + ItemName + " : " + Priority.ToString("D2") + ")";
    }
}

就可以如下面這樣的範例來使用:

var priorityQueue = new BinaryHeapPriorityQueue<WorkItem>();
var rand = new Random();

for (var i = 1; i <= 10; i++)
{
    var item = new WorkItem
        {
            ItemName = "item" + i.ToString("D2"),
            Priority = rand.Next(11)
        };
    priorityQueue.Enqueue(item);
}

var capacity = priorityQueue.Count;
for (var i = 0; i < capacity; i++)
{
    var item = priorityQueue.Dequeue();
    Console.WriteLine(item);
}

要讓此Priority Queue類別支援C#的foreach語法的話,須在類別宣告上增加一個C#類別庫中定義的IEnumerable介面:

public partial class BinaryHeapPriorityQueue : IEnumerable where T : IComparable

可使用Partial Classes的語法,將額外增加實作IEnumerable介面的程式碼寫在另一個.cs檔,如下:

public partial class BinaryHeapPriorityQueue<T> : IEnumerable<T> where T : IComparable<T>
{
    public IEnumerator<T> GetEnumerator()
    {
        return new BinaryHeapEnumerator(this);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    private class BinaryHeapEnumerator : IEnumerator<T>
    {
        private readonly BinaryHeapPriorityQueue<T> _origin;
        private BinaryHeapPriorityQueue<T> _transit;

        private int _position = -1;

        public BinaryHeapEnumerator(BinaryHeapPriorityQueue<T> aggregate)
        {
            _origin = CopyAggregate(aggregate);
        }

        #region IEnumerator<T> implementation
        public void Dispose()
        {
            //do nothing
        }

        public bool MoveNext()
        {
            if (_transit == null)
            {
                _transit = CopyAggregate(_origin);
            }

            Current = _transit.Dequeue();
            _position++;
            return _position < _origin.Count;
        }

        public void Reset()
        {
            _transit = null;
            _position = -1;
        }

        public T Current { get; private set; }

        object IEnumerator.Current
        {
            get { return Current; }
        }
        #endregion

        private static BinaryHeapPriorityQueue<T> CopyAggregate(BinaryHeapPriorityQueue<T> aQueue)
        {
            var copy = new BinaryHeapPriorityQueue<T> { _storeData = aQueue._storeData.ToList() };
            return copy;
        }
    }
}

IEnumerable介面只有定義一個GetEnumerator()方法,對應到GoF的迭代器模式就是Aggregate介面的CreateIterator()方法:

IEnumerator<T> GetEnumerator()

這個介面宣告方法的實作只有回傳一個自定義的BinaryHeapEnumerator類別的物件,該類別有實作C#類別庫中定義的IEnumerator介面,此介面就是對應到GoF的迭代器模式的Iterator介面;而下方的

IEnumerator IEnumerable.GetEnumerator()

是為了和.net 2.0之前無支援泛型的版本相容而在IEnumerable介面裡還留著的舊式方法,所以在該方法實作上就直接傳回呼叫GetEnumerator()方法的結果即可。

13~62行自定義的BinaryHeapEnumerator類別是一個包含在BinaryHeapPriorityQueue類別中的私有內部類別(Nested Class),如此可確保能產生該BinaryHeapEnumerator類別物件的方法只有從BinaryHeapPriorityQueue類別的GetEnumerator()取得而沒有其他方式,才不會讓此類別物件被誤用在其他的聚合類別物件上。

一開始這個BinaryHeapEnumerator類別的建構子依循GoF的迭代器模式中所敘述的,產生該類別的物件時須將要讀取內容的聚合類別的物件傳入,而在此實作中,將傳入的Priority Queue利用CopyAggregate()這個方法把原始物件拷貝一份存起來。

第57行CopyAggregate()的實作中,由於此方法是在BinaryHeapPriorityQueue這個外部類別裡面的內部類別,所以可以存取到外部類別的私有變數,因此,可以藉由此特殊權限在這裡呼叫外部類別的建構子產生外部類別的物件時,順便指定該外部類別物件的私有變數內容,達到如同呼叫了外部類別的拷貝建構子(Copy constructor)的效果,即使外部類別沒有拷貝建構子的宣告與實作。

第26行Dispose()方法是.net類別庫在設計時,顧及到可能會有Enumerator的實作不是去存取聚合類別的成員元素,而是去實際讀取資料庫或是檔案系統的內容,而讓IEnumerator介面繼承IDisposable介面而有的方法宣告,因此在實作上該方法不必做任何事情。

第31行MoveNext()方法同等於GoF迭代器模式的IsDone()和Next()方法,在實作上,將原本的Priority Queue拷貝到一個實際操作的_transit物件上,對該_transit物件實際執行Dequeue的動作來取得下一個成員元素,並且將讀取的「游標」(_position),指向下一個,並檢查是否已經超過原本原始Priority Queue所承載的容量,來當作MoveNext()的結果。

第43行Reset()方法同等於GoF迭代器模式的First()方法,只是該方法沒有回傳第一個成員元素的值。

第49行Current屬性(Property)同等於GoF迭代器模式的CurrentItem()方法,由於要相容.net 2.0之前的無泛型版本的介面宣告,因此在下方有一個IEnumerator.Current的無泛型版本。

經過這樣的修改之後,原本上面的使用範例就可以改成用foreach語法的方式來讀取:

foreach (var workItem in priorityQueue)
{
    Console.WriteLine(workItem);
}

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: