Bucket queue とは

データ構造の設計および分析では、バケット・キュー(バケット優先順位キューまたは有界高優先順位キューとも呼ばれる)は、優先順位が小さい整数である要素を優先順位付けする優先順位キューです。それはバケットの配列の形をしています:配列データ構造は優先順位によってインデックス付けされ、そのセルには互いに同じ優先順位の項目のバケットが含まれています。
バケットキューは、ハッシュソートソート(バケットソートとも呼ばれます)のプライオリティキューアナログです。ソートアルゴリズムは、要素を優先順位によってインデックス付けされたバケットに配置し、バケットを連結します。選択ソートで優先度キューとしてバケット・キューを使用すると、ピジョンホール・ソート・アルゴリズムの形式が得られます。
バケットキューのアプリケーションには、グラフの縮退の計算と、最短パスの高速アルゴリズムと、小さな整数または既にソートされているウェイトを持つグラフの最も広いパスが含まれます。その最初の使用はDial(1969)の最短経路アルゴリズムであった。