힙(heap)은 힙의 특성(부모 자식관의 관계)을 만족하는 거의 완전한 트리(Almost Complete Tree)인 특수한 트리 기반의 자료구조이다.
힙(heap)이라는자료구조는 J.W.J. 윌리엄스(Williams)라는 영국의 컴퓨터과학자가 1964년에 힙 정렬 알고리즘을 고안하면서 최초로 설계 되었다.
자식 노드가 둘인 힙을 특별히 이진 힙(Binary Heap)이라 하며, 대부분 이진 힙이 널리 사용된다.
🤚완전이진트리(Complete Binary Tree) 란?
마지막 레벨을 제외하고 모든 레벨에 노드들이 완전히 채워져 있는 이진트리.
(마지막 레벨의 노드들은 왼쪽부터 채워져야 함.)
최소 힙(min heap)
은 부모가 항상 자식보다 작은 경우로 루트 노드가 가장 작은 값을 가지며,
최대 힙(max heap)
은 부모가 항상 자식보다 큰 경우로 루트 노드가 가장 큰 값을 가진다.(힙은 정렬된 구조가 아니다. 부모 자식 간의 관계만 정의할 뿐, 좌우 노드에 대한 대소관계는 정의하지 않는다.)
(시간복잡도: O(logn), 자세한 내용은 아래 추출 참조)
힙은 대표적으로 우선순위 큐뿐 아니라 이를 이용한 다익스트라 알고리즘에도 활용된다.
(다익스트라 알고리즘에서 힙(우선순위 큐)를 사용하여 시간복잡도를 O(V²)에서 O(Elogn)로 줄일 수 있다.)
또한 원래의 용도인 힙 정렬 과 최소 신장 트리(Minimum Spanning Tree)를 구현하는 프림 알고리즘(Prim's Algorithm) 등에도 활용되며, 중앙값의 근사값(Approximation)을 빠르게 구하는 데도 활용할 수 있다.
파이썬에서 우선순위 큐를 사용할 때 활용하는 heapq 모듈이 힙으로 구현되어 있다.
(heapq모듈은 최소 힙만 구현되어 있음.)
(우선순위 큐는 이진 힙으로 구현 -> 따라서 우선순우 큐는 배열로 구현)
인덱스 계산을 편하게 하기 위해서 1부터 시작
class BinaryHeap(object):
def __init__(self):
self.items = [None] # index를 1부터 시작하기 위해서 비어있는 값(None)을 index=0에 채운다.
def __len__(self): # 매직메소드(__method__), len(a) -> a.__len__() 호출
return len(self.items) - 1
힙에 요소를 삽입하기 위해서는 업힙(up-Heap) 연산을 수행해야 한다. 일반적으로 업힙 연산은 percolate_up()으로 정의한다.
- 요소를 가장 하위 레벨의 최대한 왼쪽에 삽입한다.(배열로 표현할 경우 가장 마지막에 삽입)
- 부모 값과 비교해 값이 더 작은 경우 위치를 변경한다.
- 계속해서 부모 값과 비교해 위치를 변경한다.(가장 작은 값인 경우 루트까지 올라간다.)
# 시간복잡도: log(n)
# => parent = i // 2 -> 절반씩 줄여나감, 로그(log(n)) 연산
# 삽입, 반복 구현
def _percolate_up(self):
i = len(self)
parent = i // 2 # parent_node_index = i -> child_node_index = 2i, 2i+1
while parent > 0:
# 추가한 node 값이 부모 node 값보다 작은 경우 스왑
if self.items[i] < self.items[parent]:
self.items[parent], self.items[i] = self.items[i], self.items[parent]
i = parent # 부모 노드로 index 변경
parent = i // 2
def insert(self, k):
self.items.append(k) # 배열 -> 가장 마지막 삽입
self._percolate_up()
최소 or 최대 값 추출 -> 루트 노드 추출
최소(min Heap) or 최대(max Heap) 값을 추출하는 것은 간단하다.
루트 노드를 추출
하면 된다. 따라서 시간복잡도는 O(1)인 것 같지만,
추출 이후 다시 힙을 구성해줘야 하기 때문에 시간복잡도는 O(logn)
이다.
# 시간복잡도: log(n)
# 추출, 재귀 구현
def _percolate_down(self, idx):
left = idx * 2
right = idx * 2 + 1
smallest = idx
# left 노드 값이 더 작은 경우 smallest 변경
if left <= len(self) and self.items[left] < self.items[smallest]:
smallest = left
# right 노드 값이 더 작은 경우 smallest 변경
if right <= len(self) and self.items[right] < self.items[smallest]:
smallest = right
# left or right 노드 값이 더 작아 smallest가 변경된 경우 swap 처리
if smallest != idx:
self.items[idx], self.items[smallest] = self.items[smallest], self.items[idx]
# 재귀 -> 탐색
self._percolate_down(smallest)
def extract(self):
extracted = self.items[1]
self.items[1] = self.items[len(self)] #마지막 요소, root Node에 할당
self.items.pop() # 할당 처리 후 필요없는 마지막 요소 제거
self._percolate_down(1)
return extracted
Reference)
파이썬 알고리즘 인터뷰
https://baeharam.github.io/posts/data-structure/heap/
https://devlog-wjdrbs96.tistory.com/43
https://galid1.tistory.com/485
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html