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

发布时间：2020-12-16 19:19:10 所属栏目：安全来源：网络整理

导读：是否可以从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各种双值(一些重复) –

是否可以从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","10041.0","9900.0","10787.0","10476.0","10439.0","10722.0","11028.0","10764.0","10698.0","10374.0","-10176.0","10198.0","-10136.0","11478.0","10930.0","10881.0","10555.0","-10787.0","-10476.0","11596.0","-10439.0","10757.0","-10722.0","10493.0","10551.0","-11028.0","-10764.0","11892.0","-10698.0","11276.0","10917.0","15855.0","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的成本增加感到高兴,以获得您所寻求的功能.

如果要删除堆中的特定值,则可以从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")
}

如果他/她希望移除O(lg n),我会向读者/ OP添加一个MultiMap作为练习. (提示：您需要更新修改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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!