우선순위 큐(Priority Queue)
큐 형태로 우선순위가 높은 데이터가 먼저 나가는 자료구조
cf ) 큐(Queue)
먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조
ADT(Abstract Data Type)
- 객체
우선순위를 가진 요소들의 모음
- 연산
- insert(x)
우선순위 큐에 요소 x 추가 - remove()
우선순위 큐에서 가장 우선순위가 높은 요소를 삭제하고 반환 - find()
우선순위 큐에서 가장 우선순위가 높은 요소를 반환
구현 방법
- 배열 또는 연결리스트를 이용 > 삽입 또는 삭제 연산을 위한 시간복잡도는 O(n) ( ∵ 선형 구조의 자료구조 )
- 힙 트리 이용 > 힙트리의 높이는 log₂(n+1)이며 힙의 시간복잡도는 O(log₂n) ( ∵ 완전이진트리 구조 )
=> 일반적으로 힙(Heap)을 이용하여 구현
힙(Heap)
우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조
특징
- 부모노드와 서브트리간 대소 관계가 성립된다. (반정렬 상태)
- 여러 개의 값 중 최대/소값을 찾아내는 연산이 빠르다.
- 이진탐색트리(BST)와 달리 중복된 값이 허용된다.
종류
- 최대 힙 (Max Heap)
부모 노드의 키 값 ≥ 자식 노드의 키 값
- 최소 힙 (Min Heap)
부모 노드의 키 값 ≤ 자식 노드의 키 값
구현 방법
배열을 이용하여 구현( ∵ 완전이진트리이므로 중간에 비어있는 요소 X )
- HOW TO
트리의 각 노드에 인덱스 번호를 붙인다.
- 특징
부모/자식 노드를 찾아가는 연산 구현이 간편 ( ∵ 배열로 구현)
- 자식노드를 구하는 경우
- 왼쪽 자식노드 index = (부모 노드 index) * 2
- 오른쪽 자식노드 index = (부모 노드 index) * 2 + 1
- 부모노드를 구하는 경우
- 부모 노드 index = (자식노드 index) / 2
- 연산
힙 트리의 성질을 만족시키면서 연산하는 것이 중요하다.
- 삽입
시간복잡도 O(log₂n) ( ∵ 최악의 경우 새로 추가된 노드가 루트노트까지 비교하며 올라감)
- 완전이진트리의 마지막 노드에 이어서 새로운 노드를 추가한다.
- 추가된 새로운 노드를 부모의 노드와 비교하여 교환한다.
- 정상적인 힙트리가 될 때까지 (더이상 부모노드와 교환할 필요가 없을 때까지) 2번을 반복한다.
- 삭제
시간복잡도 O(log₂n) ( ∵ 최악의 경우 루트노트부터 가장 아래까지 내려감)
- 루트 노드를 삭제한다. ( ∵ 가장 높은 우선순위 )
- 루트 노드가 삭제된 빈자리에 완전이진트리의 마지막 노드를 가져온다.
- 루트 자리에 위치한 새로운 노드를 자식 노드와 비교하여 교환한다.
최대 힙인 경우 - 자식노드 중 더 큰 값과 교환
최소 힙인 경우 - 더 작은 값과 교환 - 정상적인 힙트리가 될 때까지 (더 이상 자식노드와 교환할 필요가 없을 때까지) 3번을 반복한다.
구현
소스 추가 예정
'알고리즘 > 자료구조' 카테고리의 다른 글
Collection 함수 정리 (0) | 2022.05.03 |
---|