자료구조 힙(Heap) 알아보기

자료구조 힙(Heap) 알아보기

 

힙(Heap)은 무엇인가?

힙은 완전 이진 트리(Complete binary tree)의 한 종류이다.

• 완전 이진 트리에는 마지막 레벨을 제외하고는 빈 노드가 존재하지 않는다.
• 따라서 배열로 구현하기에 적합한 이진 트리이다.
• 루트 노드가 그 트리의 최댓값 혹은 최솟값을 가진다.
  • 루트 노드가 트리의 최댓값을 가지면 최대 힙(Max heap)
  • 루트 노드가 트리의 최솟값을 가지면 최소 힙(Min heap)

최대 힙과 최소 힙

 

힙의 종류

최대 힙 (Max heap)

• 최대 힙은 각 노드의 값이 자식 노드의 값보다 크거나 같은 트리이다.
• 부모 노드의 Key 값 >= 자식 노드의 Key 값
• 루트 노드의 Key 값 = 트리의 최댓값

최소 힙 (Min heap)

• 최소 힙은 각 노드의 값이 자식 노드의 값보다 작거나 같은 트리이다.
• 부모 노드의 Key 값 <= 자식 노드의 Key 값
• 루트 노드의 Key 값 = 트리의 최솟값

* 최대 힙과 최소 힙을 만족하는 트리가 되기 위해서는 트리가 완전 이진 트리여야만 한다.

* 힙은 느슨한 정렬 상태를 유지한다.

• 최대 힙의 경우 각 노드 값이 자식 노드의 값보다 크거나 같다.
• 하지만 각 노드가 모든 하위 레벨의 노드보다 크거나 같지는 않다.

느슨한 정렬 상태

 

배열을 이용한 힙의 추상 자료형

• 히프 생성
• 히프 삭제
• 자료 추가
• 자료 제거
  • 힙에서는 자료를 제거할때 루트 노드가 제거되어 반환된다.
  • 최대 힙이라면 루트 노드가 제거되면 다음으로 큰 값이 새로운 루트 노드가 된다.
  • 최소 힙이라면 루트 노드가 제거되면 다음으로 작은 값이 새로운 루트 노드가 된다.

힙에서는 자료를 추가, 자료를 제거 하는 두가지 연산이 필요하다.

 

 

배열 힙에 필요한 연산

자료 추가

1. 히프에 새로운 노드가 추가 될때, 새로운 노드는 먼저 트리의 가장 마지막 자리에 임시로 저장된다.
2. 노드 위치 바꾸기
   • 최대 힙일때 : 새로 추가된 노드의 키 값이 부모 노드의 키 값보다 크다면 새로 추가된 노드와 부모 노드의 위치를 바꾼다. 최대 힙의 조건을 만족할때까지 반복한다.
   • 최소 힙일때: 새로 추가된 노드의 키 값이 부모 노드의 키 값보다 작다면 새로 추가된 노드와 부모 노드의 위치를 바꾼다. 최소 힙의 조건을 만족할때까지 반복한다.

마지막 위치에 임시로 저장

 

노드의 키 값을 비교

만약 이진 트리가 꽉 차 있는 포화 이진 트리라면 새로운 자료를 추가하기 위해서 새로운 레벨을 추가하고 새로운 레벨의 가장 왼쪽에 자료를 추가하면 된다.

포화 이진 트리에 자료 추가

 

 

자료 제거

1. 루트 노드를 제거한다
   1. 최대 힙이라면 루트 노드는 트리에서 가장 최댓값
   2. 최소 힙이라면 루트 노드는 트리에서 가장 최솟값
2. 비어있는 루트노드에 트리의 마지막 노드를 임시로 이동시킨다.
3. 힙의 조건을 만족시키위해 노드의 값을 비교하여 위치를 바꾼다.

루트 노드 제거후 마지막 노드를 임시 이동

자식 노드와 키 값을 비교한후 이동