[자료구조] 힙(Heap)이란? 최대힙(Max Heap)과 최소힙(Min Heap)

힙(Heap)

• 최대 힙(Max Heap)
• 최소 힙(Min Heap)

 

1. 최대 힙(Max Heap)

• 최대 트리(Max Tree)는 각 노드의 키(Key)값이 (자식 노드가 있다면) 그 자식의 키(Key)값보다 작지 않은(=크거나 같은) 트리이다.
• 최대 힙(Max Heap)은 최대 트리(Max Tree)이면서 완전 이진 트리(Complete Binary Tree)이다.

2. 최소 힙(Min Heap)

• 최소 트리(Min Tree)는 각 노드의 키(Key)값이 (자식 노드가 있다면) 그 자식의 키(Key)값보다 크지 않은(=작거나 같은) 트리이다.
• 최소 힙(Min Heap)은 최소 트리(Min Tree)이면서 완전 이진 트리(Complete Binary Tree)이다.

 

+ 정리)

최대 힙(Max Heap) : 부모 노드는 자식 노드보다 작지만 않으면 된다. + 완전이진트리이다.

최소 힙(Min Heap) : 부모 노드는 자식 노드보다 크지만 않으면 된다. + 완전이진트리이다.

 

 

+ 추가설명) 그렇다면 완전 이진 트리(Complete Binary Tree)란 무엇인가?

완전 이진트리(Complete Binary Tree)는 노드를 삽입할 때, 왼쪽부터 차례대로 삽입하는 트리이다.

예를들어서 [그림 1]의 경우는 완전이진트리가 맞지만, [그림 2]와 같은 경우는 완전 이진트리가 아니다.

 

[그림 1]

 

[그림 2]

 

3. 최대 힙(Max Heap)에서의 삽입

예를들어, 아래 [그림 3(a)]처럼 5개의 원소를 가진 최대 힙이 있다고 하자.

최대 힙은 완전이진트리를 따르기 때문에 여기서 하나의 원소를 추가시킨다면 [그림 3(b)]처럼 된다.

삽입되는 원소의 정확한 위치를 결정하기 위해, 트리의 새 노드에서 시작해서 루트쪽으로 올라가는 방법을 사용한다.

삽입되는 원소는 새 노드에 삽입이 되고나서, 최대 힙이 될 때까지 위로 올라가는 과정을 반복한다.

부모 노드보다 값이 클 경우, 서로 교환하면서 위로 올라가는 과정을 반복하는 것이다.

 

[그림 3]

 

 

4. 최대 힙(Max Heap)에서의 삭제

최대 힙에서 원소를 삭제할 때는 힙(Heap)의 루트(Root)에서 삭제한다.

예를들어, [그림 3(a)]에서 원소를 삭제한다면 루트노드에 있는 숫자 21이 삭제된다.

[그림 4(a)]처럼 루트노드가 비워져 있는 상태이고, 가장 마지막 노드가 루트노드로 올라오게 된다.

새로 올라온 값이 제자리를 찾아갈 수 있도록 연산을 반복하면 된다.

[그림 4(b)]의 경우엔 루트노드에 있는 숫자 2가 자식노드 15, 20과 값을 비교한다.

둘다 2보다 크고, 이 중에서 20이 가장 크기때문에 숫자 2는 20과 자리를 서로 바꾸면 된다.

 

[그림 4]