Heap

Concept

힙(Heap)은 특정한 규칙을 따르는 이진 트리입니다. 힙은 주로 우선순위 큐(Priority Queue)와 같은 응용 분야에서 사용되며, 최댓값을 찾아야 하거나, 최솟값을 찾아야 하는 자료구조 에서의 효율적인 삽입과 삭제 연산을 제공합니다. 힙은 다음과 같은 두 가지 주요 규칙을 따르는 이진 트리입니다. 위의 그림처럼, 왼쪽부터 아래 오른쪽으로 순서대로 인덱스 번호가 매겨집니다.

• 완전 이진 트리(Complete Binary Tree) 구조:
  힙은 완전 이진 트리 형태를 가져야 합니다. 즉, 모든 레벨이 꽉 차 있어야 하며, 마지막 레벨은 왼쪽에서 오른쪽으로 채워져야 합니다.

• 힙 속성(Heap Property):

  최대 힙 : 부모 노드의 값이 자식 노드의 값보다 크거나 같아야 합니다. 따라서 루트 노드에는 가장 큰 값이 위치합니다.
  최소 힙 : 부모 노드의 값이 자식 노드의 값보다 작거나 같아야 합니다. 따라서 루트 노드에는 가장 작은 값이 위치합니다.

Logic

힙은 노드의 추가와 삭제가 핵심 기능이며 이 기능에 대해서 살펴보겠습니다.

노드의 추가

그림과 같은 그래프가 존재할때, 2라는 숫자가 담긴, 노드가 추가될때, 처음에는 가장 낮은 인덱스에 위치하게 됩니다. 그리고 추가된 이 위치에서 부모 노드와 숫자를 비교합니다. 추가된 노드가 숫자가 더 작다면,

위 그림처럼 부모노드와 자리를 교체하고 다시한번 바뀐 위치에서의 부모노드와 크기를 비교합니다.

비교를 통해 최종적으로 2의 숫자를 가진 노드는 Root 노드에 위치하게 됩니다. 만약 부모노드와 숫자를 비교하여 부모노드가 숫자가 더 작았다면 해당 비교작업은 멈추고, 해당 형태를 보존했을 것입니다.

노드의 삭제

위의 그림처럼, Heap 자료구조의 노드 삭제는 해당 트리에서 가장 최솟값을 추출 하는 의미로써 사용되며, Root 의 위치한 노드가 사라지게 됩니다.

그리고 Root 노드의 위치에는 가장 낮은 인덱스에 있던 노드를 끌고와 배치합니다. 그리고 자신의 두개의 자식노드중 더 작은 숫자인 노드(5)와 비교하여, 자식노드가 숫자가 더 작다면,

위 그림처럼 자식노드와 자리를 교체하고 다시한번 바뀐 위치에서의 자식노드와 크기를 비교합니다. 지금 상황에서는 자식노드(8)가 한개밖에 없으니 해당 비교를 통해,

최종적으로 9의 숫자를 가진 노드는 그림과 같은 위치에 배치됩니다. 자식노드들과 숫자를 비교하여 자식노드들이 숫자가 더 컸다면 해당 비교작업은 멈추고, 해당 형태를 보존했을 것입니다.