5. 우선순위 큐

우선 순위가 높은 데이터가 먼저 나가는 자료구조. : 우선 순위를 가진 항목들을 저장하는 큐

우선순위 큐 활용 분야 : 

1. 시뮬레이션 시스템

2. 네트워크 트래픽 제어

3. OS 작업 스케줄링

 

출처 : https://hannom.tistory.com/36

우선순위 큐의 구현 방법 3가지

1.  배열

2. 연결리스트

3. 힙(Heap)

 

배열 / 연결리스트를 이용해서 구현 시 장점 : 간단하게 구현 가능

단점 : 

1. 데이터 삽입 및 삭제 시 데이터를 한 칸씩 당기거나 밀어야 하는 연산을 계속 하여야 한다.

2. 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 한다.

   (이 경우 우선순위가 가장 낮은 데이터를 저장할 때 최악의 경우가 발생)

 

이러한 단점들 때문에 우선순위 큐는 힙(Heap)을 이용해서 구현하는 것이 일반적.

 

힙을 배열 기반으로 구현 시 :

왼쪽 자식 노드의 인덱스 값	부모 노드의 인덱스 값 * 2
오른쪽 자식 노드의 인덱스 값	(부모 노드의 인덱스 값 * 2) + 1
부모 노드의 인덱스 값	자식 노드의 인덱스 값 / 2

 

구현 : https://robodream.tistory.com/183