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

 嫣嫣细语dingdingjq 发布于 2022-12-12 20:26

是否可以从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)

1 个回答
  • 根据文档,您只能通过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
    

    2022-12-12 20:33 回答
撰写答案
今天,你开发时遇到什么问题呢?
立即提问
热门标签
PHP1.CN | 中国最专业的PHP中文社区 | PNG素材下载 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有