1. 우선순위 큐
- 우선순위의 개념을 큐에 도입한 자료구조
- 우선순위가 높은 데이터가 먼저 나감
2. 우선순위 큐 사용
- 시뮬레이션 시스템, 작업 스케쥴링, 수치해석 계산
우선순위 큐는 배열, 연결리스트, 힙으로 구현(힙이 가장 효율적)
힙 -> 삽입 : O(logn), 삭제 : O(logn)
3. 힙
- 우선순위 큐를 위해 만들어진 자료구조.
- 완전 이진트리의 일종
- 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조
- 반 정렬 상태
- 힙 트리는 중복 값 허용 (이진트리 - X)
4. 힙 종류
- 최대 힙(max heap)
부모 노드의 키 값이 자식 노드의 키 값 보다 크거나 같은 완전 이진트리
- 최소 힙(min heap)
부모 노드의 키 값이 자식 노드의 키 값 보다 작거나 같은 완전 이진트리
5. 구현
- 힙을 저장하는 표준적인 자료구조는 배열
- 구현을 쉽게하기 위해 배열의 첫번째 인덱스 0 사용 X
6. 부모 - 자식
- 왼쪽 자식 index = (부모 index) * 2
- 오른쪽 자식 index = (부모 index) * 2 + 1
- 부모 index = (자식 index) / 2
7. 힙의 삽입
- 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입
- 새로운 노드를 부모 노드들과 교환
8. 힙의 삭제
- 최대 힙에서 최대값은 루트 노드 이므로 루트 노드가 삭제됨
(최대 힙에서 삭제 연산은 최대값 요소를 삭제 하는것)
- 삭제된 루트 노드에는 힙의 마지막 노드를 가져옴
- 힙의 재구성