[Java] PriorityQueue

Cjw.dev·2023년 3월 23일
0

JavaSturdy

목록 보기
1/1

PriorityQueue

일반적인 Queue 구조는 선입선출 방식의 자료구조이다.
PriorityQueue(우선순위 큐)는 '우선순위'가 높은 순서대로 소비되는 자료구조이다.
이 우선순위 큐는 일반적으로 힙(Heap)이라는 자료구조를 이용하여 구현될 수 있는데
힙은 최소 힙, 최대 힙이라는 두가지 구조가 있다.
(JAVA에서의 우선순위 큐는 최소 힙 구조로 되어있다)
입력받은 데이터를 최대 힙 또는 최소 힙을 구성하고 데이터를 꺼낼 때는 루트노드에서 꺼낸다.
그러므로 우선순위 큐를 이해하기 위해서는 힙에 대해 알아야 한다.


힙(HEAP)

최대 힙 : 가장 큰 값이 루트 노드에 위치한다.
(위 그림을 배열의 형태로 바꿔보면 [9,7,6,5,4,3,2,2,1])

최소 힙 : 가장 작은 값이 루트 노드에 위치한다.
(위 그림을 배열의 형태로 바꿔보면 [1,4,2,7,5,3,3,7,8])

특징을 조금 더 자세히 알아보자.

특징

  1. 힙은 이진트리의 일종으로 반정렬 상태이며(정렬된 상태가 아님) 중복값을 허용한다.
  2. 트리구조 이기 때문에 삽입/삭제가 빠르다. O(logN)
  3. 보통 우선순위 큐가 힙으로 많이 구현되는데, 배열과 리스트보다 효율적이다.
  4. 힙은 최대힙과 최소힙으로 나뉘어진다.
    최대힙 : 부모노드가 자식노드보다 큼
    최소힙 : 부모노드가 자식노드보다 작음
  5. 인덱스 구조
    부모 : n 왼쪽자식 : 2n 오른쪽자식 : 2n+1

(시간 복잡도에 대한 것은 https://www.youtube.com/watch?v=AjFlp951nz0 를 참고)


PriorityQueue의 최대 힙과 최소 힙

자, 그럼 우선순위 큐에 새로운 값이 들어왔을 때 어떤식으로 힙 구조로 정렬이 되는지 알아보자.
최대 힙을 예시로 보겠다. (최소 힙도 똑같다)

priorityQueue = {17,12,5,4,2}; 에 index6=19; 값이 새로 들어왔다.
index3과 index6을 보자.
최대 힙 구조는 부모 노드가 자식보다 커야 하는데 자식 노드인 index6이 더 크다.
이럴 경우 index3과 index6의 위치를 바꾼다.

바꾸고 보니 이번엔 부모 노드인 index1보다 자식 노드인 index3이 더 크다.
이번에도 위치를 바꾼다.
그럼 최종적으로 {19, 12, 17, 4, 2, 5} 라는 우선순위 큐의 최대 힙이 완성된다.

이렇게 아래서 위로 올라가며 구조를 맞추는 방식을 상향식이라고 한다.
반대로 위에서부터 내려가며 구조를 맞추는 방식도 있는데 하양식이라고 한다.

상향식과 하양식의 경우 위치가 약간 다를 수 있으나 최대 힙, 최소 힙의 조건은 만족하기 때문에
어떤 방식으로 사용하든 상관없다.

poll

자, 그럼 우선순위가 제일 높은 루트노드 값을 poll(큐에서 제거함)하면 어떻게 될까?

마지막 index6이 루트노드로 이동했다. 이걸 배열형태로 보면
pq = {17,12,5,4,2,11};
pq.poll;
pq = {11,12,5,4,2};
맨 마지막에 있던 11이 앞으로 온 것이다.
그리고 다시 구조를 보면 최대 힙 구조가 깨져있다. 그러니 다시 최대 힙 구조로 맞춘다.

pq={12,11,5,4,2};
다시 최대 힙으로 정렬되었다.

우선순위 값들을 poll할 때마다 위의 상황이 반복됨을 알면 된다.

참고 :
https://www.youtube.com/watch?v=iyl9bfp_8ag
https://www.youtube.com/watch?v=AjFlp951nz0
https://velog.io/@evelyn82ny/priority-queue

profile
백엔드 개발 공부 기록 22.11.07 ~ ing

0개의 댓글