4-1) 힙(Heap) - 힙과 트리, tree levels, 추가와 제거

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

트리 (Tree) 

가계도처럼 노드를 나무 형태로 연결한 비선형 자료구조를 트리라고 한다. 트리를 구성하고 있는 각각의 기본 요소는 노드로, 노드는 부모, 자식 형태로 이어진다.

 

• 루트 (root): 트리의 시작 부분. 부모가 없는 최상위 노드. 루트를 이용해 트리를 탐색한다.
• 리프, 단말노드 (leaf): 자식 노드가 없는 노드.
• 간선 (edge): 두 노드를 연결하는 선. 뿌리로부터의 간선의 수에 따라 level을 나눈다. ( 루트는 0 level)
• 형제 노드(sibling): 같은 부모를 가지는 노드.

 

힙 (Heap)

 

힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기반으로 한 자료구조이다.

 

힙에는 두 가지 규칙이 있다.

- parent is > children  MAX HEAP

- parent is < children  MIN HEAP

 

힙에는 최대 힙(max heap)과 최소 힙(min heap)이 있다. 부모 노드가 자식 노드보다 크면 최대 힙, 반대이면 최소 힙이다.

가장 큰 숫자가 루트에 있게 하려면 최대 힙, 가장 작은 숫자로부터 시작하려면 최소 힙을 사용하면 된다.

 

height(높이) : 루트에서부터 가장 먼 잎까지 가는데 거치게 되는 간선의 개수  = log​2​​(n+1)−1

 

추가와 제거

힙에 새로운 데이터를 추가하거나 제거할 때 최대 힙이면 부모 노드가 자식 노드보다 커야 하고, 최소 힙은 자식 노드가 부모 노드보다 커야 한다.

 

 

노드 추가 (add)

1. 비어있는 공간에 노드를 추가한다.
2. 힙의 종류에 따라 부모와 자식의 크기를 비교하고 두 노드를 바꿔준다. (trickle up)

 

루트 제거 (remove)

무언가를 제거할 때 힙에서는 항상 루트를 제거해야 한다. 

 

1. 루트를 제거한다.
2. 트리의 마지막 요소를 루트에 넣어준다.
3. 루트에서 시작하여 두 자식 중 큰 노드와 바꿔주어 힙의 규칙을 만족하게 합니다. (trickle down)