[자료구조] 힙(heap)이란

힙(heap) 자료구조란? 완전 이진 트리를 기본으로 한 자료구조로서, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었다. 여기서 완전 이진 트리란, 마지막 레벨을 제외한 모든 레벨의 node가 완전히 채워져 있으며 마지막 레벨의 노드들은 가능한 한 왼쪽부터 채워져 있는 구조를 말한다. 완전 이진 트리에 대해서는 이 글을 참고하면 좋을 것 같다. 힙의 종류 힙의 종류에는 두가지가 있다. 부모 노드의 값이 자식 노드의 값보다 항상 큰 힙을 최대 힙(max heap), 부모 노드의 값이 자식 노드의 값보다 항상 작은 힙을 최소 힙(min heap)이라고 한다. 값의 대소 관계는 부모 노드와 자식 노드 간에만 성립하고, 형제 노드 간에는 성립하지 않는다는 특징을 갖는다. 힙의 구현 힙을 저장하는..