Fila Prioritária remove o tempo de complexidade

Qual é a complexidade (big-oh) para oremove() função na classe Priority Queue em Java? Eu não consigo encontrar nada documentado em lugar algum, eu acho que é O (n), considerando que você tem que encontrar o elemento antes de removê-lo e então reorganizar a árvore. mas eu vi outros que discordam e acham que é O (logn). Alguma ideia?