Ich mache ein ÜbungsproblemPractice IT Kth Kleinste

Dieses Problem ist, dass Sie in einer PriorityQueue und einem bestimmten k übergeben werden und den k-kleinsten Wert in dieser PriorityQueue zurückgeben müssen. Sie müssen die PriorityQueue auch in den Ausgangszustand zurückversetzen und können einen Stapel oder eine Warteschlange als Hilfsdatenstruktur verwenden.

Mein übergeordnetes Pseudo-Denken ist, dass, weil die PriorityQueue bereits als Min-Heap fungiert, vonJava PriorityQueue, alles was ich wirklich tun muss (mein Algorithmus) ist:

Entfernen Sie k Elemente aus der PriorityQueue

Speichere den k-ten kleinsten Wert als lokale Variable

Push entfernte k Elemente auf einen Stapel (Stapel, damit ich Elemente in der gleichen Reihenfolge hinzufügen kann)

Pop alle Elemente aus dem Stapel und fügen Sie sie wieder in die PriorityQueue

Rückgabe des k-ten kleinsten Wertes

Hier ist der Code, um all das zu tun:

public int kthSmallest(PriorityQueue<Integer> pQ, int k) {
    if(k <= 0 || k > pQ.size()) {
           throw new IllegalArgumentException();
    } else {
         Stack<Integer> aux = new Stack<Integer>();
         int kThSmallest = -1;
         for(int c=0;c<k;c++){
               int element = pQ.remove();
               if(c == k-1) 
                   kThSmallest = element;
               aux.push(element);
          }
          while(!aux.isEmpty())
              pQ.add(aux.pop());
         return kThSmallest;
      }    
}

Wenn ich das Programm ausführe, erhalte ich die richtigen Ausgaben, bezogen auf kth tiny, aber ich kann den Status meiner PriorityQueue nicht wiederherstellen. Zum Beispiel, wenn eine PriorityQueue übergeben wird von:

[-3, 9, 17, 22, 42, 81] with a k of 3

... mein Algorithmus erzeugt das richtige Ergebnis, 17, ändert aber den Status von PriorityQueue in[-3, 17, 9, 81, 22, 42], was unerwartet ist.

Ich habe darüber nachgedacht, eine Kopie der PriorityQueue zu erstellen, aber das verstößt gegen eine der Bedingungen: "Sie können einen Stapel oder eine Warteschlange als Hilfsdatenstruktur verwenden."

Wie kann ich den Status der PriorityQueue wiederherstellen?