[Python] Heap(힙)

■

 

Heap(힙)은 트리 기반의 자료구조이다. 그리고 부모가 항상 자식보다 작은 구조이다. 그렇기때문에 루트가 가장 작은 값을 갖게되며 가장 작은 값을 추출하는 것은 루트를 추출한다는 것이 된다.

여기서 주의해야할 점은 Heap(힙)은 정렬된 구조가 아니다. 즉, 왼쪽 자식과 오른쪽 자식의 관계를 정의하지 않았다. 오직 부모, 자식 간의 관계만 정의하였다.

Min Heap

위 그림을 보면 오른쪽 노드가 왼쪽 노드보다 작은 것 (33, 17)이 있듯이 왼쪽과 오른쪽의 관계는 정의하지 않았다.

그리고 위 그림을 보면 자식이 두 개로 구성되어 있는데 이것을 Binary Heap(이진 힙)이라하며 트리 중 이중 트리가 많이 사용되듯이 힙도 이진 힙이 가장 많이 사용된다.

 

위 그림처럼 배열로 표현할 경우 대개 계산의 편이를 위해 인덱스를 1부터 사용하는데 앞의 인덱스 0은 "None"과 같이 비워준다. 그리고 힙에서의 인덱스 순서는 위 그림과 같다.

 

■■

 

힙에 대한 설명은 여기까지하고 힙에서의 삽입과 추출의 구현을 알아보자. 당연히 힙 중에서도 이진 힙을 구현하는 것이다.

일단 힙의 기본적인 틀을 만들어보자. 무언가를 담는 것에 최적화된 그릇을 만든다고 생각하면 되겠다.

class Heap(object):
	def __init__(self): #초기화 값 설정
    	self.items = [None] #인덱스 0은 사용하지 않을 것이기 때문에 None을 미리 삽입해 놓는다
        
    def __len__(self): #마지막 요소의 인덱스 값을 가져오기 위해 생성
    	#물론 알겠지만 인덱스는 항상 0부터 시작하기 때문에 마지막 인덱스는 아래와 같이 전체 길이의 -1이다
        return len(self.items) - 1

 

■■■

 

이제 본격적으로 삽입(Insert)와 추출(extract)를 구현 할 것인데 삽입(Insert)를 먼저 해보겠다.

순서는 이렇다.

1. 삽입한 요소는 배열 상 맨 왼쪽에 위치한다.

2. 부모 값과 비교해 더 작으면 서로 위치를 변경한다.

3. 계속해서 2번 사항을 반복한다.

솔직히 굉장히 간단한 반복이다.

삽입 과정

def _heap_insert(self):
	#cur_node는 현재 삽입한 요소의 index 값이다
    #앞서 클래스를 정의할 때 만든 __len__ 을 사용하여 맨 마지막 인덱스를 불러온다
	cur_node = len(self)
    #신기하게도 삽입한 요소의 부모는 마지막 인덱스의 반에 위치한다
	parent = cur_node // 2
    #인덱스 1부터 시작하기때문에 1보다 작으면 None값에 도달한다
    while parent > 0:
    	#이제 삽입된 요소와 부모와 비교하며 반복한다
    	if self.itmes[cur_node] < self.itmes[parent]:
        	#삽입된 요소가 더 적으면 서로 바꾸면서 조건에 맞을때마다 반복한다
        	self.itmes[parent], self.items[cur_node] = self.items[cur_node], self.itmes[parent]
        #다음은 삽입된 요소가 바뀌었든 안바뀌었든 부모와 자리가 바뀌면서 다시 인덱스의 반에 위치한 부모를 정의해준다
        #처음 삽입된 요소가 더 크다면 예외처리 해줄 수도 있겠다
        cur_node = parent
        parent = cur_node // 2
       
def insert(self, n):
    self.itmes.append(n) #요소 n 추가
    self._heap_insert() #위치 재정의

 음... 아쉬운 부분이 없잖아 있지만 문제는 없으니...

암튼 삽입 구현은 위 코드와 같고 parent를 //2 로 반반씩 나누는 것으로 보아 시간복잡도는 O(logn)이라는 것을 알 수 있다.

 

■■■■

 

추출... 이것도 시간복잡도는 O(logn)이다.

예상하겠지만 삽입과 과정이 매우 비슷하며 추출은 맨 작은 값인 root를 빼오고 가장 큰 값, 가장 마지막 인덱스에 있는 값을 root에 가져오며 자식들과 계속 비교하며 추락한다.

 

추출 과정

def _heap_extract(self, i):
	#여기서 인덱스를 1부터 시작하는 것의 진가가 나오는데
    #left = 부모의 인덱스 * 2, right = 부모의 인덱스 * 2 + 1 로 각각 깔끔하게 나온다
    left = i * 2
    right = i * 2 + 1
    root = i
    
    #일단 left와 right는 맨 마지막 인덱스보다 작은 위치에 있어야 비교가 가능하다.
    #그 이유는 당연하게도 맨 마지막이랑 같게 되는 순간 더 이상 비교할 것이 없기 때문이다
    if left <= len(self) and self.items[left] < self.items[root]:
    	root = left #왼쪽 자식이 더 작으면 왼쪽 자식의 인덱스 저장
        
    if right <= len(self) and self.items[right] < self.items[root]:
    	root = right #오른쪽 자식이 더 작으면 오른쪽 자식의 인덱스 저장
        
    #root 값과 i 값이 같으면 비교가 진행이 안된 것이므로 더 이상 함수는 진행하지 못한다...
    if root != i:
    	#위에서 비교해서 더 작은 곳의 인덱스가 root에 저장되었으니 이제 추출된 인덱스 1부터 시작하여 서로 변경된다
		self.items[i], self.items[root] = self.items[root], self.items[i]
        #재귀(recursion)가 진행된다
        self._heap_extract(root)
 
 def extract(self):
    extract_val = self.items[1] #가장 작은 값 root의 인덱스 1을 지정하여 extract_val에 저장
    self.items[1] = self.items[len(self)] #마지막 인덱스에 있는 가장 큰 값을 root로 올려준다
    self.items.pop() #root로 올려줬으니 아래에 있는 값은 지워줘야지...
    self._heap_extract(1) #이제 root로 올려보낸 값의 인덱스가 1이 되었으니 1부터 시작하여 자식들과 비교한다
    return extract_val #추출한건 빼와야지...

이상 구현을 마치겠다.

아, 그리고 _heap_insert, _heap_extract의 맨 앞에 "_"는 class 내부에서만 사용할 수 있게 만들어준다. 즉, class의 내부 함수로 만들어준다.

 

■■■■■

 

마지막으로 짧게 이진 힙과 이진 탐색 트리(BST)를 비교하고 끝내겠다.

 

이진 힙	이진 탐색 트리(BST)
1. 상하 관계 즉, 부모와 자식 관계를 보장하며 부모가 자식보다 작다. 2. 가장 큰 값이나 가장 작은 값을 추출할 시 이진 힙을 사용하면 시간복잡도가 O(1)이므로 반드시 사용해야겠다는 것을 뼛속 깊이 새겨졌을 것이다	1. 좌우 관계 즉, 왼쪽 자식과 오른쪽 자식의 관계를 보장하며 부모는 왼쪽 자식보다 크고 오른쪽 자식보다는 작거나 같다 (왼쪽 자식<부모<=오른쪽 자식) 2. 모든 값이 정렬되어있을때 사용할 수 있으며 탐색과 삽입 모두 시간복잡도 O(logn)에 가능하다

많이 작성한거 같은데 별로 안되네...