callstack

プログラミングでいろいろやる

ヤング盤

最近,優先度付きキュー(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

やっぱり優先度付きキューじゃないか.訴訟.