配列 a[1]～a[N] で二分木を構成します。
a[1] の子：a[2] と a[3]
a[2] の子：a[4] と a[5]
a[3] の子：a[6] と a[7]
...
a[n] の子：a[2n] と a[2n+1]
んでもってどの要素に対しても
a[n] <= a[2n], a[n] <= a[2n+1]
すなわち「親は(最大)二人の子より大きくない」
を満たすように配置します。
そうすれば当然、大本の親となるa[1]が最小の要素になりますわね。
最小要素a[1]を引っこ抜いたときは、その位置に末端要素a[n]を代入します。
ほんでもって上の条件を満たすように並び変えます。
上記作業にはたいした手間はかかりません。
a[n]の子(a[2n],a[2n+1])のうち、親a[n]より小さな子がいたら、
親と中身を交換し、そいつを親として再度この処理を行います。
この処理の繰り返しは高々log2(N)で完了します。
なんてからくりでこしらえた SortedQueue＜T＞。
要素をEnqueueでパカパカぶっこんでおくと、
小さい順にDequeueしてくれます。
大小の判定はコンストラクト時にdelegateを設定しておきます。
x,yの大小に応じて 負,0,正のint値を返す int f(T x, T y) を設定しといてください。
# επιστημηはSilverBouquetプロジェクトを応援し、SortedQueue＜T＞ を供出します。
# もらってやってください > とりこびっち
----- SortedQueue.cs -----
using System;
using System.Collections.Generic;
namespace SilverBouquet.Collections.Generic {
/// <summary>
/// ソートされたキュー
/// </summary>
/// <typeparam name="T">要素の型</typeparam>
/// <author>επιστημη</author>
/// <contact>episteme@cppll.jp</contact>
/// <publishDate>2007/09/15</publishDate>
/// <lastUpdate>2007/09/15</lastUpdateDate>
/// <version>1.0</version>
public class SortedQueue<T> {
private List<T> heap_;
private Comparison<T> comp_;
/// <summary>
/// コンストラクタ
/// </summary>
/// <param name="comp">比較delegate</param>
public SortedQueue(Comparison<T> comp) {
heap_ = new List<T>();
comp_ = comp;
}
/// <summary>
/// 要素を追加する
/// </summary>
/// <param name="a">追加する要素</param>
public void Enqueue(T a){
heap_.Add(a);
int num = heap_.Count;
int i = num;
int j = i / 2;
while ( i > 1 && comp_(heap_[i-1],heap_[j-1]) < 0 ) {
T t = heap_[i-1];
heap_[i-1] = heap_[j-1];
heap_[j-1] = t;
i = j;
j = i / 2;
}
}
/// <summary>
/// 要素を取り出す。比較delegateに基づき、最小の要素を返す。
/// </summary>
/// <returns>キュー内の最小の要素</returns>
public T Dequeue() {
T r = heap_[0];
int num = heap_.Count;
heap_[0] = heap_[--num];
int i = 1;
int j = i * 2;
while ( j <= num ) {
if ( j+1 <= num && comp_(heap_[j-1],heap_[j]) > 0 ) j++;
if ( comp_(heap_[i-1],heap_[j-1]) > 0 ) {
T t = heap_[i-1];
heap_[i-1] = heap_[j-1];
heap_[j-1] = t;
}
i = j;
j = i * 2;
}
heap_.RemoveAt(heap_.Count-1);
return r;
}
/// <summary>
/// キューを空にする
/// </summary>
public void Clear() { heap_.Clear(); }
/// <summary>
/// キュー内の最小要素
/// </summary>
public T Top { get { return heap_[0]; } }
/// <summary>
/// キュー内の要素数
/// </summary>
public int Count { get { return heap_.Count; } }
/// <summary>
/// キューは空か?
/// </summary>
public bool Empty { get { return heap_.Count == 0; }}
}
}
---- おためし ----
using System;
using SilverBouquet.Collections.Generic;
namespace PriorityQueueTrial {
class Program {
static void Main() {
int[] input = { 1, 3, 5, 7, 9, 0, 2, 4, 6, 8 };
SortedQueue<int> sq =
new SortedQueue<int>(delegate (int x, int y) { return x - y; });
foreach ( int item in input ) sq.Enqueue(item);
while ( !sq.Empty ) {
Console.Write("{0} ", sq.Dequeue());
}
}
}
}