Как восстановить приоритет PriorityQueue до его начального состояния перед вызовом метода?

Question

Я делаю проблемы практики Practice IT Kth Smallest

Эта проблема в основном вы прошли в PriorityQueue и некоторого к, и вы должны вернуть -ю наименьшее значение в этом PriorityQueue. Вы также должны восстановить PriorityQueue в исходное состояние и можете использовать один стек или очередь в качестве вспомогательной структуры данных.

Мой высокий уровень псевдо мышления является то, что, поскольку PriorityQueue действует как мин кучи уже с Java PriorityQueue, все, что я действительно должен сделать (мой алгоритм) является:

1. Снимите к элементов из PriorityQueue

2. магазин -й наименьшее значение в качестве локальной переменной

3. Нажимные удалены к элементов на стек (стек таким образом я могу добавить элементы в том же порядке)

4. Поп все элементы из стека и повторно добавить их обратно в PriorityQueue

5. Вернуться к-й наименьшее значение

Вот код, чтобы сделать все, что:

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; 
     }  
} 

Когда я запускаю программу, я получаю все правильные выходы в терминах k-го наименьшего размера, но я не могу восстановить состояние моего PriorityQueue. Например, при переходе в PriorityQueue из:

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

... мой алгоритм дает правильный результат, 17, но он изменяет состояние PriorityQueue к [-3, 17, 9, 81, 22, 42], который является неожиданным.

Я думал о создании копии PriorityQueue, но это нарушает одно из условий: «вы можете использовать один стек или очередь в качестве вспомогательной структуры данных».

Как я могу восстановить состояние PriorityQueue?

Answer 1

В вашей реализации необходимо скорректировать две вещи. Во-первых, в качестве дополнительной структуры данных вы должны использовать очередь, а не стек. Толкание элементов в стек, а затем их выталкивание приведет к их добавлению обратно в очередь приоритетов в обратном порядке. Если они выходят из очереди приоритетов как 1, 2, 3, они будут добавлены обратно в очередь приоритетов как 3, 2, 1. Это связано с тем, что стеки представляют собой структуру данных LIFO (Last in, first out). Вы хотите использовать очередь в качестве своей вспомогательной структуры данных, потому что это структура данных FIFO (First in, first out), поэтому она сохранит тот же порядок.

Во-вторых, вы только вытаскиваете первые k элементов из очереди priorty. Я бы рекомендовал осушить всю очередь, чтобы вы добавили все элементы в очередь в том порядке, в котором они вышли, а не только некоторые.

Другими словами, я бы настроить программу следующим образом:

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

Примечание: Я изменил переменную «элемент» в вашей программе от типа int к Integer. Это не важно для правильности вашей программы, но это хорошая привычка уделять внимание авто-боксу. Общие типы, например коллекции, используют в штучной упаковке целые числа. Это объект, в котором хранится примитивное целое число. Присвоение целому числу в штучной упаковке типа int требует, чтобы он был распакован, т. Е. Возвратился в примитив int. Это не имеет большого значения, за исключением того, что вы снова добавляете это значение обратно в коллекцию. Поскольку вы распаковали его в примитив int, его снова нужно снова вставить в Integer, и для этого требуется, чтобы система создала объект для его хранения. Поскольку все, что вы делаете со значением, выводит его из и вернув его в коллекцию, лучше использовать значение Integer здесь, чтобы избежать разблокировки и бокса, поскольку это действительно не нужно.