힙(Heap)의 삭제 연산 과정

힙(Heap)의 삭제 연산 과정

루트 노드의 값이 가장 먼저 삭제된다. 최대 힙의 경우 최대값부터, 최소 힙의 경우 최솟값부터 삭제된다

최대 힙을 예로 들어 힙의 삭제 연산에 대해 알아보자 

 

루트 노드를 삭제하고, 마지막 노드를 루트 노드의 자리로 이동한다

 

최대 힙은 루트 노드에 최대값이 와야 한다. 삭제 연산 후 루트 노드의 값은 전체 노드 중 최댓값이 아니므로 재구조화 과정이 필요하다. 루트 노드의 자식 노드 중, 더 큰 값(6)과 루트 노드의 값(2)을 비교하고 swap한다

 

부모 노드의 값(2)이 자식 노드의 값(5) 보다 작으므로 swap을 진행해주어 최대 힙의 구조를 완성시킨다