자료구조 - 힙

힙이란 무엇인가

• 부모노드가 자식노드보다 무조건 크거나 작은 완전 이진트리 구조의 자료구조이다. 
  • 완전 이진 트리: 마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진트리
• 최대힙 : 부모 노드의 값이 자식노드의 값보다 항상 크다
• 최소힙: 부모 노드의 값이 자식 노드의 값보다 항상 작다.
• 중복값을 허용한다.

 

왜 힙은 배열로 구현할까?

완전 이진 트리를 기본으로 하기에 빈 공간이 없어 배열로 구현하기 용이하다.

• 루트 노드를 배열의 0번 인덱스에 저장
• 각 노드를 기점으로 왼쪽 자식 노드는 a[i∗2+1], 오른쪽 자식 노드는 a[i∗2+2] 인덱스에 저장
• 특정 인덱스 노드에서 부모 노드는 a[(i−1)//2]

 

이진트리와 차이점?

• 힙은 각 노드와 값이 자식노드보다 크거나 같다.
• 완전 이진트리의 경우 값의 크기가 오른쪽 자식노드> 부모노드>왼쪽 자식노드 순이다.
• 완전 이진트리는 탐색을 위한 구조, 힙은 최대/최소값을 위한 구조이다.

 

 

---

힙 연산 과정

재구조화(heapify)

힙에서 삽입 삭제가 일어나면 경우에 따라 힙의 조건이 깨질 수 있다. 이런 경우에 힙의 조건을 만족하도록 노드들의 위치를 재구조화를 해주어야 한다. 이때 부모와 자식의 값을 바꾸는 과정을 swap 이라고 한다.

 

삽입(Insert)

• 힙은 완전 이진 트리이기 때문에 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워진다.

가장 말단의 노드에 11을 삽입한다.

부모노드와 비교해서 더 크다면 자리를 바꾼다.(swap)

 

swap 과정을 반복하여 최대 힙 구조가 유지되면서 삽입 과정이 완료된다.

 

최악의 경우 말단에 삽입한 원소가 루트까지 올라가게 된다. 이때 비교 횟수는 트리의 높이만큼이므로 시간 복잡도는 O(logN)이다.

 

삭제 (Delete)

최대힙에는 최대값(루트노드)을 삭제, 최소힙에서는 최소값(루트노드)을 삭제하는 것이 일반적이다.

루트노드가 삭제되면 가장 말단 노드를 루트노드 자리에 대체한 후 재구조화 과정을 수행한다.

최대힙 이므로 최대값 10 삭제

 

가장 말단노드인 1을 루트노드로 대체한다.

 

자식 노드인 9와 5중 더 큰 값인 9와 위치를 교환한다.

 

 

이 과정을 반복하여 힙 구조를 완성한다.

 

최악의 경우 루트노드에서 말단 노드까지 내려오므로 비교 횟수는 트리의 높이 만큼이다.

따라서 시간 복잡도는 O(logN)이다.

 

조회/탐색

최대값 최솟값은 최대힙,최소힙에서 제일 앞에 있는 값을 가져오기만 하면 된다. 따라서 시간 복잡도는 O(1)이다.

 

 

 

---

코드 구현

파이썬에서는 heapq 라이브러리를 사용해 구현할 수 있다. (최소힙만 제공)

 

최소힙 삽입/삭제

import heapq

# 기존 힙에 넣을 값들
h_min = [50, 10, 20]

# heapify
heapq.heapify(h_min)
print("heapify 직후 상태:", h_min)

# 15 삽입
heapq.heappush(h_min, 15)
print("15 삽입 후:", h_min) 

# 최솟값 삭제
smallest = heapq.heappop(h_min)
print("삭제된 최솟값:", smallest)    
print("삭제 후 최종 상태:", h_min)

 

출력 결과

최대힙 삽입/삭제

import heapq

# 초기 데이터를 (우선순위, 실제값) 튜플로 준비
h_max = [(-50, 50), (-10, 10), (-20, 20)]

# heapify: 튜플의 첫 번째 원소(-값) 기준으로 최대 힙 변환
heapq.heapify(h_max)
print("heapify 직후 상태:", h_max)  #-50이 맨 앞

# 삽입
# 30을 (-30, 30) 형태로 삽입
heapq.heappush(h_max, (-30, 30))
print("30 삽입 후:", h_max)

# 삭제
# 꺼낸 튜플에서 1번 인덱스의 값만
largest = heapq.heappop(h_max)[1]
print("삭제된 최댓값:", largest)  
print("삭제 후 최종 상태:", h_max)   # 두 번째로 컸던 30을 가진 튜플이 맨 앞으로 이동

출력결과

• heapq 모듈이 내부적으로 최소힙만 지원한다. (늘 작은 값을 루트노드로 가져오려고 함)
• 그래서 최대힙은 데이터에 음수를 붙여서 최소힙에 넣는 꼼수를 썼다.
  • 10,20,50을 넣으면 최소힙에 따라 10을 가장 루트노드로 가져오려고 함
  • 여기서 음수를 곱하면 원래 50 < -20 < -10 이 되므로 -50이 루트노드가 됨
  • 데이터를 꺼낼 때 다시 음수를 곱하면 결과적으로는 최대힙을 구현한 것과 같음