java - javaのpriorityQueue poll()メソッドのビッグオーとは

Question

http://en.wikipedia.org/wiki/Priority_queueを確認 したところ、単純な実装は o(n) であることがわかりました。

バイナリ検索を使用すると、log(n) になります。しかし、Javaで使用されているかどうかはわかりません。また、priorityQueue でバイナリ検索を使用するにはどうすればよいですか?

ありがとう。

Answer 1

PriorityQueue Javadocから:

実装に関する注意: この実装は、エンキューおよびデキュー メソッド ( 、、および ) にO(log(n))時間を提供します。および メソッドの線形時間。検索方法 ( 、 、および) の定数時間。offerpollremove()addremove(Object)contains(Object)peekelementsize

プライオリティ キューは通常、ヒープを使用して実装されます。ソートされた配列として実装されている場合、ヘッドは常に最後の要素*であるため、O(1) で検索して削除できますが、挿入ポイントを見つける必要があるため、新しい要素の挿入は O(n) になります (バイナリ検索を使用して O(log(n)) で実行されます)、その後のすべての要素は、O(n) のスペースを確保するためにシフトする必要があります。

^{* head が最小要素で、配列が降順でソートされていると仮定します。}