Maxheap이란 트리구성에서 데이터값이 가장 큰 노드가 가장 root노드에 배치된다.
간단히 배열로써 구현하였다.
배열인덱스 1은 루트노드를 의미한다.
Maxheap tree에 push 하는법 : i가 트리의 크기(즉, 맨 마지막 노드) 로 부터 시작해 부모노드와 크기비교
만약 부모 노드가 더 크다면 maxheap이 유지되는것이니 그냥 마지막에 넣으면 되는데 부모노드가 더 작다면 부모노드를 내려야한다. 계속해서 최상단 root까지 비교해 거슬러 올라가는 식이다.
Maxheap tree에 pop 하는법 : pop이 어려운데, 이는 상단 부모노드를 한개 뺄시 아래의 균형이 깨진다.
따라서 자식들중 더 큰 노드를 다시 부모자리에 채우는 식이다.
'Data Structure' 카테고리의 다른 글
위너트리(Winner Tree) (0) | 2020.06.14 |
---|---|
이진탐색드리(Binary Search Tree) (0) | 2020.06.14 |
명제식 이진트리 (2) | 2020.06.14 |
트리의 순회(inorder, preorder, postorder, levelorder traversal) (0) | 2020.06.14 |
트리(Tree) (0) | 2020.06.14 |