是否可以从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
我有一个PQ w各种双值(一些重复) - 我用它作为一个堆来跟踪流媒体环境中的滚动中位数.我想从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)
根据文档,您只能通过clear
和删除元素dequeue
.
也许您会对TreeMultiset
获得所需功能的成本增加感到满意.
如果要删除堆中的特定值,则可以从源开始滚动自己的值.
编辑:
这是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
如果他/她希望O(lg n)
移除,我会向读者/ OP 添加一个练习.(提示:您需要更新修改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