[CS] 힙, 우선순위 큐

1. 힙 (Heap)

- 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다

(우선순위 큐 : 데이터들이 우선순위를 가지고 있어, 우선순위가 높은 데이터가 먼저 나간다)

 

- 여러개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다

힙은 일종의 반정렬 상태 (느슨한 정렬 상태)를 유지한다

 

- 쉽게말해 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작은 이진트리이다

 

- 힙 트리에서는 중복된 값을 허용한다 (이진 탐색 트리에서는 중복된 값을 허용하지 않는다)

 

2. 힙의 종류

최대힙

- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리이다

- Key (부모노드) >= key (자식노드)

 

최소힙

- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리이다

- Key (부모노드) <= key (자식노드)

 

3. 시간 복잡도

삽입 : O (log n)

- 힙에 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 삽입한다

- 새로운 노드를 부모 노드들과 교환한다

 

삭제 : O (log n)

- 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제된다

(최대 힙에서 삭제 연산은 최대 값의 요소를 삭제하는 것이다)

- 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다

- 힙을 재구성한다

 

4. 우선순위 큐 (Priority Queue)

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

우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다

 

enqueue()

- queue에 새 요소를 삽입한다

- 힙의 삽입과 동일한다

 

dequeue()

queue에서 최대 우선 순위 요소를 삭제하고 그 값을 반환한다

- 힙의 삭제와 동일하다

 

peek()

queue에서 최대 우선순위 요소를 반환한다