java - JAVA-PriorityQueueの実装

Question

Javaは、PriorityQueueオブジェクトの実装で、ヒープを使用します。実装（Javaによる）は、poll（）操作の後の「heapify」操作（たとえば、別のスレッドによる）と並行していますか？

前もって感謝します。

Answer 1

heapify操作は、一度に1つの要素のみを考慮し、それをシンクまたはシフトアップします。並列化する方法がわかりません。

それでも、コードを見てみませんか？

編集：私は今、少なくともopenjdkの実装について確信しています

Answer 2

いいえ、それはそれを並列化しません。アルゴリズムはそのように設計されていません。

さらに、操作全体が終了するのを待つ必要があるため、コンピューターが待機する必要がある重要なコードブロックがあった場合（たとえば、Webページの取得）にのみ、マルチスレッド化の利点が得られることを考慮してください。 。これは明らかにヒープには当てはまらないので、それによるメリットはありません。

もう1つ：マルチスレッドが含まれている場合は常に、支払う代償もあります。メンテナンスがより複雑になり、スレッドのインスタンス化やロック管理などにCPU時間が費やされます...

この場合、それは役に立ちません。別の問題は、複数のコンピューターに分散して機能する必要があるデータ構造が必要な場合です。その場合、分散バリアントを開発する必要がありますが、それは、並列化のメリットがデータの分散に伴うオーバーヘッドを上回る場合に限られます。