트리
- 최하단 level의 노드를 leaf 노드라고도 부릅니다.
- 모든 노드는 하나의 부모 노드를 가집니다.
이진 트리
각 자식 노드들이 최대 2개까지 가지는 트리입니다.
- 마지막 레벨을 제외한 모든 노드가 채워진 완전 이진 트리
- 모든 노드가 2개씩 꽉 채워진 포화 이진 트리
- 한 방향으로만 나아가는 편향 트리
등이 있습니다.
우선순위 큐
FIFO인 큐와 달리, 우선순위가 높은 큐가 먼저 빠져나가는 큐 입니다.
다만, 우선순위 큐는 자료구조가 아닌 개념 입니다.
이때, 힙은 우선 순위 큐를 구현하기 굉장히 적합한 방법 중 하나입니다.
힙
이진 트리 형태를 가지며, 우선순위가 높은 요소가 먼저 나가기 위해
요소가 삽입, 삭제될 때 바로 정렬되는 특징이 있습니다.
때문에 힙 노드 삭제시, root 노드가 먼저 빠져나갑니다.
종류는 루트가 가장 큰 값인 최대 힙, 가장 작은 값인 최소 힙이 있습니다.
마무리
최근 코딩 테스트 문제에 상당 시간을 투자하고 있습니다.
평소 프로그래머스 lv2 문제도 겨우겨우 조금씩 해결하고 있는데, 갑자기 lv3 문제들을 해결하려니,
어려움이 없잖아 있습니다.. ;ㅅ;
언젠가는 나아지겠죠..?
