-
힙 (우선순위큐의 구현방법)
- 조건 1. 완전이진트리 (complete binary tree) 형태
- 조건 2. parent의 우선순위가 항상 child의 우선순위보다 높거나 같음 (root : 최우선순위)
- 최소힙 (Min Heap) : parent의 key ≤ child의 key
- 최대힙 (Max Heap) : child의 key ≤ parent의 key
-
큐 vs 우선순위큐
- 큐 는 우선순위 개념이 없이 FIFO 원칙을 지키지만, 우선순위 큐 는 우선순위가 높은 데이터가 먼저 인출됨
-
참고자료
- 관련예제 : peek
- 본 예제는 최소힙으로 구현
- 우선, heap[++size]에 새로운 노드를 삽입
- i(size)와, i의 parent인
i/2를 서로 비교하여 i가 더 작을 경우 swap해줌 - 위 과정을 반복하여 heap을 정렬함
- 관련예제 : insert
- 우선순위가 가장높은 root를 삭제시켜주는 연산
- 우선 heap[size] 즉, 마지막 노드가 root를 대체하도록 함
- i(root)와, i의 child인
2i와2i + 1중 더 작은 값을 서로 비교하여 i가 더 클 경우 swap해줌 - 위 과정을 반복하여 heap을 정렬함
- 관련예제 : pop