Ist es möglich, Elemente aus PriorityQueue zu entfernen?

Question

Ist es möglich, Elemente aus PriorityQueue zu entfernen?

Dokumentation:
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

Ich habe eine PQ w verschiedene Doppel Werte (einige Duplikate) - Ich benutze es als ein Haufen Spur von Roll Mediane in einer Streaming-Umgebung zu halten. Ich möchte Werte aus PQ entfernen, kann aber nicht herausfinden, wie.
Ich habe versucht, den Iterator zu verwenden, um ein Element der PQ zu finden und dort zu fallen, aber es hat nicht funktioniert. Ich frage mich, ob es überhaupt möglich ist?

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) 

Die Größe von PQ ändert sich nicht.

EDIT 1: Bis jetzt verwende ich maxHeapLeft= new mutable.PriorityQueue[Double]()(Ordering[Double]) ++ (maxHeapLeft.toList diff List(15)), um 15 aus dem PQ zu entfernen. Natürlich, schrecklich.

EDIT 2: Ein Testfall (für @Nate), die für die individuelle Prioritätswarteschlange fehlschlägt:

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

Testausgang:
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

Entsprechend der Dokumentation können Sie nur Elemente durch clear und 012 entfernen.

Vielleicht sind Sie glücklich mit den erhöhten Kosten von TreeMultiset, um die Funktionalität zu erhalten, die Sie suchen.

Wenn Sie einen bestimmten Wert im Heap entfernen möchten, können Sie Ihren eigenen mit der source starten.

EDIT:

Here is an updated version of PriorityQueue die O(n) Entfernung bietet. Hier ist der relevante hinzugefügt Code-Schnipsel:

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

Ich lasse das Hinzufügen einer MultiMap als eine Übung für den Leser/OP, wenn er/sie eine O(lg n) Entfernung wünscht.

Edit 2 (Hinweis: Sie müssen alle Methoden aktualisieren, die die resarr Array ändern.):

Laufen lokal:

$ 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

Revise Richtigkeit der PriorityQueue für Ihre Aufgabe verwenden. Wenn Sie eine ähnliche API mit eindeutigen Werten benötigen, verwenden Sie .

Answer 3

Sie können immer ein einzelnes Element wie so herauszufiltern (in nicht-gleichzeitigen Code):

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

Das heißt, das ist neu erstellt die gesamte Warteschlange (ein Element speichern) jedes Mal, was nicht sein kann, schnell genug für dich.