JavaのPriorityQueueのjavadocは、次のように書いています。 このキューの先頭は、指定された順序に関して最小の要素です。JavaのPriorityQueueは最小の要素を最初に返す
このクラスがヒープとして使用されることが意図されていたか、ヒープ記述に都合よく合うように意図されていたかどうかは知りませんか？ そして、ヒープになっていたのであれば、なぜremove（）によって返される要素が最下位であるのかが混乱しています。なぜなら、「最小」要素が最も優先度が高いか、 'または'最も古い '要素がヒープで使用されていますか？事前に
おかげ
ヒープは、必ずしも最大の要素を返すことを想定されていない優先順位の前に来ると仮定します。これを行うヒープは、最大ヒープと呼ばれます。 Javaヒープは最小ヒープです。順序/比較のステップで小なり記号の代わりに大なり記号を使用する以外は全く同じ構造です。
source code/documentation for PriorityQueueを見て、JLSをスキミングした後、minがmaxを超えて選択された理由を示すものは表示されません。それはちょうどコインフリップに来た可能性がある、または値のグループは、1が頭部であり、可能な限り最小値である1からnになることが多い。
ヒープは、優先度キュー抽象化。 –
ヒープは2種類、最大 - ヒープおよび最小ヒープに来ます。 Java PriorityQueueは最小ヒープを使用するため、head/topは最小の要素です。最小要素はドキュメントの迅速な閲覧から、削除によって返される理由の
ダニエルありがとうございました。これもまた明らかです。 – iralight
優先キューがヒープであることはよくある誤解です。 優先キューは、「リスト」または「マップ」のような抽象的な概念です。リンクリストまたは配列を使用してリストを実装できるように、優先キューは、ヒープまたはさまざまな方法で実装できます。
ありがとう、これはそれを明確にします:) – iralight
「最小要素」は、代数のように抽象的な用語です。これは、定義した特定の順序付けに関する最初の要素を意味します。あなたはあらゆる種類のもの、最大の要素、最も要求された要素などを使用することができます... – UmNyobe
@iralight、私はあなたのお役に立ってうれしいです;私はもう少し研究をした後、答えに移しました。 – Pops