Ce qui est grand O de java priorityQueue poll() la méthode

J'ai vérifié http://en.wikipedia.org/wiki/Priority_queue
il a dit Naïf implémentations est o(n).

Si je utiliser les binaires de recherche, il sera log(n). Mais je ne suis pas sûr s'il est utilisé en Java.
Et comment puis-je utiliser les binaires de recherche sur un priorityQueue?

Grâce.

Êtes-vous juste de poser des questions sur la mise en œuvre de Java poll? Il y a pas de substitut de la lecture de la source. Bien sûr, le documentation générale déjà les réponses à cette question particulière.
PriorityQueues sont normalement à l'aide de Tas implémentations pour de bonnes raisons. Si Java n'.

OriginalL'auteur user2547667 | 2013-10-31

  1. 28

    De la PriorityQueue Javadoc:

    Mise en œuvre remarque: cette application fournit O(log(n)) temps pour
    le enqueing et dequeing méthodes (offer, poll, remove() et
    add); le temps linéaire de la remove(Object) et contains(Object)
    méthodes; et de la constante de temps pour la récupération de méthodes (peek,
    element, et size).

    Files d'attente de priorité sont généralement mis en œuvre à l'aide d'un tas. Si elles sont appliquées comme un tableau trié, la tête peut être consulté et retiré en O(1) car il est toujours le dernier élément*, mais l'insertion de nouveaux éléments est O(n) depuis le point d'insertion doit être trouvé (ce qui peut être fait en O(log(n)) à l'aide d'une recherche binaire) et ensuite tous les éléments postérieurs doivent être déplacés pour faire de la place, qui est O(n).

    * en Supposant que la tête est le plus petit élément et le tableau est trié dans l'ordre décroissant.

    OriginalL'auteur tom