루트 노드 Root node: 부모가 없는 최상위 노드
단말 노드 leaf node: 자식이 없는 노드
깊이 deapt: 루트 노드에서의 길이(출발 노드에서 목적지 노드까지 거쳐야하는 간선의 수)
트리의 높이 height: 루트 노드에서 가장 깊은 노드까지의 길이
이진 트리 Binary Tree: 최대 2개의 자식을 가질 수 있는 트리
우선순위 큐 Priority Queue: 우선순위에 따라서 데이터를 추출하는 자료구조. 힙(heap)을 이용해 구현
포화 이진 트리 Full Binary Tree: 리프 노드를 제외한 모든 노드가 2개의 자식 노드를 가지고있는 트리
완전 이진 트리 Complete Binary Tree: 모든 노드가 왼쪽 자식부터 채워진 트리
높이 균형 트리 Height Balanced Tree: 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1 이상 차이 나지않는 트리
힙 Heap: 원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조
최대 힙 Max Heap: 값이 큰 원소부터 추출
최소 힙 Min Heap: 값이 작은 원소부터 추출
원소의 삽입, 삭제 시 시간 복잡도: O(logN)
N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업: 정렬
정렬 시 시간 복잡도: O(NlogN)
루트 노드: 우선순위가 가장 높은 노드
최대 힙: 부모 노드가 자식 노드보다 값이 큰 완전 이진 트리. 루트 노드는 전체 트리에서 가장 큰 값을 가짐. 값이 큰 데이터가 우선순위
최소 힙: 부모 노드가 자식 노드보다 값이 작은 완전 이진 트리. 루트 노드는 전체 트리에서 가장 작은 값을 가짐. 값이 작은 데이터가 우선순위
최소 힙 구성 함수: Heapify(상향식 접근 방식)
부모로 거슬러 올라가며, 부모보다 자신이 더 작은 경우 위치를 교체
힙에 새로운 원소가 삽입될 때의 시간 복잡도: O(logN)
힙에 원소가 삭제될 때의 시간 복잡도: O(logN)
가장 마지막 노드가 루트 노드의 위치에 오도록 함 => 루트 노드에서부터 하향식으로 heapify() 진행
