최근 수정:
Heap. 힙. Hip이 아니다!!
트리 형태의 자료구조 중의 하나로, 부모 노드는 자식 노드보다 항상 크거나 (Max Heap) 항상 작아야 (Min Heap) 한다는 성질을 가진다. 즉, 최솟값 혹은 최댓값은 항상 루트에 있다!
힙에는 여러 종류가 있지만 주로 사용되는 것이 이진 힙이므로 여기서는 이진 힙에 대해 설명한다. 이진 힙 (Binary Heap)은 이진 트리를 이용한 힙으로 완전 이진 트리 구조를 가진다. 구현은 배열을 사용하여 꽤나 간단히 할 수 있다.
또한, 부모가 자식보다 크면 Max Heap, 작으면 Min Heap이고, 구현은 부등호만 빼면 서로 비슷하다.
힙과 우선순위 큐를 헷갈릴 수 있으나, 엄연히 다른 것이다! 우선순위 큐는 말 그대로 우선순위에 따라 데이터가 나오는 큐이며, 힙은 부모 노드는 자식 노드와의 관계를 이용한 자료구조이다. 우선순위 큐를 힙으로 구현할 수 있는 것이지 둘은 구분하도록 하자.