728x90
[자료구조] 우선순위 큐와 힙 (Priority Queue & Heap) (tistory.com)
[자료구조] 우선순위 큐와 힙 (Priority Queue & Heap)
1. 우선순위 큐 1.1 우선순위 큐란? 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위
suyeon96.tistory.com
큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.
우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.
힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다.
여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르다.
- 완전이진트리 형태로 이루어져 있다.
- 부모노드와 서브트리간 대소 관계가 성립된다. (반정렬 상태)
- 이진탐색트리(BST)와 달리 중복된 값이 허용된다.
힙의 종류
- 최대 힙 (Max Heap)❝ key(부모노드) ≥ key(자식노드) ❞
- 부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리이다.
- 최소 힙 (Min Heap)❝ key(부모노드) ≥ key(자식노드) ❞
- 부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리이다.
2. 우선순위 큐 구현
2.1 힙 구현
힙은 일반적으로 배열을 이용하여 구현한다.
완전 이진트리이므로 중간에 비어있는 요소가 없기 때문이다.
위 그림과 같이 트리의 각 노드에 번호를 붙이고, 이 번호를 배열의 인덱스로 생각하면 효과적으로 힙을 구현할 수 있다.
배열로 구현하였기 때문에 부모 또는 자식 노드를 찾아가는 연산을 구현하기도 간편하다.
자식노드를 구하고 싶을 때
- 왼쪽 자식노드 index = (부모 노드 index) * 2
- 오른쪽 자식노드 index = (부모 노드 index) * 2 + 1
부모노드를 구하고 싶을 때
- 부모 노드 index = (자식노드 index) / 2
728x90
'CS > 자료구조 & 알고리즘' 카테고리의 다른 글
| List / Dictionary(C++에서의 map) / Set (0) | 2023.12.16 |
|---|---|
| 이진탐색 (시간복잡도와 이유) (0) | 2023.12.16 |
| 레드블랙트리 (0) | 2023.12.16 |
| map과 hashMap차이 (0) | 2023.12.16 |
| 자료구조 장단점(C++) (0) | 2023.10.10 |