¿Cómo restaurar PriorityQueue a su estado inicial antes de la llamada al método?

Estoy haciendo un problema de práctica Practica IT Kth Smallest

Este problema es básicamente que pasaste en una PriorityQueue y en una cierta k, y debes devolver el k-ésimo valor más pequeño en esa PriorityQueue. También debe restaurar PriorityQueue a su estado inicial y puede usar una stack o cola como estructura de datos auxiliares.

Mi pseudo pensamiento de nivel superior es que debido a que PriorityQueue ya actúa como un montón mínimo, desde Java PriorityQueue , todo lo que realmente tengo que hacer (mi algoritmo) es:

  1. Elimina k elementos de PriorityQueue

  2. Almacena el k-ésimo valor más pequeño como variable local

  3. Empuje los elementos k eliminados en una stack (astackr para poder agregar elementos en el mismo orden)

  4. Coloca todos los elementos de la stack y vuelve a agregarlos a PriorityQueue

  5. Devuelve el k-ésimo valor más pequeño

Aquí está el código para hacer todo eso:

public int kthSmallest(PriorityQueue pQ, int k) { if(k  pQ.size()) { throw new IllegalArgumentException(); } else { Stack aux = new Stack(); 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; } } 

Cuando ejecuto el progtwig obtengo todos los resultados correctos, en términos de kth más pequeño, pero no puedo restaurar el estado de mi PriorityQueue. Por ejemplo, al pasar en una Prioridad de:

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

… mi algoritmo produce el resultado correcto, 17, pero cambia el estado de PriorityQueue a [-3, 17, 9, 81, 22, 42] , lo cual es inesperado.

Pensé en hacer una copia de PriorityQueue pero eso viola una de las condiciones, “puedes usar una stack o cola como una estructura de datos auxiliar”.

¿Cómo puedo restaurar el estado de PriorityQueue?

Dos cosas deben ajustarse en su implementación. En primer lugar, debe usar una cola, en lugar de una stack, como estructura de datos auxiliares. Si inserta elementos en una stack y los vuelve a abrir, se volverán a agregar a la cola de prioridad en orden inverso . Si salen de la cola de prioridad como 1, 2, 3 , se agregarán nuevamente a la cola de prioridad como 3, 2, 1 . Esto se debe a que las stacks son una estructura de datos LIFO (último en entrar, primero en salir). Desea utilizar una cola como su estructura de datos auxiliares porque es una estructura de datos FIFO (Primero en entrar, primero en salir), por lo que conservará el mismo orden.

En segundo lugar, solo extrae los primeros k elementos de la lista priorty. Recomendaría agotar toda la cola, de modo que esté agregando todos los elementos nuevamente en la cola en el orden en que salieron, en lugar de solo algunos.

En otras palabras, ajustaría su progtwig de la siguiente manera:

 public int kthSmallest(PriorityQueue pQ, int k) { if(k <= 0 || k > pQ.size()) { throw new IllegalArgumentException(); } else { Queue aux = new ArrayDeque(); int kThSmallest = -1; for(int c=0;c 

Nota: Cambié la variable 'elemento' en su progtwig de tipo int a Integer . No importa la corrección de su progtwig, pero es un buen hábito prestar atención al auto-boxeo. Los tipos generics, como las colecciones, usan enteros encuadrados . Este es un objeto que almacena el entero primitivo. La asignación de un entero encuadrado a algo de tipo int requiere que se desagrupe, es decir, se vuelva a convertir en una primitiva de tipo int . Esto no es gran cosa, excepto que inmediatamente está volviendo a agregar este valor a una colección. Como lo has desempaquetado en un int primitivo, se debe volver a encajonar en un Integer , y eso requiere que el sistema cree un objeto para almacenarlo. Dado que todo lo que estás haciendo con el valor es sacarlo de y volver a ponerlo en colecciones, es mejor usar un valor Integer aquí, para evitar el desempaquetado y el valor del boxeo, ya que no es realmente necesario.