[자료구조] heap/ 최대 heap에서 insert

이런 max heap에서 원소 하나를 삽입한다고 해 보자. 

complete binary tree의 조건을 만족하려면, 원소 하나가 들어갔을 때 트리는 무조건 

\

저 자리에 들어갈 수 밖에 없다. 

 

삽입되는 원소의 정확한 위치를 결정하기 위해서는, 트리의 새 노드에서 시작해서 루트 쪽으로 올라가는 bubbling-up 방법을 사용하면 된다고 한다. 삽입되는 원소는 삽입이 완료된 뒤, 최대 힙이 되는 것이 확인될 때 까지 위쪽으로 계속 올라간다. 

 

예를 들어서 생각해보자! 새로운 원소가 30이라면, 바로 저 자리에 넣으면 된다. 그러나 값이 49이면 넣을 수 없다. 그러므로 31을 검은색 위치에 넣고, 최대 힙이 되는지 본다. 여전히 안 된다. 그럼 48을 그 자리에 넣는다. 여전히 안된다. 51을 그 자리에 넣는다. 이제야 된다!

 

이런식으로 구현을 하려면, 노드에서 자신의 부모 노드로 갈 수 있어야 한다. 

 

코드는 다음과 같다!

 

복잡도는 O(log2n)이다.