[자료구조] 힙(Heap)과 우선순위 큐(Priority Queue)

큐란?

[자료구조] 큐(Queue) - 선형 큐(Linear Queue), 원형 큐(Circular Queue), 연결 큐(Linked List Queue), 데크(Double-E

트리란?

[자료구조] 트리(Tree) - 이진 트리(Binary Tree), 트리 순회(Tree Traverse), 이진 탐색 트리(Binary Search Tree)

 

● 우선순위 큐 (Priority Queue)

- 가장 먼저 삽입된 데이터가 아닌 우선 순위가 높은 데이터가 가장 먼저 삭제된다.

- 일반적으로 '힙(Heap)'을 이용하여 구현한다.

 

● 힙 (Heap)

- 완전 이진 트리로 트리 안에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조다.

○ 최대 힙(Max Heap) 

- 모든 노드에 저장된 키 값은 자식 노드에 저장된 키 값보다 크거나 같아야 한다. \(key(부모노드) >= key(자식노드)\)

- 즉, 루트 노드에는 트리의 최대값이 존재한다.

- 루트 노드로 올라갈 수록 노드에 저장된 키 값은 커진다.

○ 최소 힙(Min Heap) 

- 모든 노드에 저장된 키 값은 자식 노드에 저장된 키 값보다 작거나 같아야 한다. \(key(부모노드) <= key(자식노드)\)

- 즉, 루트 노드에는 트리의 최소값이 존재한다.

- 루트 노드로 올라갈 수록 노드에 저장된 키 값은 작아진다.

 

○ 삽입 연산

① 완전 이진 트리의 성질에 만족하도록 마지막 노드의 다음 자리에 공백 노드를 만들고, 데이터를 삽입한다.

 

② 힙의 성질에 만족하도록 부모 노드와 키 값을 비교하며 자리 이동을 반복한다.

 

 

○ 삭제 연산

① 루트 노드를 삭제하고, 마지막 노드를 루트 노드의 자리로 이동한다.

 

② 힙의 성질에 만족하도록 자식 노드와 키 값을 비교하며 자리 이동을 반복한다. 

# 두 개의 자식 노드 중 키 값이 더 큰 자식과 자리를 교환한다.