완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 가장 작은 노드를 찾기 위해서 만든 자료구조
- 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 > 자식 노드의 키 값
- 루트 노드 : 키 값이 가장 큰 노드
- 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 < 자식 노드의 키 값
- 루트 노드 : 키 값이 가장 작은 노드
- 힙에 마지막에 원소를 삽입하고 부모노드와 비교하며 자리를 변경
- O(logN)
- 힙에서는 루트 노드의 원소만을 삭제할 수 있다.
- 루트 노드의 원소를 삭제하여 반환한다.
- 힙의 종류에 따라 최대값 또는 최솟값을 구할 수 있다.
- O(logN)
- 우선순위 큐를 구현하는 가장 효율적인 방법이 힙을 사용하는 것이다.
- 노드 하나의 추가/삭제 시간 복잡도가 O(logN)이고 최대값/최소값을 O(1)에 구할 수 있다.
- 완전 정렬보다 관리 비용이 적다
- 배열을 통해 트리 형태를 쉽게 구현할 수 있다.
- 부모나 자식 노드를 O(1)연산으로 쉽게 찾을 수 있다.
- n위치에 있는 노드의 자식은 2n과 2n+1위치에 존재한다
- 완전 이진 트리의 특성에 의해 추가/삭제의 위치는 자료의 시작과 끝 인덱스로 쉽게 판단
- 우선순위를 가진 항목들을 저장하는 큐
- FIFO 순서가 아니라 우선 순위가 높은 순서대로 먼저 나가게 된다.
- Heap 자료 구조
- 최대 Heap
- 가장 큰 값을 기준으로 먼저 나옴
- 최소 Heap
- 가장 작은 값을 기준으로 먼저 나옴
- PriorityQueue()
- 원소들의 nature Ordering에 따라 힙 유지
- 따라서, 반드시 모든 원소는 Comparable 인터페이스를 구현해야 함
- PriorityQueue(Comparator comparator)
- 명시된 Comparator의 구현에 따라 원소들의 순서를 유지
- 힙 정렬은 힙 자료구조를 이용해서 이진 트리와 유사한 방법으로 수행된다.
- 정렬을 위한 2단계
- 하나의 값을 힙에 삽입한다(반복)
- 힙에서 순차적(오름차순)으로 값을 하나 씩 제거한다
- 힙 정렬의 시간 복잡도
- N개의 노드 삽입 연산 + N개의 노드 삭제 연산
- 노드 하나의 삽입과 삭제 연산은 각각 O(logN)이다
- 따라서 전체 정렬은 O(NlogN)이다