[Data Structure] Heap
Heap 힙
- 데이터에서 최대값이나 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리
- 배열에 데이터를 넣고 최대값이나 최소값을 찾으려면 O(n)의 시간이 걸리지만, 힙에서는 O(logn)이 걸림
- 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 등에 활용됨
- 힙에는 부모노드의 키 값이 자식노드의 키 값보다 항상 큰 ‘최대 힙’과 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 ‘최소 힙’ 두가지의 종류가 있음
- 일반적으로 힙을 저장하는 자료구조로는 배열로 구현
- 구현의 편의성을 위해 배열의 첫번째 인덱스(0)은 None으로 비워 둠
- (부모 노드 인덱스) = (자식 노드 인덱스) // 2
- (왼쪽 자식 노드 인덱스) = (부모 노드 인덱스) * 2
- (오른쪽 자식 노드 인덱스) = (부모 노드 인덱스) * 2 + 1
- 완전 이진 트리인 힙과 이진 탐색 트리는 여러 차이점이 있음
- 힙은 각 노드의 값이 자식 노드보다 크거나 같음 (최대 힙일 경우 / 최소 힙이면 반대)
- 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고 오른쪽 자식 노드가 가장 크지만, 힙은 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
- 이진 탐색 트리는 탐색을 위한 구조이고 힙은 최대,최소값 검색을 위한 구조 중 하나
힙 구현
- 힙에 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입 한 후 새 노드를 부모 노드들과 교환하여 힙의 성질을 만족시킴
- 힙의 삽입에는 O(logn)의 시간이 소요됨
- 최대 힙에서 최대값은 루트 노드이므로 루트 노드 삭제 후 삭제된 힙의 마지막 노드를 루트 노드에 가져와서 힙을 재구성 함
- 힙의 삭제에는 O(logn)의 시간이 소요됨
class Heap:
def __init__(self, data):
self.heap_array = list()
self.heap_array.append(None)
self.heap_array.append(data)
def move_down(self, popped_idx):
left_child_popped_idx = popped_idx * 2
right_child_popped_idx = popped_idx * 2 + 1
# case1: 자식 노드가 없을 때
if left_child_popped_idx >= len(self.heap_array):
return False
# case2: 오른쪽 자식 노드만 없을 때
elif right_child_popped_idx >= len(self.heap_array):
if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
return True
else:
return False
# case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
else:
if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:
if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
return True
else:
return False
else:
if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
return True
else:
return False
def pop(self):
if len(self.heap_array) <= 1:
return None
returned_data = self.heap_array[1]
self.heap_array[1] = self.heap_array[-1]
del self.heap_array[-1]
popped_idx = 1
while self.move_down(popped_idx):
left_child_popped_idx = popped_idx * 2
right_child_popped_idx = popped_idx * 2 + 1
# case2: 오른쪽 자식 노드만 없을 때
if right_child_popped_idx >= len(self.heap_array):
if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
popped_idx = left_child_popped_idx
# case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
else:
if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:
if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
popped_idx = left_child_popped_idx
else:
if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
self.heap_array[popped_idx], self.heap_array[right_child_popped_idx] = self.heap_array[right_child_popped_idx], self.heap_array[popped_idx]
popped_idx = right_child_popped_idx
return returned_data
def move_up(self, inserted_idx):
if inserted_idx <= 1:
return False
parent_idx = inserted_idx // 2
if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
return True
else:
return False
def insert(self, data):
if len(self.heap_array) == 1:
self.heap_array.append(data)
return True
self.heap_array.append(data)
inserted_idx = len(self.heap_array) - 1
while self.move_up(inserted_idx):
parent_idx = inserted_idx // 2
self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
inserted_idx = parent_idx
return True
힙의 연산의 시간 복잡도 정리
| 힙 연산 | 시간 복잡도 |
|---|---|
| make-heap | O(nlogn) |
| find-max | O(1) |
| insert | O(logn) |
| delete-max | O(logn) |
| 리프 레벨까지 도달 | O(logn) |
- Search를 효율적으로 할 수 있는 자료구조가 아니기 때문에 굳이 구현하지 않음
- 가장 큰(작은) 값을 찾거나 지우는 연산이 많은 곳에 효율적
참고
잔재미코딩
신찬수 교수님 유튜브
위키 백과
Heee’s Development Blog
