트리 - Max heap

 

Maxheap이란 트리구성에서 데이터값이 가장 큰 노드가 가장 root노드에 배치된다.

 

 

간단히 배열로써 구현하였다.

배열인덱스 1은 루트노드를 의미한다.

 

 

Maxheap tree에 push 하는법 : i가 트리의 크기(즉, 맨 마지막 노드) 로 부터 시작해 부모노드와 크기비교

만약 부모 노드가 더 크다면 maxheap이 유지되는것이니 그냥 마지막에 넣으면 되는데 부모노드가 더 작다면 부모노드를 내려야한다. 계속해서 최상단 root까지 비교해 거슬러 올라가는 식이다.

 

Maxheap tree에 pop 하는법 : pop이 어려운데, 이는 상단 부모노드를 한개 뺄시 아래의 균형이 깨진다.

따라서 자식들중 더 큰 노드를 다시 부모자리에 채우는 식이다.