PriorityQueue를 stream에서 사용시우선순위를 유지하는 방법

• 참고자료
  • Maintaining PriorityQueue Order with Java Streams
  • How to customize PriorityQueue.stream().foreach to iterate in priority order
  • PriorityQueue 관련
    • Priority Queue
    • Heap vs Priority Queues vs Queues
    • Data Structure, Java : Priority Queue

1. PriorityQueue는 stream/iterator 사용 시 정렬을 유지하지 않는다.

우선순위 큐(PriorityQueue)에서 Stream을 사용한다면 우선순위대로 나오는 것이 아닌,
값을 넣은 순서대로 값이 나오는 것을 볼 수 있다.

• 샘플 데이터
  • 반복문 + poll()을 사용하여 값을 가져오는 경우 [10 - 20 - 30 - 40 -50]의 우선순위로 정렬된 순서로 나오게 된다. (test 1)
  • stream과 iterator를 사용하는 경우 [10 - 20 - 50 - 30 - 40]의 queue에 데이터를 넣은 순서대로 나오게 된다. (test 2, 3)

    		private static Queue<Integer> createQueue() {
            Queue<Integer> queue = new PriorityQueue<>();
            queue. offer(10);
            queue.add(20);
            queue.add(50);
            queue.add(30);
            queue.add(40);
            return queue;
        }

1. test 1 : for문 + Queue.poll()

    		private static void for문으로_출력(Queue<Integer> queue) {
            System.out.println("\ncase : for문으로 출력");
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Integer value = queue.poll();
                System.out.print("- " + value);
            }
            System.out.println("\n출력 후 큐의 크기 : " + queue.size());
        }

    case : for문으로 출력
    - 10- 20- 30- 40- 50
    출력 후 큐의 크기 : 0

2. test 2 : stream

    		private static void 스트림_출력_기본(Queue<Integer> queue) {
            System.out.println("\ncase : stream으로 출력");
            queue.stream().forEach(value -> System.out.print("- " + value));
            System.out.println("\n출력 후 큐의 크기 : " + queue.size());
        }

    case : stream으로 출력
    - 10- 20- 50- 30- 40
    출력 후 큐의 크기 : 5

3. test 3 : iterator

    		private static void 이터레이터_출력(Queue<Integer> queue) {
            System.out.println("\ncase : iterator로 출력");
            Iterator<Integer> iterator = queue.iterator();
            while(iterator.hasNext()) {
                System.out.print("- " + iterator.next());
            }
            System.out.println("\n출력 후 큐의 크기 : " + queue.size());
        }

    case : iterator로 출력
    - 10- 20- 50- 30- 40
    출력 후 큐의 크기 : 5

2. 해결방법

The priority order of the PriorityQueue is not preserved when iterating/traversing so, essentially, we need to create our Stream instances ourselves.

PriorityQueue의 정렬이 순회 및 탐색 시 유지가 안되기 때문에, 새로운 스트림을 만들어 주어야 한다.

1. 스트림에서 Queue의 poll() 메소드를 이용하도록 수정
   • 단, poll()을 사용하는 만큼 stream을 돌고 나서 poll한 만큼 큐의 데이터가 빠져나가 있다.
   • stream을 사용하여 큐의 데이터를 안 뽑아내고 간단히 사용하려는 때에는 적합하지 않다.

    		private static void 스트림_출력_변형_1(Queue<Integer> queue) {
            System.out.println("\ncase : stream으로 출력 : poll을 이용하도록 수정");
            Stream.generate(queue::poll)
                    .limit(queue.size())
                    .forEach(value -> System.out.print("- " + value));
            System.out.println("\n출력 후 큐의 크기 : " + queue.size());
        }

    case : stream으로 출력 : poll을 이용하도록 수정
    - 10- 20- 30- 40- 50
    출력 후 큐의 크기 : 0

2. 스트림에서 다시 정렬해주기
   • 정렬되지 않은 데이터를 다시 sorted()하기 때문에 1번 해결방법보다 시간이 조금 더 걸리게 된다. (단, 데이터/Compartor에 따라 다르지만 대부분 큰 차이는 없다)

    		private static void 스트림_출력_변형_2(Queue<Integer> queue) {
            System.out.println("\ncase : stream으로 출력 : sort");
            Objects.requireNonNull(queue);
            queue.stream().sorted()
                    .forEach(value -> System.out.print("- " + value));
            System.out.println("\n출력 후 큐의 크기 : " + queue.size());
        }

    case : stream으로 출력 : sort
    - 10- 20- 30- 40- 50
    출력 후 큐의 크기 : 5