단방향 그래프의 한 구조, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태
자식 노드가 최대 두개인 노드들로 구성된 트리, 효율적인 탐색에 용이
모든 왼쪽 자식의 값은 루트나 부모보다 작고, 모든 오른쪽 자식의 값은 루트나 부모보다 크다.
종류 | 설명 |
---|---|
정 이진 트리 | 각 노드가 0개 혹은 2개의 자식노드를 가짐 |
포화 이진 트리 | 정 이진트리이면서 완전 이진 트리일 경우, 모든 리프 노드의 레벨이 같고 모든 레벨이 가득 차 있는 트리 |
완전 이진 트리 | 마지막 레벨을 제외한 모든 노드가 차 있고 마지막 레벨의 노드는 전부 차 있지 않고 왼쪽만 존재하는 트리 |
우선 순위에 따라 빠르게 자료를 검색할 수 있는 트리
완전 이진 트리로 구성되어 있으며, 단순히 최소값, 최대값을 찾기 위해 완전 이진트리를 구성할 필요는 없지만 삽입/삭제 성능을 위해 완전 이진 트리로 구현하게 된다.
중복된 값을 저장할 수 있다. 이는 최대값/최소값을 찾아내기 위한 구조이기 때문이다.
PriorityQueue를 이용해서 Max/Min Heap Tree를 구현할 수 있다.
import java.util.*;
public class MaxHeap {
public static void main(String[] args) {
PriorityQueue<Integer> pq
= new PriorityQueue<Integer>(
Collections.reverseOrder()); // reverse를 통한 우선순위 변경
pq.add(1);
pq.add(5);
pq.add(6);
pq.add(8);
pq.add(10);
pq.add(11);
Iterator<Integer> itr = pq.iterator();
while (itr.hasNext())
System.out.println(itr.next());
}
}
import java.util.*;
public class MinHeap {
public static void main(String[] args) {
PriorityQueue<Integer> pq
= new PriorityQueue<Integer>();
pq.add(1);
pq.add(5);
pq.add(6);
pq.add(8);
pq.add(10);
pq.add(11);
Iterator<Integer> itr = pq.iterator();
while (itr.hasNext())
System.out.println(itr.next());
}
}
최대값과 최소값을 찾기 위해 걸리는 시간 복잡도는 O(1)이다. root 노드에 최대힙의 경우 최대값이, 최소힙의 경우 최소값이 위치하기 때문이다.
데이터 삽입과 삭제는 조금 복잡하기 때문에 좀 더 알아보기로 한다.
[최대힙의 데이터 삽입]
[최대힙의 데이터 삭제]
heap tree는 완전 이진 트리로 구현어 배열로 표현가능
완전 이진 트리의 특성상 중간에 빈값이 없기 때문에, 루트 노드부터 높이 순서대로 배열에 모두 정렬이 가능
구현과 노드의 위치를 찾기 쉽게 하기 위해 일반적으로 배열의 0번째 인덱스는 사용하지 않고, 첫 번째 인덱스부터 사용
배열로 heap tree를 구현한다면 배열의 크기에 따라서 heap tree의 depth가 얼마인지, 부모와 자식 노드의 위치까지도 쉽게 검색 가능
depth(깊이)는 배열의 길이가 1, 3, 7, 15 순서대로 2의 배수를 계속 더한 만큼 depth(깊이)가 늘어난다.
※ 참고 - Heap Tree를 사용되는 곳
힙정렬