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