우선순위 큐
우선순위가 높은 데이터 순서대로 출력하는 자료구조
FIFO 구조인 큐와 달리, 우선순위 큐는 우선순위가 높은 순서대로 데이터가 출력됨
구현 방법 : 배열, 연결리스트, 힙
- 배열 : 구현은 쉬우나, 데이터가 많은 경우에는 전체 비교를 거쳐 적절한 위치를 찾고, 삽입을 위해 해당 자리 이후의 데이터를 한 칸씩 뒤로 밀어내야 함. 선형구조로, 삽입 및 삭제 연산 시 시간복잡도 O(n)
- 연결리스트 : 구현은 쉬우나, 데이터가 많은 경우에는 모든 노드에 접근하여 비교해야 함. 선형구조로, 삽입 및 삭제 연산 시 시간복잡도 O(n)
- 힙 : 우선순위 큐를 위해 고안된 이진트리의 일종
힙
우선순위 큐의 구현체
완전 이진 트리 형태로, 이진 탐색 트리와 달리 중복값 허용
부모 노드는 자식 노드보다 항상 우선순위가 높으며, 형제 노드 간의 우선순위는 고려하지 않는 반정렬 상태를 유지
* 반정렬상태 : 정렬되어 있지 않은 상태. 부모-자식 간의 우선순위는 있으나 형제 노드 간 우선순위는 없으므로
최소 힙(오름차순) : 노드 값이 작을수록 우선순위가 높음 → 루트 노드의 값이 가장 작음(부모 노드의 값 <= 자식 노드의 값)
최대 힙(내림차순) : 노드 값이 클수록 우선순위가 높음 → 루트 노드의 값이 가장 큼(부모 노드의 값 >= 자식 노드의 값)
힙 정렬
- 최소 힙, 최대 힙을 이용한 정렬 알고리즘
- 항상 루트 노드를 출력 → 전체 자료를 정렬하기 보다는 최댓값 혹은 최솟값을 찾아내고자 할 때 적절
- 시간복잡도 : 부모 - 자식 간의 비교만 진행하면 되므로 O(log n)
힙의 표현
- 주로 배열을 이용해 구현하며, 보통 편의상 index 0은 사용하지 않고 1부터 시작
- 배열을 사용하는 이유 : 완전 이진 트리이므로 중간에 빈 노드가 없음 + index를 통한 값 조회가 편리함
- 부모 노드의 index = 자식 노드의 index / 2
- 좌측 자식 노드의 index = 부모 노드의 index * 2
- 우측 자식 노드의 index = 부모 노드의 index * 2 + 1
힙의 삽입
- 마지막 노드의 우측에 새로운 노드 삽입 후, 부모노드와 비교하며 우선순위에 맞는 적절한 자리를 찾아감
힙의 삭제
- 우선순위가 가장 높은 노드(즉, 루트노드)부터 삭제
- 마지막 노드를 루트 노드 위치로 이동
- 루트 노드 자리로 이동한 마지막 노드의 값을 자식 노드와의 값과 비교하며 적절한 자리를 물색
- 만일 부모노드가 좌측, 우측 자식을 모두 가진 경우에는 둘 중 우선순위가 더 높은 자식과 swap
참고
'자료구조&알고리즘' 카테고리의 다른 글
| 완전탐색(Brute-Force Search) (0) | 2022.06.04 |
|---|---|
| 해시(Hash) (0) | 2022.05.29 |
| 트리(Tree) - 이진 탐색 트리(Binary Search Tree) (0) | 2022.05.29 |
| 정렬(Sorting) (0) | 2022.05.29 |