あなたの質問に対する簡単な答えは、「バケットにアイテムがあるかどうかを追跡するための追加のデータ構造がない場合」です。
バケットソートを行う方法は複数あります。 「ベスト」は、キーの範囲、アイテムの数、およびユニークな番号の数に大きく依存します。範囲が0〜1,000,000で、50％ユニークであることがわかっている場合は、1,000,000バケットの単一の配列が使いやすく、余分なスペースを無駄にせず、無駄にしません空のバケツを飛び越えるのに多くの時間がかかる。
しかし、あなたは非常にまばらに人口が数百万の範囲を話している場合は、多くのメモリとかなりの時間を空のバケツをスキップすることを無駄になります。極端な場合、範囲全体をカバーするのに十分な大きさの配列を割り当てることさえできません。
バケットソートを実装する別の一般的な方法は、ハッシュマップの辞書を使用することです。アイデアは次のとおりです。もちろん
initialize empty hash map
for each item in list
if key already in hash map
add item to that bucket
else
create new bucket in hash map
、あなたは、あなたが移入終わったらキーでバケットを並べ替えることがありますが、（その場合は）数千バケットをソートすることは些細な時間がかかります。そして、あなたは空のバケツにギガバイトのメモリを無駄にしません。
私はバケットベースの優先度キューを作成しましたが、辞書アプローチを使用しました。私はインデックスでキー入力された辞書を維持し、各項目を適切なバケットに追加しました。私はバケツのシンプルなバイナリヒープを維持しました。だから、ヒープに項目を追加することになりました：
if item.key exists in dictionary
dictionary[item.key].add(item) // adds item to bucket
else
{
dictionary.add(item.key, item) // creates a new bucket
heap.push(dictionary[item.key]) // pushes the bucket onto the heap
}
とヒープから項目を削除するには、次のようになります。
bucket = heap.peek()
item = bucket.getFirst()
if (bucket.count() == 0)
{
// bucket is empty. Remove from heap and from dictionary
heap.pop()
dictionary.remove(item.key)
}
return item
これは非常によく実行されます。私のキーは疎でバケツが大きく詰まっていたので、ヒープ自体には何の効果もありませんでした。ほとんどのアクティビティでは、既にヒープに入っていたバケットに物を追加したり削除したりしていました。ヒープが運動をする唯一の時間は、バケットが空になったときか、新しいバケットを追加したときでした。したがって、平均で、挿入と削除の両方がO（1）に非常に近い。
私のキーの範囲が非常に大きく（10文字の英数字）、個々のアイテムの数が何億も何十億にもなるため、これはうまく機能しましたが、いつでも使用された一意のキーの数は何千というディクショナリの間接参照は若干オーバーヘッドがありますが、それは数千万のアイテムではなく、数千のヒープで作業することの節約によって相殺されます。
ここにあなたが何を求めているのかはわかりません。バケットソートの組み合わせパス中に空のバケットをスキップする方法を質問していますか、効率的なバケットベースの優先キューを作る方法を尋ねていますか？あなたが望むものを理解できるようになる前に、もう少し詳しく説明しなければなりません。 –
@ JimMischel空のバケットを効率的にスキップできれば、バケットベースの優先順位キューを作ることは問題にはなりません。彼らは同じ問題です。 –
バケットベースの優先度キューは問題ありません。使用されているバケットからヒープを構築するだけです。 –