0. 힙(Heap)
완전 이진 트리에 있는 노드에서 가장 큰 키 값이나 가장 작은 키 값을 찾기 위해서 만든 자료구조이다.
중복 값도 가능하다.
힙의 특징으로는 노드의 삽입 혹은 삭제 연산이 발생할 때만, 해당 노드가 옳바른 자리를 찾아간다.
0-1. 최대 힙(Max Heap)
- 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 >= 자식 노드의 키 값
- 루트 노드: 키 값이 가장 큰 노드
0-2. 최소 힙(Min Heap)
- 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 <= 자식 노드의 키 값
- 루트 노드: 키 값이 가장 작은 노드
1. 힙 연산
최대 힙을 기준으로 설명을 할 예정이며, 최소 힙의 경우도 동일하게 동작한다.
노드 하나의 삽입 / 삭제 연산은 시간 복잡도가 O(lonN)이고 최대값/최소값을 구하는 것은 O(1)이다.
1-1. 삽입
- 17을 삽입하는 경우
- 23을 삽입하는 경우
1-2. 삭제
루트 노드의 원소만을 삭제할 수 있다.
루트 노드의 원소를 삭제하여 반환한다.
힙의 종류에 따라 최대값 또는 최소값을 구할 수 있다.
2. 우선순위 큐(Priority Queue)
우선순위를 가진 항목들을 저장한느 큐로 FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 된다.
사용하기 위해서는 Comparable 인터페이스를 구현하거나 Comparator를 작성해주어야 한다.
반응형
