8. 우선순위 큐

우선순위 큐: 우선순위를 가진 항목들을 저장하는 큐 

- 일반 큐와 다른 점은 우선순위가 높은 데이터가 먼저 나감 

 

구현 방법

1. 배열을 이용한 우선순위 큐

2. 연결 리스트를 활용한 우선순위 큐

3. 히프(heap)를 이용한 우선순위 큐

 

구현 별 시간 복잡도 

표현 방법                               삽입                    삭제

순서 없는 배열                       O(1)                     O(n)

순서 없는 연결 리스트           O(1)                     O(n)

정렬된 배열                            O(n)                     O(1)

정렬된 연결 리스트                O(n)                     O(1)

히프                                        O(log n)               O(log n)

 

히프: 노드의 키들이 다음 식을 만족하는 완전이진트리 

- 최대 히프: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 // key(부모 노드) >= key(자식 노드)

- 최소 히프: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리 // key(부모 노드) <= key(자식 노드)

 

히프의 높이

- n개의 노드를 가지고 있는 히프의 높이는 O(log n)

- 마지막 레벨 h를 제외하고는 각 레벨에 2^(i-1)개의 노드 존재 

 

히프의 구현 방법

1. 히프는 배열을 이용하여 구현 

- 완전이진트리이므로 각 노드에 번호를 붙이는데 이 번호를 배열의 인덱스라고 생각 

히프 배열 구현

2. 부모와 자식 노드를 찾기 쉬움 

- 왼쪽 자식의 인덱스 = (부모의 인덱스)*2

- 오른쪽 자식의 인덱스 = (부모의 인덱스)*2 +1

- 부모의 인덱스 = (자식의 인덱스)/2

 

히프의 정의 

히프 정의

 

히프에서의 삽입 

- 새로운 요소가 들어오면 히프의 마지막 노드에 삽입한 후에 부모 노드와 비교하여 교환

히프 삽입연산

 

히프에서의 삭제

- 루트 노드를 삭제하고 마지막 노드를 루트 노드로 이동, 그 후 루트에서부터 단말 노드까지의 경로에 있는 노드들을 비교 및 교환

히프 삭제연산

히프의 복잡도 분석

- 삽입 연산에서 최악의 경우, 루트 노드까지 올라가야 하므로 트리 높이에 해당하는 비교 연산 및 이동 연산이 필요

   -> O(log n) 

- 삭제도 최악의 경우, 가장 아래 레벨까지 내려가야 하므로 트리의 높이만큼의 시간이 걸림

   -> O(log n) 

 

히프 정렬

-  최대 히프를 이용하면 정렬을 할 수 있는데 n개의 요소는 O(nlog n) 시간 안에 정렬된다. 

히프 정렬

 

 

 

 

 

 

 

자료 출처: 천인국 외 1명, C언어로 쉽게 풀어쓴 자료구조, 생능출판(2019)