PriorityQueue2 [ Java ] PriorityQueue에 하나씩 넣으면 O(n log n)인데, 한 번에 만들면 O(n)이라고? 지난 글에 이어서 PQ를 또 후두리찹찹 해보도록 하겠습니다. 우선순위 큐를 처음 채울 때 보통 이렇게 작성합니다.PriorityQueue pq = new PriorityQueue();for (int value : values) { pq.offer(value);}원소 하나를 넣을 때 힙을 조정하는 비용이 O(log n)이니까, n개를 넣으면 최악 O(n log n)입니다.그런데 이미 리스트에 값이 모여 있다면 이렇게도 만들 수 있습니다.List values = Arrays.asList(7, 6, 5, 4, 3, 2, 1);PriorityQueue pq = new PriorityQueue(values);이 경로의 힙 구성은 O(n)입니다.“같은 값을 넣는데, 생성자로 넘기면 더 싸다고?”(생성자가 반복.. 2026. 9. 28. [ Java ] PriorityQueue에 넣은 값을 바꿨는데, 왜 꺼내는 순서는 그대로일까? 코테를 풀다 보면 우선순위 큐를 자주 사용하게 됩니다. 작은 값부터 꺼내고 싶으면 PriorityQueue에 넣고, poll()로 하나씩 꺼내면 되죠. 그런데 객체를 넣었다면? 그리고 큐에 넣은 뒤에 그 객체의 우선순위를 바꿨다면? “값이 작아졌으니까 알아서 먼저 나오겠지?” ( 4개월 전 작성자의 크나큰 실수.. ) 흠..? 정말 그렇게 동작하는지 살펴보겠습니다!분명 1로 바꿨는데, 10이 먼저 나온다숫자가 작을수록 먼저 처리하는 작업 큐를 만들어보겠습니다.import java.util.Comparator;import java.util.PriorityQueue;public class PriorityQueueMutationDemo { static class Task { final Str.. 2026. 9. 27. 이전 1 다음
