[자료구조] 우선 순위 큐

우선 순위 큐(Priority Queue)

 

일반적인 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 First-In First-Out의 FIFO 구조입니다.

 

우선 순위 큐는 들어간 순서에 상관없이 우선 순위가 높은 데이터가 먼저 나오는 것입니다.

 

우선 순위 큐는 힙 자료구조를 이용해 구현할 수 있습니다.

 

 

완전 이진 트리인 힙 구조이고 최대 힙입니다.

 

여기에 9가 추가 되었습니다

 

 

그럼 완전 이진 트리의 조건을 만족시키기 위해 왼쪽부터 채워져서 현재 자리에 위치하게 됩니다

 

 

그럼 9는 최대 힙 구조를 만족 시키기 위해 처음 부모 노드였던 3과 자리를 바꾸고

또 부모 노드였던 6과 자리를 바꾸게 됩니다.

 

Push 연산을 봤으니 삭제하는 Pop 연산을 보겠습니다

 

 

최대 힙 구조에서 우선도가 가장 높은 17이 빠져 나갔습니다

그럼 저 자리는 힙 구조의 가장 마지막 원소가 채워지게 됩니다

? 자리에는 3이 오겠죠

 

 

하지만 3이 맨 위에 있으면 최대 힙 구조를 만족시키 못하게됩니다.

그래서 13과 바꿨더니 또 최대 힙과 맞지 않으므로

최대 힙 조건에 맞을 때 까지 바꿔주며 맞는 자리에 오게됩니다

 

 

이렇게요

 

최소 힙도 최대 힙과 마찬가지입니다!

 

 

 

사진 출저

https://choheeis.github.io/newblog//articles/2020-05/PriorityQueue