자료구조 - 우선순위 큐

우선순위 큐 - 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조

 

 

우선순위 큐의 구현 방법

● 배열을 기반으로 구현하는 방법

● 연결 리스트를 기반으로 구현하는 방법

● 힙을 이용하는 방법

 

 

우선순위 큐의 시간 복잡도

 

 

여기서 힙이란 ?

힙은 완전 이진트리를 말하며 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다.

즉 루트 노드에 저장된 값이 가장 커야 한다.

 

 

위 트리처럼 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리를 가리켜 최대 힙이라 한다.

 

 

반면 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리를 가리켜 최소 힙이라 한다.

 

---

▼ 힙에서의 데이터 저장 과정

 

숫자가 작을수록 우선순위가 높다고 가정

새로운 데이터는 완전 이진트리가 유지되는 마지막 레벨에 위치한다. 그리고 부모 노드와 우선 순위를 비교한다. 비교 후 위치를 바꾼다.

 

또 부모 노드와 우선 순위를 비교 후 자리를 바꾼다.

다시 한번 과정을 반복한다.

 

 

---

 

▼ 힙에서의 데이터 삭제 과정

 

우선순위가 가장 높은 루트 노드를 삭제한다.

트리의 마지막 노드를 루트 자리로 옮긴다.

두 개의 자식 노드인 3과 7중 우선 순위가 높은 3과 비교하여 위치를 바꾼다.

위치 교환하는 과정을 반복한다.