PriorityQueue에서 요소를 제거 할 수 있습니까?

Question

PriorityQueue에서 요소를 제거 할 수 있습니까?

문서 : http://www.scala-lang.org/api/current/index.html#scala.collection.Iterator

내가 여러 번 값 (일부 중복) 승 PQ이
이 http://www.scala-lang.org/api/current/index.html#scala.collection.mutable.PriorityQueue
- 나는 스트리밍 환경에서 롤링 중간 값을 추적하기 위해 힙로 사용합니다. 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의 크기는 변경되지 않습니다.

EDIT 1 : 지금까지 나는 012를 PQ에서 제거하려면 maxHeapLeft= new mutable.PriorityQueue[Double]()(Ordering[Double]) ++ (maxHeapLeft.toList diff List(15))을 사용합니다. 물론, 끔찍한.

EDIT 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과 012 만 제거 할 수 있습니다..

아마 당신은 당신이 찾는 기능을 얻기 위해 TreeMultiset의 증가 된 비용에 만족할 것입니다.

힙에있는 특정 값을 제거하려면 source으로 시작하는 고유 한 값을 롤백 할 수 있습니다.

편집 :O(n) 제거를 제공

Here is an updated version of PriorityQueue.

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) 제거를 원한다면 내가 리더/영업 이익 운동으로 MultiMap을 추가로 둡니다 다음은 관련 추가 코드입니다.

편집 2 (힌트 : 당신이 resarr 배열을 수정할 수있는 모든 방법을 업데이트해야합니다.) :

로컬로 실행 : 당신의 작업 PriorityQueue를 사용

$ 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

개정의 corectness. 고유 한 값을 갖는 유사한 API가 필요하면 SortedSet을 사용하십시오.

Answer 3

당신은 항상 (비 동시 코드)과 같이 하나의 요소 필터링 할 수 있습니다 :

말했다

var filtered = false 
pq.filter(x => !filtered && { val ok = p(x); if (!ok) filtered = true; ok }) 

, 이것이 전체 큐 (하나 개의 요소를 저장)마다하지 않을 수 있습니다 재 구축 당신을 위해 충분히 빠릅니다.