힙
- 최소/최대값을 빠르게 찾기 위해 고안된 완전 이진 트리 형태의 자료구조
- 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례로 삽입하는 트리
왼쪽: 완전이진트리 / 오른쪽: 단순이진트리
- 힙의 구조: Max Heap / Min Heap
- Max Heap: 최대값이 루트노드이고, 각 부모노드는 자식노드보다 크거나 같은 값을 가짐
- Min Heap: 최소값이 루트노드이고, 각 부모노드는 자식노드보다 작거나 같은 값을 가짐
- 우선순위 큐의 구현을 위해 사용된다.
- 큐는 선입선출 방식이지만, 우선순위 큐는 들어간 순서와 상관없이 높은 우선순위를 가진 원소가 가장 먼저 나오는 방식이다.
- 작은 숫자부터 나오는 큐를 Min Heap, 큰 숫자부터 나오는 큐를 Max Heap이라고 한다.
- 이진 탐색 트리와는 달리 중복된 값이 허용되고, 자식노드의 좌우는 크기 상관없이 배치된다. (힙은 정렬된 구조가 아니다)
- 힙을 사용하는 이유: 배열에 데이터를 넣고 최대/최소값을 찾으려면 O(n)이 걸리지만, 힙에 데이터를 넣고 최대/최소값을 찾으면 O(log n)이 걸린다.
이진 탐색 트리 (BST)
- 특정 값을 빠르게 검색하기 위해 고안된 이진 트리 형태의 자료구조
- 왼쪽 자식노드 < 부모노드 < 오른쪽 자식노드 순으로 배치되어 있다.
- 모든 노드는 유일한 값(key)을 가지고, 왼쪽 서브트리와 오른쪽 서브트리 모두 이진 탐색 트리를 이룬다.
- 한번 탐색할 때마다 노드의 개수가 절반씩 줄어들기 때문에 완전 이진 트리인 경우 탐색 시간은 O(log n)이 걸린다.
- 편향 이진 트리인 경우 탐색 시 O(n)가 걸리기 때문에 가급적 완전 이진 트리 형태를 유지할 수 있도록 해야한다.
