[Algorithm] 힙(Heap)

📌 힙(Heap)이란?

• 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조
• 힙은 최대힙, 최소힙으로 나눠집니다.
• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
• 시간복잡도 = O(log n)

✅ 최대힙

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

key(부모) >= key(자식)

 

✅ 최소힙

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완진 이진트리

key(부모) <= key(자식)

 

🍀 힙의 구현

• 힙을 저장하는 표준적인 자료구조는 배열이다.
• 구현을 쉽게하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
  • 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
• 부모 노드와 자식 노드의 관계
  • 왼쪽 자식 인덱스 = (부모의 인덱스) * 2 
  • 오른쪽 자식 인덱스 = (부모의 인덱스) * 2 + 1 
  • 부모의 인덱스 = (자식의 인덱스) / 2

✅ 삽입 연산

1. 삽입하고자 하는 값을 트리의 가장 마지막 원소에 추가한다.
2. 부모 노드와의 대소관계를 비교하면서 만족할 때까지 자리 교환을 반복한다.

✅ 삭제 연산

1. 힙에서는 루트 노드만 삭제가 가능하므로 루트 노드를 제거한다.
   1. 최대 힙에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
3. 자식노드와 비교하여 조건이 만족할 때까지 이동시킨다.

 

📝 추가자료

• 힙구현