■優先度付きキュー

※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

情報

作者名:1.0e+21 (@TumoiYorozu)

概要

なでしこ用の優先度付きキュー(priority queue)です。
キューに入れた要素をいい感じにソート(並び替え)して、最大値(カスタム可能)を取り出すことが可能です。
二分ヒープによる実装で、要素の挿入・削除をO(log n)で、先頭の参照はO(1)で行うことができます。

優先度付きキュー(priority queue)について詳しくは、Wikipedia等を御覧ください。
http://ja.wikipedia.org/wiki/%E5%84%AA%E5%85%88%E5%BA%A6%E3%81%A4%E3%81%8D%E3%82%AD%E3%83%A5%E3%83%BC

デフォルトでは降順(大きい順)ですが、内部の比較(A,B)関数を上書きすることで、カスタマイズできます。
要素が空の状態でトップ・ポップした場合、NILを返します。


解説

・初期化~

初期化します。意識しなくても、作った時に勝手に呼ばれます。

・プッシュ(V|Vを)~

変数Vをキューに入れます。
Vはデフォルトで整数・実数に対して有効ですが、後述の操作で文字列や配列等も挿入可能です。
O(log n)時間かかります。

・トップ~

ソートした際の最上位の値を返します。
つまり、デフォルトでは降順なので、最大の値が返ります。
O(1)時間かかります。

・ポップ~

ソートした際の最上位の変数を削除します。
返り値は、削除した値になります。
O(log n)時間かかります。

・トップポップ~

トップの操作をし、ポップの操作をします。トップの返り値を返ります。
が、実質的にポップと同じ動作です。
(ここらへんはC++の仕様とか習わし的な何かを模した結果)
(てか、ポップがC++だと返り値を返さないけど、このライブラリは返すのが原因)

・サイズ

データの個数を返します。

・比較(A,B)~

比較のための関数です。
デフォルトでA-Bで比較するので、整数・実数にのみ有効です。
文字列や配列等の比較をするには、後述の比較関数の上書きが必要です。(要サンプルプログラム2参照)

サンプルプログラム

Qとは優先度付きキュー


4をQがプッシュ	//4
1をQがプッシュ	//4,1

Qのトップを表示	//4,1の中で4が一番大きいから「4」が表示される
Qがポップを表示	//「4」を表示して、4を削除

5をQがプッシュ	//1,5
7をQがプッシュ	//1,5,7

Qがトップポップを表示	//「7」が表示

2をQがプッシュ	//1,2,5

Qがポップを表示	//「5」が表示

「サイズ:{Qのサイズ}」を表示	//1,2なのでサイズは「2」

Qがポップを表示	//「2」
Qがポップを表示	//「1」

「サイズ:{Qのサイズ}」を表示

Qのトップの変数型確認を表示		//存在しないのに呼び出したからNILが返却

サンプルプログラム2(カスタムソート)

*Qの比較(A,B)
などのように比較関数を上書きすることにより、オリジナルのソートが可能です。
関数の返り値は整数か実数である必要があり、「正の数」か、「負またはゼロ」で大小が判断されます。
Qとは優先度付きキュー

Qに2をプッシュ	//2
Qに8をプッシュ	//2,8
Qに5をプッシュ	//2,8,5

Qのポップを表示	//「2」 残り:8,5
Qのポップを表示	//「5」 残り:8
Qのポップを表示	//「8」

*Qの比較(A,B)
	B-Aで戻る	//昇順(小さい順)

Qとは優先度付きキュー

日付一覧は「ひな祭り,2005/03/03
こどもの日,2005/05/05
初詣に行く,2005/01/01」

Qに日付一覧[0]をプッシュ
Qに日付一覧[1]をプッシュ
Qに日付一覧[2]をプッシュ

Qのポップを表示		//こどもの日,2005/05/05
Qのポップを表示		//ひな祭り,2005/03/03
Qのポップを表示		//初詣に行く,2005/01/01

*Qの比較(A,B)
	B【1】とA【1】の日数差



本体

■優先度付きキュー
	・{非公開}データ
	・{非公開}Fサイズ
	・サイズ	→GETサイズ
	・GETサイズ~Fサイズで戻る
	・比較(A,B)~
		A-Bで戻る
	・作る~
		初期化
	・初期化~
		データ=『』
		Fサイズ=0
	・プッシュ(V|Vを)~
		親とは整数
		子とは整数=Fサイズ
		1の間
			親=INT((子-1)/2)
			もし、(比較(V,データ[親])>0)ならば
				データ[子]=データ[親]
			違えば
				データ[子]=V。抜ける。
			もし、親=0ならば
				データ[親]=V。抜ける。
			子=親
		Fサイズ=Fサイズ+1
	・トップ~
		データ[0]で戻る
	・ポップ~
		親とは整数
		子とは整数
		比較値とは変数
		返値とは変数
		返値=トップ
		もし、Fサイズ=0ならば
			返値で戻る
		親=0
		Fサイズ=Fサイズ-1
		データ[0]=データ[Fサイズ]
		データのFサイズを配列削除
		比較値=データ[0]
		
		1の間
			もし、(親*2+2<Fサイズ)ならば
				もし、(比較(データ[親*2+1],データ[親*2+2])>0)ならば
					子=親*2+1
				違えば
					子=親*2+2
			違えば、もし、(親*2+2=Fサイズ)ならば
				子=親*2+1
			違えば
				データ[子]=比較値
				抜ける。
			もし、(比較(データ[子],比較値)>0)ならば
				データ[親]=データ[子]
			違えば
				データ[親]=比較値
				抜ける。
			親=子。
		返値で戻る
	・トップポップ~
		返値とは変数
		返値=トップ
		ポップ
		返値で戻る



名前:
コメント:


ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。