자바 우선 순위 큐 (안정 정렬?)

Question

PriorityQueue pq = new PriorityQueue<>(Comparator.reverseOrder());위 우선순위큐에 1 1 1 9 1 1 1 을 삽입한다면 9 1 1 1 1 1 1 이 되는 것으로 알고 있습니다.1의 순서를 알기 쉽게 표현하기 위해서 입력순대로 알파벳으로 나열하겠습니다.1 1 1 9 1 1 1 (삽입) 9 1 1 1 1 1 1a b c 9 d e f (삽입) 9 d e f a b c 어떻게 9 d e f a b c 순으로 정렬되는지 알 수 있을까요? 간단한 코딩테스트 문제 풀이 중, 궁금해서 여러곳을 찾아봤지만 해결하지 못해서 질문 남깁니다.참고) 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42587질문 자체가 잘못되었습니다.아래 코드의 while 문 내부의 for 문으로 문제에서 요구했던 우선순위를 올바르게 짚을 수 있었습니다.(입력) 1 1 1 9 1 1 1 -> 우선순위큐에 삽입 -> 9 1 1 1 1 1 1(입력) a b c 9 d e f -> 우선순위큐에 삽입 -> 9 ? ? ? ? ? ? 로 예상 (알 수 없음)answer = 0;pq.peek -> 9 9는 입력 배열의 3번째 요소(0,1,2,3)for 문의 현재 idx -> 3 해당 프로세스 실행 순서 : ++answer (1)즉, 1등으로 실행되는 것은 입력 배열의 3번째 요소pq.dequeuepq.peek -> 11은 입력 배열의 0번째 요소for 문의 현재 idx -> 4해당 프로세스 실행 순서 : ++answer (2)즉, 2등으로 실행되는 것은 입력 배열의 4번째 요소pq.dequeue.......................따라서 1(d)는 2번째로 실행되며, 1(a)는 반복문이 끝난 후 새로운 반복문에서 answer 가 5일 때 실행되는 것이라고 마무리 지었습니다.죄송합니당.. 역시 우선순위큐에서 정렬 순서를 지정하지 않은 동일한 값에 대한 정렬 순서가 올바르게 정렬될 리가 없었습니다.문제 코드import java.util.Comparator; import java.util.PriorityQueue; public class 프로세스우선순위큐 { public static int solution(int[] priorities, int location) { int answer = 0; PriorityQueue pq = new PriorityQueue<>(Comparator.reverseOrder()); for (int i = 0; i < priorities.length; i++) { queue.add(priorities[i]); } while (!queue.isEmpty()) { for (int i = 0; i < priorities.length; i++) { if (queue.peek() == priorities[i]) { if (i == location) { answer++; return answer; } else { queue.poll(); answer++; } } } } return answer; } public static void main(String[] args) { int[] priorities = {1, 1, 9, 1, 1, 1}; System.out.println(solution(priorities, 1)); }

Clickin · Accepted Answer

큐는 기본적으로 First In, First Out이니까 들어온 순서대로 나열되는게 대전제이고우선순위 큐는 그 위에 우선순위라는 부가옵션을 더한거니까우선순위가 같은 것 끼리는 들어온 순서가 유지되어야죠.그걸 실제로 어떻게 구현했는지는 openjdk 소스 찾아보시면 되는데대충 훑어본 바로는 먼저 heap 자료구조를 만들 때 siftDownUsingComparator 를 호출하고이때 제공된 comparator를 사용해서 우선순위를 처리한 후 우선순위가 동등하면 break; 해서 FIFO 상태로 유지합니다.https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/PriorityQueue.java#L702

응애나개발자가되고싶어요 · Answer

제가 잘못 아는 부분이 있을 수 있어서 계속 디버깅해보다가 해결하면 댓글 달고 수정해두겠습니다

자바 우선 순위 큐 (안정 정렬?)

2개의 답변

Q&A 목록