1. 힙 (Heap)
: 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리 (노드 삽입 시, 최하단 왼쪽 노드부터 차례대로 삽입)
: 트리의 특별한 케이스
: 최대값과 최솟값을 찾으려면 O(logn)의 시간이 걸림 ( <> 배열의 경우 - O(n) )
: 최대 값을 구하기 위한 최대 힙 (Max Heap) / 최솟값을 구하기 위한 최소 힙 (Min Heap)으로 나뉨
* 규칙 (최대 힙의 경우)
: 해당 노드의 값 > = 자식 노드의 값
: 즉, 최대 힙의 경우 루트 -> 리프 방향으로 점점 값이 작음
: 완전 이진트리로, 왼쪽 노드부터 차례대로 삽입
** 이진 탐색 트리와의 차이점
: 이진 탐색 트리는 크기 순서가 왼쪽 자식 노드 < 현재 노드 < 오른쪽 자식 노드임
힙은 자식 노드 간의 크기 순서가 없음. 그저 자식 노드가 현재 노드보다 작거나 크다는 일정한 규칙만 존재함
2. 힙 동작 - 삽입/ 삭제
1) 구현
: 정렬 순서가 정해진 완전 이진 트리이기 때문에, 구현 시 배열을 활용함
: 구현의 편의를 위해 root 노드 인덱스 번호를 1로 지정
- 부모 노드 인덱스 = 자식 노드 인덱스 // 2
- 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 *2
- 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 *2 + 1
2) 데이터 삽입
: 왼쪽 최하단 노드부터 채워짐
: 우선 데이터를 채워 넣고, 크기 비교를 통해 노드의 위치를 정렬함
- Max heap) 삽입할 데이터가 클 경우
: 채워진 노드에서 부모 노드와 값 비교 -> 부모 노드 값보다 클 경우 swap
3) 데이터 삭제
: 힙의 목적이 최대값 또는 최솟값을 꺼내는 것이므로, 주로 최상단 노드를 삭제함
: 데이터가 삭제되면, 가장 마지막에 추가된 노드를 root 노드로 이동시킴
: 그 값이 자식 노드 값 보다 작을 경우, 자식 노드 중 가장 큰 값을 가진 노드와 swap (반복)
- Max Heap
class Heap:
def __init__(self,data):
self.heap_array = list()
self.heap_array.append(None) # root 노드의 인덱스가 1이 되게 하기 위해
self.heap_array.append(data)
def move_up(self,inserted_idx): # 부모 노드 값과의 swap 여부를 return
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 self.heap_array==0:
self.heap_array.append(None)
self.heap_array.append(data)
return True
self.heap_array.append(data)
# 부모 노드와 크기 비교 및 swap
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
def move_down(self, popped_idx): # swap 여부 판단
left_child_idx = popped_idx *2
right_child_idx = popped_idx *2 +1
if left_child_idx >=len(self.heap_array):
return False
elif right_child_idx >=len(self.heap_array):
if self.heap_array[left_child_idx] > self.heap_array[popped_idx]:
return True
else:
return False
else:
if self.heap_array[left_child_idx] > self.heap_array[right_child_idx]:
if self.heap_array[left_child_idx] > self.heap_array[popped_idx]
return True
else:
return False
else:
if self.heap_array[left_child_idx] > self.heap_array[popped_idx]
return True
else:
return False
def pop(self):
if len(self.heap_array) <=1:
return None
returned_data = self.heap_array[1] # root값을 return
self.heap_array[1] = self.heap_array[-1] # 마지막 저장 값을 root에 저장
del self.heap_array[-1]
popped_idx = 1
while self.move_down(popped_idx):
left_child_idx = popped_idx *2
right_child_idx = popped_idx*2+1
# 오른쪽 자식 노드가 없을 때
if right_child_idx >= len(self.heap_array):
if self.heap_array[left_child_idx] > self.heap_array[popped_idx]:
self.heap_array[left_child_idx], self.heap_array[popped_idx] = self.heap_array[popped_idx], self.heap_array[left_child_idx]
popped_idx = left_child_idx
# 자식 노드가 둘 다 있을 때
else:
if self.heap_array[left_child_idx] > self.heap_array[right_child_idx]:
if self.heap_array[left_child_idx] > self.heap_array[popped_idx]:
self.heap_array[left_child_idx], self.heap_array[popped_idx] = self.heap_array[popped_idx], self.heap_array[left_child_idx]
popped_idx = left_child_idx
else:
if self.heap_array[right_child_idx] > self.heap_array[popped_idx]:
self.heap_array[right_child_idx], self.heap_array[popped_idx] = self.heap_array[popped_idx], self.heap_array[right_child_idx]
popped_idx = right_child_idx
return returned_data