JavaのPriorityQueueは最小の要素を最初に返す

Question

JavaのPriorityQueueのjavadocは、次のように書いています。 このキューの先頭は、指定された順序に関して最小の要素です。

このクラスがヒープとして使用されることが意図されていたか、ヒープ記述に都合よく合うように意図されていたかどうかは知りませんか？ そして、ヒープになっていたのであれば、なぜremove（）によって返される要素が最下位であるのかが混乱しています。なぜなら、「最小」要素が最も優先度が高いか、 'または'最も古い '要素がヒープで使用されていますか？事前に

おかげ

Answer 1

ヒープは、必ずしも最大の要素を返すことを想定されていない優先順位の前に来ると仮定します。これを行うヒープは、最大ヒープと呼ばれます。 Javaヒープは最小ヒープです。順序/比較のステップで小なり記号の代わりに大なり記号を使用する以外は全く同じ構造です。

source code/documentation for PriorityQueueを見て、JLSをスキミングした後、minがmaxを超えて選択された理由を示すものは表示されません。それはちょうどコインフリップに来た可能性がある、または値のグループは、1が頭部であり、可能な限り最小値である1からnになることが多い。

Answer 2

ヒープは2種類、最大 - ヒープおよび最小ヒープに来ます。 Java PriorityQueueは最小ヒープを使用するため、head/topは最小の要素です。最小要素はドキュメントの迅速な閲覧から、削除によって返される理由の

Answer 3

、私はので、優先度1が2つの

Answer 4

優先キューがヒープであることはよくある誤解です。 優先キューは、「リスト」または「マップ」のような抽象的な概念です。リンクリストまたは配列を使用してリストを実装できるように、優先キューは、ヒープまたはさまざまな方法で実装できます。