우선순위 큐(Priority Queue), 힙(Heap)

우선순위 큐(Priority Queue)

선입선출(FIFO)인 큐와 달리 모든 데이터가 우선순위를 가지고, 들어온 순서와 관계없이 우선순위가 높은 데이터가 먼저 출력되는 자료구조이며 삭제 연산에서 어떤 요소가 먼저 삭제되느냐에 따라 최소 우선순위 큐, 최대 우선순위 큐로 나누어진다.

---

최대/최소 우선순위 큐의 추상자료형

 

데이터

우선순위를 가진 요소들의 집합

 

연산

init(): 초기화

insert(): 항목 추가

delete(): 가장 우선순위가 높은/낮은 요소를 삭제 및 반환

find(): 가장 우선순위가 높은/낮은 요소를 반환

isEmpty(): 우선순위 큐가 비어있는지 확인

isFull(): 우선순위 큐가 가득찼는지 확인

---

우선순위 큐의 구현 방법

 - 배열을 통한 구현

 - 연결 리스트를 통한 구현

 - 힙을 통한 구현

---

힙(Heap)

완전이진트리이며 여러 개의 값들 중에서 가장 큰/작은 값을 빠르게 찾을 수 있도록 만들어진 자료구조이다.

 

힙의 특징

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

 - 중복된 값을 허용한다.

 - 주로 배열을 기반으로 구현한다.

 - 프로그램의 구현을 쉽게 하기 위해 배열의 첫 번째 인덱스는 사용하지 않는다.

 

힙의 종류

 

최대 힙(Max Heap)

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

 

최소 힙(Min Haep)

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

 

---

 

힙의 연산

힙의  삽입

힙은 삽입 시 새로운 노드를 힙의 마지막 노드의 다음 위치에 삽입한다. 하지만 이것만 하면 힙의 성질이 만족되지 않으므로 부모 노드와 비교 및 교환을 통해 힙의 성질을 만족시켜 주는 업 힙(Up-Heap)이라는 과정이 필요하다.

 

 

힙의 삭제

힙에서의 삭제 연산은 루트 노드를 삭제하는 것이며 최대 힙의 경우 루트가 최댓값이므로 루트 노드를 삭제 후 힙 트리를 재구성하는 과정이 필요하다. 이 때 말단을 루트로 올려 순차적으로 비교 및 교환을 하는 다운 힙(Down-Heap)이라는 과정을 사용한다.