ヤング盤
最近,優先度付きキュー(Priority Queue)に興味があったので色々調べていたら,
ヤング盤(young tableau)というものを見つけました.
有名なあの書物で,ヒープソートの章の練習問題で出てくるらしいですね.
詳細は他の文献に譲るとして,定義は以下の通り.
ヤング盤は、ヤング図形を一つ取り、同図形の n 個の箱に 1, 2, …, n の数を、以下の制約に基づいて埋めることによって得られる。
- 各行で、数は左から右に増加する。
- 各列で、数は上から下に増加する。
(出典:Wikipedia)
例えば3x3の表で配列A=[5, 3, 2, 1, 4]が与えられたとして,
1 | 3 | 5 |
2 | 4 | - |
- | - | - |
みたいな感じですかね.上の定義でいくと,与えられた配列を昇順ソートして,
1 | 2 | 3 |
4 | 5 | - |
- | - | - |
のように入れてもヤング盤といえます.
並べ方は色々ありますが,共通しているのは左上の要素が最小値になることですね.
なんか面白そうなので勉強がてら実装しました.言語はRuby(2.3.0).
https://gist.github.com/rk0der/411a73309e3c10b91250ce9592237581
値の追加(insert)と最小値の取り出し(extract)を実装しました.
これらの操作後は再構築が実行されるので,常にヤング盤が維持されます.
上のプログラムは
m n a1 a2 ...
という入力をとり, m × n の表を作り,そこにa1, a2, ... から成る配列を元にヤング盤を構築します.
ruby young_tableau.rb 3 3 5 3 2 1 4 1 2 3 4 5
やっぱり優先度付きキューじゃないか.訴訟.