왜 사용하는가?
- Heap 정렬은
최대값이나최소값을 효과적으로 구하기 위한 방법이다. - 복잡도 : O(logn)
완전이진트리와 같이 맨 밑의 왼쪽 노드부터 삽입
특징
각 노드 (부모노드)은 자식노드 보다 무조건 크거나 같다 (Max Heap인 경우). 부모노드 > 자식노드들 을 만족한다. 이 점이 이진노드와의 차이점이다. 이진 노드는 부모노드와의 크기비교 상관없이 왼쪽노드 < 오른쪽노드 만 만족시키면 된다.
구현
Heap insert
15, 10, 8, 5, 4, 20 을 차례대로 넣는다고 생각해보자. Max heap의 목적은 최대값을 찾는 것이고, heap array의 맨 앞에 20 이 위치해야 한다.
그림과 같이 노드가 완성된다. 20이 들어갔을 때는 대소비교를 하여 위로 올라가는 과정을 보자.
구현을 할 때, 20 이 부모노드보다 작아지는 순간이 오거나, 가장 높이 올라갈 때까지 부모노드와 swap 을 해주면 된다.
class Heap():
def __init__(self, data):
self.heap_array = []
self.heap_array.append(None)
self.heap_array.append(data)
def move_up(self, inserted_idx): # 부모노드와 현재노드 비교 (부모노드 > 현재노드일 때 True)
if inserted_idx <= 1:
return False
parent_idx = inserted_idx // 2 # 부모노드 index (그림 참조)
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: # 안에 None만 있을 때
self.heap_array.append(data)
return True
self.heap_array.append(data)
inserted_idx = len(self.heap_array) - 1 # [None, 1, 2, 3]에서 최근 3이 삽입되었다면 idx = len(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
heap = Heap(15)
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
print(heap.heap_array)
# [None, 15, 10, 8, 5, 4]
위 그림을 보면 가장 최근에 삽입되었던 4 일 때, inserted_idx은 len(heap_array) - 1 = 5 이다. 4 의 부모노드는 10 인데, 10 은 inserted // 2 = 2 로 구할 수 있다.
자식노드가 부모노드보다 작아질 때까지 swap을 계속 해준다. 여기에서 20 을 넣어주면 다음과 같다.
heap = Heap(15)
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
heap.insert(20)
print(heap.heap_array)
# [None, 20, 10, 15, 5, 4, 8]
20 이 가장 앞으로 오는 것을 확인할 수 있고 최대값을 쉽게 구했다. 최소값은 부호의 방향만 반대로 해주면 된다.
Heap pop
이제 최대값인 맨 앞 요소를 뽑아내는 것이 중요하다. pop 메서드를 구현할 것이다. 단순히 빼오는 것이 아니라 맨 위에 있는 요소가 빠지면 다시 정렬해줘야 한다.
- Root 노트를 삭제
- 가장 아래에 있는 노드를 Root 노드로 이동
- Root 노드가 child 노드보다 작을 경우, 두 child 노드 중 큰 노드와 Root 노드를 swap
class Heap():
def __init__(self, data):
self.heap_array = []
self.heap_array.append(None)
self.heap_array.append(data)
def move_up(self, inserted_idx): # 부모노드와 현재노드 비교 (부모노드 > 현재노드일 때 True)
if inserted_idx <= 1:
return False
parent_idx = inserted_idx // 2 # 부모노드 index (그림 참조)
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: # 안에 None만 있을 때
self.heap_array.append(data)
return True
self.heap_array.append(data)
inserted_idx = len(self.heap_array) - 1 # [None, 1, 2, 3]에서 최근 3이 삽입되었다면 idx = len(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):
left_child_popped_idx = popped_idx*2
right_child_popped_idx = popped_idx*2 + 1
if left_child_popped_idx >= len(self.heap_array): # child가 없는 경우
return False
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
else: # left right child 둘다 있는 경우
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] # Root node
self.heap_array[1] = self.heap_array[-1] # 맨 마지막 node가 root node로 이동
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
if right_child_popped_idx >= len(self.heap_array): # 왼쪽 child만 있는 경우
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:
# child node 중에서 오른쪽
if self.heap_array[left_child_popped_idx] > self.heap_array[right_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:
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
heap = Heap(15)
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
heap.insert(20)
print(heap.pop())
print(heap.pop())
print(heap.pop())
print(heap.pop())
print(heap.heap_array)
# 20
# 15
# 10
# 8
# [None, 5, 4]
파이썬 모듈
파이썬에서 간단하게 heapq 을 불러와서 사용할 수 있다.
import heapq
추가
import heapq
heap = []
heapq.heappush(heap, 4)
print(heap)
heapq.heappush(heap, 8)
print(heap)
heapq.heappush(heap, 2)
print(heap)
heapq.heappush(heap, 11)
print(heap)
heapq.heappush(heap, 15)
print(heap)
# [4]
# [4, 8]
# [2, 8, 4]
# [2, 8, 4]
# [2, 8, 4, 11]
# [2, 8, 4, 11, 15]
heapq 을 이용하면 최소 heap으로 구현되는 것을 알 수 있다. 최대 heap을 구하려면 -을 붙여서 넣어둔 다음 pop 할 때, -을 다시 붙여서 뱉으면 된다.
삭제
print(heapq.heappop(heap))
print(heap)
# 2
# [4, 8, 15, 11]
List을 Heap으로 변환
heap = [11, 15, 8, 2, 4]
heapq.heapify(heap)
print(heap)
# [2, 4, 8, 15, 11]
최대 heap
최대를 비교하기 위해 - 가 붙은 수를 앞에 세우고 tuple 형태로 heap에 집어 넣는다.
num = [11, 15, 8, 2, 4]
heap = []
for n in num:
heapq.heappush(heap, (-n, n))
while heap:
print(heapq.heappop(heap)[1])
# 15
# 11
# 8
# 4
# 2