힙(Heap)
- 완전이진트리 형태의 자료구조이며 여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산을 할 때 주로 사용한다.
- 부모노드와 서브트리간 대소 관계가 성립된다.
- 종류로는 최대 힙 (부모 노드의 키 값이 자식 노드보다 큼), 최소 힙(부모 노드의 키 값이 자식 노드보다 작음)이 있다.
우선 순위 큐
큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.
우선순위 큐(Priority Queue)는 들어오는 순서가 아니라 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.
우선순위 큐는 배열 또는 연결리스트로도 구현이 가능하지만 시간복잡도의 향상을 위해 일반적으로 완전이진트리 형태의 힙(Heap)을 이용하여 구현.
우선순위 큐의 동작 원리(최대값 우선순위일 때)
- 우선순위 큐의 삽입
- 삽입할 원소는 완전 이진트리를 유지하는 형태로 순차적으로 삽입된다
- 삽입 이후에는 루트 노드까지 거슬러 올라가면서 최대 힙을 구성[상향식]
- 추가된 원소 9가 부모 노드보다 크므로 바꿔주고, 바꾼 후 또 그 부모보다 크므로 바꿔주면서 최대 힙을 유지한다.
- 삽입 완성
여러가지 블로그를 보고 우선순위 큐 자료구조에 개념을 이해하고 우선순위 큐 알고리즘 문제 10문제 풀어본 후 블로그 글 참고하여 기록.
'알고리즘&자료구조' 카테고리의 다른 글
| [자료구조] Collection (1) | 2023.04.12 |
|---|
