PriorityQueue [Class]

Queue 인터페이스를 구현한 구현체가 PriorityQueue다.

기본적인 함수는 동일하게 사용한다
(add(e),remove(),element()...)

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. (Java doc 발췌)

대략적으로 우선순위큐(Priority Queue)는 우선순위 힙(Priotiry Heap)을 기반으로 설계되어 있고, 우선순위 큐의 엘리멘트(데이터)들은 자연정렬(natural ordering) 순서체계를 따르거나 큐가 만들어질때 비교기준(Comparator)이 있다면 그것을 따른다. 라는 말인데..

즉, 힙구조로 설계되어 있다는 뜻이다.
(= FIFO(선입선출)방식이 아님)
(*자연정렬이란 숫자를 자연스럽게 맞추는 것을 뜻함 1,2,3,4,5 이런식)

코드를 보자

		PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

		priorityQueue.offer(6);
		priorityQueue.offer(2);
		priorityQueue.offer(9);
		priorityQueue.offer(10);
		priorityQueue.offer(5);
		priorityQueue.offer(2);
		priorityQueue.offer(1);

		System.out.println(priorityQueue);
        
        //출력

		[1, 5, 2, 10, 6, 9, 2]

원래 큐(Queue)라면 [6,2,9,10,5,2,1] 이런식으로 정의가 되어있지만 뭔가 결과가 이상하지 않은가? 오름차순도 아니고 내림차순도 아니고, 이것은 힙 구조다.

출처: https://velog.io/@nninnnin7/HEAP

힙이란 크게 2가지 인데,

min heap은 최솟값이 최상단에 위치하며 아래 트리구조를 지닌 자료구조 이고
max heap은 반대로 최댓값이 위에 있다

heap에 대해서 간략하게 예제를 보면서 어떻게 위의 코드에서 출력이 저렇게 나오는지 알아보자

1. 처음 배열은 [6,2,9,10,5,2,1] 이렇게 되어있다 (참고로 priorityQueue의 디폴트 힙은 최솟값이 최상단에 온다)

2. 이걸 힙으로 바꿔보면이런 구조인데,

3. 힙은 맨위의 값과 자식노드(노드란 하나의 값(value)를 가지고 있는 공간 이다) 둘을 비교하고 최솟값이 위로 오도록 자리를 바꾼다.

4. 그럼 이런 형태가 되는데, 여기서 6번으로 이동해서 값들을 비교해준다.

5. 그렇다면 이런형태가 되고 다음 9로 넘어간다

6. 

7. 

8. 

9. 

10. 읽기는 여러 방법이 있지만 자바에서의 priorityQueue는 왼쪽 -> 오른쪽으로 읽기를 하는듯하다 [1,5,2,10,6,9,2]

이렇게 heap구조로 저장되어서 출력이 되지만 막상 poll을 입력하여 윗값부터 빼내어 보면 숫자 순서대로 빠진다

		System.out.println(priorityQueue.poll());
		System.out.println(priorityQueue.poll());
		System.out.println(priorityQueue.poll());

		System.out.println(priorityQueue);
        
        //출력
		1 //순서대로 빠짐
		2
		2
		[5, 6, 9, 10]

아마도 우선순위 큐는 자료를 큐의 구조(선입선출) 방식으로 넣지만 최댓값 최솟값을 빠르게 구별해서 출력해야 하며 순서가 중요한 곳에 쓰지 않을까 생각한다. 좀더 공부한 후 포스팅해보겠다.

포스팅은 반말이지만 마음은 존댓말 입니다 감사합니다