scala - 是否可以从 PriorityQueue 中删除元素？

Question

是否可以从 PriorityQueue 中删除元素？

文档:
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

我有一个带有各种 double 值的 PQ(一些重复) - 我将它用作堆来跟踪流媒体环境中的滚动中位数。我想从 PQ 中删除值，但不知道如何。
我尝试使用迭代器来查找 PQ 的一个元素并放到那里，但是没有用。我想知道这是否可能？

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)

PQ 的大小不会改变。

编辑 1:到目前为止，我使用 maxHeapLeft= new mutable.PriorityQueue[Double]()(Ordering[Double]) ++ (maxHeapLeft.toList diff List(15))从 PQ 中删除 15。当然，可怕。

编辑 2:自定义优先级队列失败的测试用例(对于@Nate):

 "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)
  }

测试输出:
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

根据文档，您只能通过 clear 删除元素和 dequeue .

也许您会对 TreeMultiset 增加的成本感到满意。以获得您所寻求的功能。

如果您想删除堆中的特定值，那么您可以从 source 开始滚动您自己的值。 .

编辑:

Here is an updated version of PriorityQueue提供 O(n)移动。这是相关的添加代码片段:

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")
}

我留下添加 MultiMap如果读者/OP 需要 O(lg n)，作为他/她的练习移动。 (提示:您需要更新所有修改 resarr 数组的方法。)

编辑 2:

在本地运行:

$ 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