[자료구조] 힙(Heap) 2
in Study on Data Structure
Max Heap의 파이썬 구현
파이썬의 Heapq 라이브러리
사실 파이썬에는 Heap을 위한 라이브러리가 구현되어 있긴 하다.
import heapq
Heap = []
heapq.heappush(Heap, 1)
heapq.heappush(Heap, 5)
heapq.heappush(Heap, 10)
print(Heap)
# 결과 : [1, 10, 5]
heapq.heappop(Heap)
print(Heap)
# 결과 : [5, 10]
heapq 라이브러리를 사용하면 우선순위 큐에 대한 코드를 쉽게 짤 수 있다.
하지만 직접 구현해서 해보는 것도 참을 순 없지.
파이썬 코드로 Max Heap 구현하기
코드 참고 :
class heap:
def __init__(self, data):
self.heap_array = list() # 인덱스 계산을 편하게 하기 위함.
self.heap_array.append(None) # (0번 인덱스 비워두기)
self.heap_array.append(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):
# 진짜 만약에 힙의 길이가 0이면?
if len(self.heap_array) == 0:
self.heap_array = list()
self.heap_array = None # (0번 인덱스 비워두기)
self.heap_array.append(data)
return True
# 자연스럽게 이진트리 구조로 만들어지기 때문에 추가해주면 됨.
self.heap_array.append(data)
# 인덱스값과 리스트의 길이를 맞추기 위해서 0번 인덱스에
# None을 삽입했으므로, 실제 idx값을 구하려면 1을 뺄 것.
inserted_idx = len(self.heap_array) - 1
# swap 하는 과정
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
우선 삽입부에 대해서 구현을 하자면 이렇게 할 수 있을 것 같다.
힙은 인덱스 구조가 위와 같이 나타나는데, 왼쪽 자식노드는 부모노드의 2배, 오른쪽 자식 노드는 부모노드의 2배 + 1 이라는 것을 알 수 있다.
왼쪽 자식노드부터 순서대로 채워지기 때문에 가능한 구조이다.
그래서 데이터를 채우고 나서, index를 계산하여 해당 index 내 값을 비교하면서 재배치를 하는 형태로 코드가 짜여져있다.
# Test Code
My = heap(10)
My.insert(5)
print(My.heap_array)
My.insert(8)
print(My.heap_array)
My.insert(12)
print(My.heap_array)
My.insert(4)
print(My.heap_array)
My.insert(11)
print(My.heap_array)
My.insert(15)
print(My.heap_array)
# 출력 결과
[None, 10, 5]
[None, 10, 5, 8]
[None, 12, 10, 8, 5]
[None, 12, 10, 8, 5, 4]
[None, 12, 10, 11, 5, 4, 8]
[None, 15, 10, 12, 5, 4, 8, 11]
시험 해보면 위와 같다.
# 힙 데이터의 삭제(pop)
def move_down(self, popped_idx):
left_child_popped_idx = popped_idx * 2
right_child_popped_idx = popped_idx * 2 + 1
# Case 1 : 왼쪽 자식노드도 없을 때
if left_child_popped_idx >= len(self.heap_array):
return False
# Case 2 : 오른쪽 자식 노드만 없을 때
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
# Case 3 : 왼쪽, 오른쪽 자식노드 모두 있을 때
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
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
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
그리고 삭제과정도 위와 같다.
흐름을 요약하면,
- 제일 앞에 있는 데이터를 pop 할 테니 따로 빼둔다.
- 맨 끝에 있는 데이터를 루트노드로 이동한다.
- 그리고 Heap의 맨 뒤를 삭제한다.
- index 계산을 하여 값들을 재배치한다.
# Test Code
My.heap_array = [None, 15, 10, 12, 5, 4, 8, 11]
My.pop()
print(My.heap_array)
My.pop()
print(My.heap_array)
My.pop()
print(My.heap_array)
# 출력 결과
[None, 12, 10, 11, 5, 4, 8]
[None, 11, 10, 8, 5, 4]
[None, 10, 5, 8, 4]
순서대로 15, 12, 11이 삭제되었고, 부모노드의 값이 자식노드의 값보다 크도록 재배치 된 것도 확인할 수 있다.
코드 고치기
코드를 치면서 아쉬웠던 점은,
- heap_array를 출력하면 맨 앞의 None이 거슬린다.
- 중복코드가 많이 있다.
조금 더 깔끔하게 만들어보자.
우선, None이 있는 이유는 단순히 인덱스 계산을 편하게 하기 위함이다.
그렇다면, 인덱스 계산과정 앞에다가 잠깐 맨 앞에 None을 넣어주고 다 끝나면 None을 삭제하면 되는 것으로 해결된다.
def make_heap(self, data):
self.heap_array = list()
self.heap_array.append(data)
return
def __init__(self, data):
self.make_heap(data)
def exchange(self, list_input, idx_1, idx_2):
list_input[idx_1], list_input[idx_2] = list_input[idx_2], list_input[idx_1]
return list_input, idx_2
def insert(self, data):
# 진짜 만약에 힙의 길이가 0이면?
if len(self.heap_array) == 0:
self.make_heap(data)
return True
# 자연스럽게 이진트리 구조로 만들어지기 때문에 추가해주면 됨.
self.heap_array.append(data)
# 인덱스값의 계산을 편하게 하기 위해서
# 계산 과정시에는 리스트 맨 앞에 None을 임의로 추가
self.heap_array.insert(0, None)
# None을 삽입했으므로, 실제 idx값을 구하려면 1을 뺄 것.
inserted_idx = len(self.heap_array) - 1
...
따라서, 중복 코드도 수정할 겸 make_heap코드를 따로 만들었고, __init__도 위와 같이 수정하였으며, insert 함수의 초반부를 위와 같이 수정했다.
# 계산이 끝났으니 맨 앞에 넣어두었던 None 삭제
del self.heap_array[0]
# Test Code
My = heap(10)
My.insert(5)
print(My.heap_array)
My.insert(8)
print(My.heap_array)
My.insert(12)
print(My.heap_array)
My.insert(4)
print(My.heap_array)
My.insert(11)
print(My.heap_array)
My.insert(15)
print(My.heap_array)
# 출력 결과
[10, 5]
[10, 5, 8]
[12, 10, 8, 5]
[12, 10, 8, 5, 4]
[12, 10, 11, 5, 4, 8]
[15, 10, 12, 5, 4, 8, 11]
수정 전과 똑같이 정상적으로 구동한다!
# pop 함수 초반부
def pop(self):
if len(self.heap_array) < 1:
return None
# 계산 과정에서 인덱스 계산을 편하게 하기 위해서
# 계산 과정시에는 리스트 맨 앞에 None을 임의로 추가
self.heap_array.insert(0, None)
...
# pop 함수 후반부 swap 과정 이후
del self.heap_array[0]
return returned_data
pop 함수도 위와 같이 None을 추가했다가 다시 빼는 과정을 넣어주었다.
# Test Code
My.heap_array = [15, 10, 12, 5, 4, 8, 11]
My.pop()
print(My.heap_array)
My.pop()
print(My.heap_array)
My.pop()
print(My.heap_array)
# 출력 결과
[12, 10, 11, 5, 4, 8]
[11, 10, 8, 5, 4]
[10, 5, 8, 4]
똑같이 작동이 잘 되는 것을 볼 수 있다!
이제 다음으로 중복코드를 없애보자.
인덱스를 계산하고, 값을 서로 비교하는 과정에서 중복코드가 많이 발생했다.
그런데 여기서 중복된 부분을 살펴보니, 인덱스를 계산하고, 부모노드보다 자식노드의 값이 더 크면 두 값을 서로 바꿔주는 것이 핵심이었다.
def insert(self, data):
# 진짜 만약에 힙의 길이가 0이면?
if len(self.heap_array) == 0:
self.make_heap(data)
return True
# 자연스럽게 이진트리 구조로 만들어지기 때문에 추가해주면 됨.
self.heap_array.append(data)
# 인덱스값의 계산을 편하게 하기 위해서
# 계산 과정시에는 리스트 맨 앞에 None을 임의로 추가
self.heap_array.insert(0, None)
# None을 삽입했으므로, 실제 idx값을 구하려면 1을 뺄 것.
inserted_idx = len(self.heap_array) - 1
# swap 하는 과정
while 1:
parent_idx = inserted_idx // 2
if inserted_idx <= 1:
break
if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
else:
break
inserted_idx = parent_idx
# 계산이 끝났으니 맨 앞에 넣어두었던 None 삭제
del self.heap_array[0]
return True
따라서, 원래 있었던 move_up 함수를 삭제했고, 무한루프의 while구문 내의 if-break문으로 대체하였다.
그리고 swap이 끝난 지점에서 None을 다시 빼주는 코드도 추가 했다.
또한, 삽입과 삭제를 포함한 전체 과정 중 swap하는 파트, 즉
array[idx_1], array[idx_2] = array[idx_2], array[idx_1]
idx_1 = idx_2
와 같은 형식을 띄는 부분은 다른 함수를 정의하였다. 아래 코드처럼.
def exchange(self, list_input, idx_1, idx_2):
list_input[idx_1], list_input[idx_2] = list_input[idx_2], list_input[idx_1]
return list_input, idx_2
self.heap_array, inserted_idx = self.exchange(self.heap_array, inserted_idx, parent_idx)
이런 식으로 작동하게 된다.
따라서 이렇게 수정된 삽입과정 코드는 아래와 같다.
def make_heap(self, data):
self.heap_array = list()
self.heap_array.append(data)
return
def __init__(self, data):
self.make_heap(data)
def exchange(self, list_input, idx_1, idx_2):
list_input[idx_1], list_input[idx_2] = list_input[idx_2], list_input[idx_1]
return list_input, idx_2
def insert(self, data):
# 진짜 만약에 힙의 길이가 0이면?
if len(self.heap_array) == 0:
self.make_heap(data)
return True
# 자연스럽게 이진트리 구조로 만들어지기 때문에 추가해주면 됨.
self.heap_array.append(data)
# 인덱스값의 계산을 편하게 하기 위해서
# 계산 과정시에는 리스트 맨 앞에 None을 임의로 추가
self.heap_array.insert(0, None)
# None을 삽입했으므로, 실제 idx값을 구하려면 1을 뺄 것.
inserted_idx = len(self.heap_array) - 1
# swap 하는 과정
while 1:
if inserted_idx <= 1:
break
parent_idx = inserted_idx // 2
if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
self.heap_array, inserted_idx = self.exchange(self.heap_array, inserted_idx, parent_idx)
else:
break
# 계산이 끝났으니 맨 앞에 넣어두었던 None 삭제
del self.heap_array[0]
return True
그리고 테스트도 해보아야지.
# Test Code
My = heap(10)
My.insert(5)
print(My.heap_array)
My.insert(8)
print(My.heap_array)
My.insert(12)
print(My.heap_array)
My.insert(4)
print(My.heap_array)
My.insert(11)
print(My.heap_array)
My.insert(15)
print(My.heap_array)
# 출력 결과
[10, 5]
[10, 5, 8]
[12, 10, 8, 5]
[12, 10, 8, 5, 4]
[12, 10, 11, 5, 4, 8]
[15, 10, 12, 5, 4, 8, 11]
똑같은 조건으로 테스트해보았고, 역시 같은 결과가 출력되었다.
삭제코드도 수정해보자.
def pop(self):
if len(self.heap_array) < 1:
return None
# 계산 과정에서 인덱스 계산을 편하게 하기 위해서
# 계산 과정시에는 리스트 맨 앞에 None을 임의로 추가
self.heap_array.insert(0, None)
returned_data = self.heap_array[1]
# 맨 끝 데이터를 루트노드로 이동.
self.heap_array[1] = self.heap_array[-1]
del self.heap_array[-1]
popped_idx = 1
while 1:
left_child_popped_idx = popped_idx * 2
right_child_popped_idx = popped_idx * 2 + 1
if left_child_popped_idx >= len(self.heap_array): # list 끝에 다다랐기 때문에 루프 중단
break
elif 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
else:
break
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:
break
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
else:
break
del self.heap_array[0]
return returned_data
이 부분에서도 역시 move_down 함수를 삭제하고 대신에 while 1문 속의 조건문으로 산입하였다. 또한, 배열 속 아이템을 교환해주는 함수도 따로 빼주었다.
따라서 삭제 함수를 수정한 코드는 아래와 같다.
# 힙 데이터의 삭제(pop)
def pop(self):
if len(self.heap_array) < 1:
return None
# 계산 과정에서 인덱스 계산을 편하게 하기 위해서
# 계산 과정시에는 리스트 맨 앞에 None을 임의로 추가
self.heap_array.insert(0, None)
returned_data = self.heap_array[1]
# 맨 끝 데이터를 루트노드로 이동.
self.heap_array[1] = self.heap_array[-1]
del self.heap_array[-1]
popped_idx = 1
while 1:
left_child_popped_idx = popped_idx * 2
right_child_popped_idx = popped_idx * 2 + 1
if left_child_popped_idx >= len(self.heap_array): # list 끝에 다다랐기 때문에 루프 중단
break
elif 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.exchange(self.heap_array, popped_idx, left_child_popped_idx)
else:
break
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.exchange(self.heap_array, popped_idx, left_child_popped_idx)
else:
break
else:
if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
self.heap_array, popped_idx = self.exchange(self.heap_array, popped_idx, right_child_popped_idx)
else:
break
del self.heap_array[0]
return returned_data
코드 수정 전과 똑같은 조건으로 테스트를 해보았다.
# Test Code (삽입 과정 진행 직후)
# Test Case : [15, 10, 12, 5, 4, 8, 11]
My.pop()
print(My.heap_array)
My.pop()
print(My.heap_array)
My.pop()
print(My.heap_array)
My.pop()
print(My.heap_array)
My.pop()
print(My.heap_array)
# 출력 결과
[12, 10, 11, 5, 4, 8]
[11, 10, 8, 5, 4]
[10, 5, 8, 4]
[8, 5, 4]
[5, 4]
오케이. 코드 수정 전과 일치한다.
수정한 나의 Max Heap 코드
# Max Heap 구현
class heap:
def make_heap(self, data):
self.heap_array = list()
self.heap_array.append(data)
return
def __init__(self, data):
self.make_heap(data)
def exchange(self, list_input, idx_1, idx_2):
list_input[idx_1], list_input[idx_2] = list_input[idx_2], list_input[idx_1]
return list_input, idx_2
def insert(self, data):
# 진짜 만약에 힙의 길이가 0이면?
if len(self.heap_array) == 0:
self.make_heap(data)
return True
# 자연스럽게 이진트리 구조로 만들어지기 때문에 추가해주면 됨.
self.heap_array.append(data)
# 인덱스값의 계산을 편하게 하기 위해서
# 계산 과정시에는 리스트 맨 앞에 None을 임의로 추가
self.heap_array.insert(0, None)
# None을 삽입했으므로, 실제 idx값을 구하려면 1을 뺄 것.
inserted_idx = len(self.heap_array) - 1
# swap 하는 과정
while 1:
if inserted_idx <= 1:
break
parent_idx = inserted_idx // 2
if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
self.heap_array, inserted_idx = self.exchange(self.heap_array, inserted_idx, parent_idx)
else:
break
# 계산이 끝났으니 맨 앞에 넣어두었던 None 삭제
del self.heap_array[0]
return True
# 힙 데이터의 삭제(pop)
def pop(self):
if len(self.heap_array) < 1:
return None
# 계산 과정에서 인덱스 계산을 편하게 하기 위해서
# 계산 과정시에는 리스트 맨 앞에 None을 임의로 추가
self.heap_array.insert(0, None)
returned_data = self.heap_array[1]
# 맨 끝 데이터를 루트노드로 이동.
self.heap_array[1] = self.heap_array[-1]
del self.heap_array[-1]
popped_idx = 1
while 1:
left_child_popped_idx = popped_idx * 2
right_child_popped_idx = popped_idx * 2 + 1
if left_child_popped_idx >= len(self.heap_array): # list 끝에 다다랐기 때문에 루프 중단
break
elif 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.exchange(self.heap_array, popped_idx, left_child_popped_idx)
else:
break
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.exchange(self.heap_array, popped_idx, left_child_popped_idx)
else:
break
else:
if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
self.heap_array, popped_idx = self.exchange(self.heap_array, popped_idx, right_child_popped_idx)
else:
break
del self.heap_array[0]
return returned_data
이렇게 Max Heap을 파이썬에서 구현한 코드는 위와 같다.
다음에 Min Heap도 구현해야지. 위의 과정에서 일부 수정을 거치면 될 것이다.
3편에서 계속..
