[자료구조]힙(Heap)

힙(Heap)은 무엇인가를 차곡차곡 쌓아 올린 더미라는 뜻을 가지고 있다.

그런 뜻을 가진 힙(Heap)이..

 

이 자료구조에서의 힙(Heap)은..

간단히 정의를 내리자면

 

힙은 완전 이진 트리이다. 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다.

루트노드에 저장된 값이 가장 커야 한다.

 

위 문장에서 말하는 형태의 이진트리는.. 다음 그림들과 같다.

위와 같이 루트 노드로 올라갈수록 값이 커지는 완전 이진 트리를 '최대 힙(Max Heap)' 이라 한다.

 

이번에는 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리를 '최소 힙(Min Heap)'이라 한다.