힙(Heap)

개요

---

힙은 완전 이진 트리(Complete Binary Tree)의 일종으로 부모 자식 노드 간의 특정한 조건을 만족하는 자료구조이다.

모든 노드가 정렬되어 있지 않은 반정렬 상태이고, 이진 탐색 트리와 달리 중복 값이 허용된다.

최대 힙은 모든 부모 노드가 그 자식 노드보다 크거나 같은 값을 가지는 특성을 가지고 최소 힙은 모든 부모 노드가 그 자식 노드보다 작거나 같은 값을 가지는 특성을 가진다.

연산

---

트리의 각 노드에 번호를 붙이고 이 번호를 배열의 인덱스로 생각하면 힙은 배열로도 표현할 수 있다.

노드 구하기

• 루트 노드 인덱스가 0일 경우
  • 왼쪽 자식 : 부모 인덱스 * 2 + 1
  • 오른쪽 자식 : 부모 인덱스 * 2 + 2
  • 부모 : (자식 인덱스 - 1) / 2 (python이라면 소숫점이 남기에 // 연산자 사용하자)
• 루트 노드 인덱스가 1일 경우
  • 왼쪽 자식 : 부모 인덱스 * 2
  • 오른쪽 자식 : 부모 인덱스 * 2 + 1
  • 부모 : 자식 인덱스 / 2

삽입 연산

1. 완전 이진 트리의 마지막 노드에 이어서 새로운 노드를 추가
2. 추가된 새로운 노드를 부모의 노드와 비교하여 교환
3. 정상적인 힙 트리가 될 때(더 이상 부모 노드와 교환이 필요 없을 때)까지 2번을 반복
   • 최악의 경우에 새로 추가된 노드와 루트 노드까지 교환이 일어날 수 있기에 시간 복잡도는 O(log N)

삭제 연산

1. 루트 노드를 삭제
2. 마지막 노드를 루트 노드로 이동
3. 이동된 노드를 자식 노드와 비교하여 교환 (최대 힙에서는 자식 노드 중 더 큰 노드와, 최소 힙에서는 자식 노드 중 더 작은 노드와 교환)
4. 정상적인 힙 트리가 될 때(더 이상 자식 노드와 교환이 필요 없을 때)까지 3번을 반복
   • 최악의 경우에 이동된 노드와 리프 노드까지 교환이 일어날 수 있기에 시간 복잡도는 O(log N)

힙과 이진 탐색 트리의 차이

---

1. 속성 : 힙은 부모 자식 간의 크기 관계만 유지하지만, BST는 왼쪽 서브 트리의 모든 노드는 부모 노드보다 작고, 오른쪽 서브 트리의 모든 노드는 부모 노드보다 크다는 속성을 유지한다.
2. 균형 : 힙은 완전 이진 트리이므로 항상 균형이 잡혀 있지만, BST는 균형이 잡히지 않을 수 있다.
3. 최대/최소값 조회 : 힙은 최대/최소값 조회에 O(1), BST는 평균적으로 O(log N)이다.
4. 삽입/삭제 : 힙은 삽입과 삭제에 O(log N), BST는 평균적으로 O(log N)이나 트리의 균형이 깨질 경우 최악의 경우 O(N)이다.

힙의 시간 복잡도 정리

---

• 최소/최대값 검색 : O(1)
• 최소/최대값 추출 : O(log N)
• 삽입 : O(log N)
• 삭제 : O(log N)
• 배열로 힙 생성 : O(N) (힙을 배열로 표현할 때, 배열의 모든 요소를 힙으로 만드는 과정이 O(N))

참고

• https://sechoi.tistory.com/36
• https://velog.io/@gnwjd309/data-structure-heap