Is it possible to remove elements from PriorityQueue?

Question

Is it possible to remove elements from PriorityQueue?

Documentation:
http://www.scala-lang.org/api/current/index.html#scala.collection.mutable.PriorityQueue
http://www.scala-lang.org/api/current/index.html#scala.collection.Iterator

I have a PQ w various double values (some duplicates) - I use it as a heap to keep track of rolling medians in a streaming environment. I want to remove values from PQ but can't figure out how.
I tried to use the iterator to find an element of the PQ and drop there, but it didn't work. I wonder if it's even possible?

val maxHeapLeft= new mutable.PriorityQueue[Double]()(Ordering[Double])
maxHeapLeft.enqueue(5)
maxHeapLeft.enqueue(55)
maxHeapLeft.enqueue(25)
maxHeapLeft.enqueue(15)
maxHeapLeft.enqueue(15)
val it= maxHeapLeft.iterator
var p1=it.next
p1=it.next

println("size before " +maxHeapLeft.size)
it.drop(1)
println("size AFTER " +maxHeapLeft.size)

Size of PQ doesn't change.

EDIT 1: So far I use maxHeapLeft= new mutable.PriorityQueue[Double]()(Ordering[Double]) ++ (maxHeapLeft.toList diff List(15)) to remove 15 from the PQ. Of course, terrible.

EDIT 2: A test case (for @Nate) that fails for the custom priority queue:

 "PQ" should "produce correct values " in {
    val testOperations = List[String]("8114.0", "9233.0", "dequeue", "10176.0", "10136.0", "dequeue", "10041.0", "9900.0", "10787.0", "10476.0", "10439.0", "dequeue", "10722.0", "9900.0", "11028.0", "10764.0", "dequeue", "10698.0", "10374.0", "dequeue", "-10176.0", "10198.0", "-10136.0", "11478.0", "10930.0", "dequeue", "10881.0", "dequeue", "10555.0", "dequeue", "-10787.0", "10439.0", "-10476.0", "11596.0", "-10439.0", "10757.0", "-10722.0", "10493.0", "10551.0", "dequeue", "-11028.0", "10493.0", "-10764.0", "11892.0", "-10698.0", "11276.0", "10917.0", "dequeue", "15855.0", "dequeue", "12008.0", "dequeue")
    val customPQ= new PriorityQueue[Double]()(Ordering[Double].reverse) //cread min heap

    for (el <-testOperations){
      el match {
        case dequeue if el=="dequeue" => customPQ.dequeue()
        case remove if remove.toDouble < 0 => customPQ -= (-1*remove.toDouble )
        case add => customPQ.enqueue(add.toDouble )
      }
    }

    println(customPQ.head + "==" + customPQ.min)
    println(customPQ)
  }

Test output:
10881.0==10757.0
PriorityQueue(10881.0, 10917.0, 11596.0, 10930.0, 11276.0, 11892.0, 12008.0, 11478.0, 10757.0, 15855.0)

Answer 1

According to the documentation you can only remove elements by clear and dequeue.

Perhaps you'd be happy with a the increased costs of a TreeMultiset to obtain the functionality you seek.

If you wanted to remove a specific value that is in the heap, then you could roll your own starting with the source.

EDIT:

Here is an updated version of PriorityQueue that offers O(n) removal. Here is the relevant added code snippet:

def -=(elem: A): this.type = {
  var k: Int = find(elem)
  resarr.p_size0 = resarr.p_size0 - 1
  resarr.p_swap(k, resarr.p_size0)
  fixUp(resarr.p_array, k)
  fixDown(resarr.p_array, k, resarr.p_size0 - 1)
  this
}

protected def find(elem: A): Int = {
  var k: Int = 1
  while (k < resarr.length) {
    if (resarr.p_array(k) == elem) {
      return k
    }
    k += 1
  }
  throw new NoSuchElementException("element does not exist in heap")
}

I leave adding a MultiMap as an exercise to the reader/OP if he/she desires an O(lg n) removal. (Hint: you will need to update all methods that modify the resarr array.)

Edit 2:

Running it locally:

$ scalac -version 
Scala compiler version
2.11.2 -- Copyright 2002-2013, LAMP/EPFL 

$ md5 PriorityQueue.scala  
MD5 (PriorityQueue.scala) = 3913496441f83bcdeda2249ec2a6b574 

$ scalac PriorityQueue.scala  

$ scala Test 
size before 4 
size after 3

Answer 2

Revise corectness of using PriorityQueue for your task. If you need similar API with unique values use SortedSet.