내가 읽고 있는 책은 왼쪽 노드와 오른쪽 노드의 인덱스를 구하는데 비트연산자를 이용했지만, 개인적으로 이런 방식이 처음 힙을 접하는 사람에게 효과적인 접근방식이 아니라 생각이 들어, 다른 방식으로 인덱스를 구했다.
먼저 힙은 기본적으로 최대값이나 최소값을 빠르게 구하기 위해 고안된 자료 구조이다. root 노드에 항상 최대값이나 최소값이 위치하도록 설계되어있고, heapify하는데, 절반의 노드만 처리해도 최대값과 최소값을 반드시 최상단 노드에 위치하게 할 수 있기 때문에 O(logN)의 시간복잡도를 갖는다.
먼저 heapify 되지 않은 리스트 [3,2,5,1,7,8,2] 라는 리스트가 있다고 해보자.
class MaxHeap(object):
def __init__(self):
self.queue = [3, 2, 5, 1, 7, 8, 2]
for i in range(len(self.queue)//2, -1, -1):
self.__max_heapify__(i)
# 힙의 절반부터 heapify를 실행한다. => 미리 설명했듯이, 모든 원소를
순회할 필요없이 절반의 원소만 처리해도 최대값이 root노드로 온다.
def __max_heapify__(self, i):
#실제 힙을 구현한 부분
left_index = self.leftchild(i) # 현재 노드의 왼쪽 노드 값
right_index = self.rightchild(i) # 현재 노드의 오른쪽 노드 값
current_point_index = i
if left_index <= len(self.queue) - 1 and self.queue[current_point_index] < self.queue[left_index]:
# 1. left_index가 전체 길이보다 작은 경우에만, 크면 존재하지 않는 자식 노드에 접근 한 것
# 2. current_point_index의 값과 left_index의 값을 비교 해서 부모 노드가 더 작은 경우
current_point_index = left_index
# 3. 왼쪽으로 포인터를 옮겨줌
if right_index <= len(self.queue) - 1 and self.queue[current_point_index] < self.queue[right_index]:
# 1. 만약 오른쪽이랑 비교했는데 오른쪽 노드가 더 크다면 오른쪽 노드를 올려주고
# 2. 그게 아니면 자동으로 왼쪽 노드가 올라감
current_point_index = right_index
# 즉 더 큰 값이 올라가게 되어있음.
if current_point_index != i:
# 변화가 있었다면, 즉 왼쪽이나 오른쪽 노드와 변화가 있으면
self.swap(i, current_point_index) # 더 큰 노드와 현재 부모 노드를 바꿔줌
self.__max_heapify__(current_point_index) # 재귀적으로 heapify
def swap(self, i, parent_index):
self.queue[i], self.queue[parent_index] = self.queue[parent_index], self.queue[i]
def parent(self, index):
return (index - 1) // 2
def leftchild(self, index):
return index * 2 + 1
def rightchild(self, index):
return index * 2 + 2
def printHeap(self):
print(self.queue)
if __name__ == "__main__":
maxHeap = MaxHeap()
maxHeap.printHeap()
#결과는 최대값이 가장 앞에 오게 된다.이렇게 힙을 구현을 했고, 그림으로 보면 더 이해가 쉽다.
추가적으로 구현해야 할 부분은, 노드의 insert와 delete가 있을 때마다 heapify를 계속 해주어야 하므로 insert와 delete의 부분을 추가로 구현해야 한다.
def insert(self, n):
self.queue.append(n)
for i in range(len(self.queue)//2, -1, -1):
self.__max_heapify__(i)
def delete(self):
max_element = self.queue[0]
n = len(self.queue)
self.queue[0] = self.queue[n-1]
self.queue = self.queue[:(n-1)]
self.__max_heapify__(0)
return max_element해당 코드를 추가하면된다.
insert의 경우 heap 리스트의 가장 마지막 부분에 추가가 되게 되고, 그렇다면 heapify를 모두 처음부터 다시 해주어야 한다. 때문에 for 문을 돌려서 heap을 다시 구성해주었다.
delete의 경우 heap의 가장 최상단 노드의 값을 delete하는 게 국룰이므로 (heap sort를 위해) 리스트의 가장 뒷 노드를 루트 노드와 스왑해주고, 그 루트노드만 heapify해주면 된다.
삭제하는 값을 리턴해주고 말고는 구현하는 사람의 자유지만 heap sort를 위해서는 반드시 리턴해주어야 하므로 return 을 넣어주자.
