힙(Heap)

힙은 완전 이진 트리(Complete Binary Tree)의 일종으로, 부모 노드와 자식 노드 간에 특정한 조건을 만족하는 자료구조를 말한다. 완전 이진 트리란 부모 노드 밑에 자식 노드가 최대 2개까지 있고, 마지막 레벨을 제외한 모든 레벨에 노드가 완전히 채워져 있는 트리 구조를 말한다.

트리란?

힙의 종류

힙의 종류는 최대 힙(Max-Heap)과 최소 힙(Min-Heap)이 있다. 최대 힙은 모드 부모 노드가 그 자식 노드보다 크거나 같은 값을 갖는 특성을 가진다. 때문에 루트 노드는 전체 힙 중에서 가장 큰 값을 가진다.

반대로 최소 힙은 모든 부모 노드가 자식 노드보다 작거나 같다. 그리고 트리의 루트 노드는 전체 힙 중에서 가장 작은 값을 가진다.