- 우선순위 큐는 일반적인 큐와 다르게 우선순위가 높은 데이터가 먼저 나갈 수 있도록 만들어진 자료구조이다.
1. Heap
1.1 Heap 이란?
- 힙(heap)은 완전이진트리를 기본으로 한 자료구조 이다.
- 완전 이진트리란 아래 사진과 같이 포화 이진트리(leaf 노드를 제외한 internal 노드들이 전부 차있는 이진트리) 에서 오른쪽 리프 부터 제거하여 얻은 트리이다.
1.2 Node 간의 관계
- A가 B의 부모노드이면, A의 키 값은 B의 키 값과 대소관계가 성립한다.
- 이 대소관계에 따라 최소 힙 또는 최대 힙으로 나뉘는데, 최소 힙의 경우 부모 노드의 키가 항상 자식노드 보다 작고, 최대 힙은 반대이다. 이때 부모 자식간의 대소관계는 성립되지만 형제 노드간에는 대소관계가 성립되지 않는다.
1.3 heap의 구현
-
힙을 저장하는 표준적인 자료구조는 배열이다.
-
특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
- 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
-
힙에서의 부모 노드와 자식 노드의 관계
- 왼쪽 자식의 인덱스 = (부모 노드의 인덱스) *2
- 오른쪽 자식의 인덱스 = (부모 노드의 인덱스 ) *2 +1
- 부모의 인덱스 = (자식의 인덱스) / 2
1.4 heap에서의 삽입
-
힙에서 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
-
새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.
- 예시) 아래 그림과 같은 최대 힙(max heap)에 새로운 요소 8을 삽입하는 방법
1.5 heap에서의 삭제
-
최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다.
- 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.
-
삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
-
힙을 재구성한다.
- 예시) 아래 그림과 같이 최대 힙(max heap)에서 최댓값을 삭제하는 방법
정리.
- heap의 root 노드의 값은 항상 우선순위가 제일 높은값(혹은 제일 낮은 값)이므로 우선순위 큐를 구현하기에 적절하다는 것을 알 수 있다.
- 시간 복잡도가 O(logN)이다
가보자고