title: Scala: can PriorityQueue.update be used efficiently to decrease keys?
body: <p>Priority queues support a 'decrease key' operation (<a href="https://en.wikipedia.org/wiki/Priority_queue#Summary_of_running_times" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Priority_queue#Summary_of_running_times</a>), it is needed for a number of best first search type algorithms. It should run in O(log n) time. Does scala.collection.mutable.PriorityQueue support this efficiently?  </p>
  
  <p>Looking through the API docs the closest thing I can find is</p>
  
  <pre><code>def update (idx: Int, elem: A) : Unit
  Replaces element at given index with a new value.
  </code></pre>
  
  <p>But there are two potential problems with this… firstly one has to find the element and it's not clear what the time complexity of <code>findIndexOf</code> is.* Second it looks like <code>update</code> allows the value to be increased as well as decreased; it's not clear whether that can be implemented efficiently.</p>
  
  <p>*See e.g. <a href="https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu">How to implement O(logn) decrease-key operation for min-heap based Priority Queue?</a> for proof that this can be done efficiently.</p>
  
  <p>Does anyone know what the time complexity of update is?</p>