6.Heap에 대해서 알아보자.
정의
- Complete Binary Tree
- A가 B의 부모노드이면 A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.
이진트리(Binary Tree)는 부모의 자식이 0~2개인 트리인데 이진트리의 모양 에 따라 이진트리를 분류 할 수 있다.
- Rooted Binary Tree 는 모든 노드의 자식이 최대 2개인 루트를 가진 트리
- Full Binary Tree 단말 노드가 아닌 모든 노드가 2개의 자식을 가진트리
- Complete Binary Tree 마지막 레벨을 제외하고 모든 노드가 채워진 이진트리, 마지막 레벨의 노드들은 왼쪽부터 채워져있다.
- Perfect Binary Tree 루트(root)에서 부터 말단노드(leaf)까지의 거리가 모두 같은 트리
이중 Heap 은 Complete Binary Tree 의 꼴을 하고 있다.
