「■優先度付きキュー」の編集履歴（バックアップ）一覧はこちら
「■優先度付きキュー」(2014/12/12 (金) 20:36:55) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*情報
作者名：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++だと返り値を返さないけど、このライブラリは返すのが原因)
**・サイズ
データの個数を返します。
*サンプルプログラム
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)ならば
データ[親]＝データ[子]
違えば
データ[親]＝比較値
抜ける。
親＝子。
返値で戻る
・トップポップ～
返値とは変数
返値＝トップ
ポップ
返値で戻る
----
#comment()
----
*情報
作者名：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)ならば
データ[親]＝データ[子]
違えば
データ[親]＝比較値
抜ける。
親＝子。
返値で戻る
・トップポップ～
返値とは変数
返値＝トップ
ポップ
返値で戻る
----
#comment()
----
