[자료구조] 힙(Heap)이란?

힙(Heap)이란?

힙(Heap)은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 자료구조로, 완전 이진 트리(Complete binary tree)의 형태를 가진다.

이러한 힙은 힙 속성을 만족하는데, 힙 속성이란,

 

• 최대 힙 속성(max heap property) : 부모 노드의 키 값은 항상 자식 노드의 키 값보다 크거나 같다.
• 최소 힙 속성(min heap property) : 부모 노드의 키 값은 항상 자식 노드의 키 값보다 작거나 같다.

다음과 같으며, 어떤 힙 속성을 만족하는지에 따라 최대 힙(Max heap)과 최소 힙(Min heap)으로 나뉜다.

 

힙(Heap)의 특징

힙의 특징은 다음과 같다.

 

• 루트 노드(root node)는 항상 최댓값 또는 최솟값을 가진다 (만족하는 힙 속성에 따라)
• 부모-자식 사이의 크기 관계만 존재하며, 왼쪽 자식-오른쪽 자식 간의 크기 관계는 존재하지 않는다
• 완전 이진 트리이기 때문에 트리의 높이를 $h$라고 하면 $h = |{\log_2}n|$ 이다.
• 이러한 힙은 힙 정렬, 우선순위 큐, 다익스트라 알고리즘 등에 응용된다.

 

힙(Heap)의 시간 복잡도

힙에서 최댓값(혹은 최솟값)을 참조함은 $O(1)$ 의 시간 복잡도를 가지며

원소를 삽입하거나 삭제 시 $O({\log} N)$의 시간 복잡도를 가진다.

 

 

힙(Heap)과 이진 탐색 트리

힙과 이진 탐색 트리는 모두 이진 트리라는 공통점을 가지고 있기에, 겉으로 보기에는 별다른 차이점이 보이지 않는다.

그러나, 이 둘은 큰 차이점들을 가지고 있다. 차이점은 다음과 같다.

	힙	이진 탐색 트리
트리 형태	완전 이진 트리	이진 트리
원소의 중복 여부	중복 가능	중복 불가능
원소의 정렬 여부	정렬 X	정렬 O
원소 탐색 시간 복잡도	$O(n)$(순차 탐색)	$O({\log} N)$(이진 탐색)
원소의 삽입 및 삭제 시간 복잡도	$O({\log} N)$	$O({\log} N)$ / $O(n)$ (skewed tree)
최댓값/최솟값 참조 시간 복잡도	$O(1)$	$O({\log} N)$ / $O(n)$ (skewed tree)

 

 

힙(Heap)의 동작

지금부터는 힙의 데이터 삽입, 삭제를 다음 예시와 함께 살펴보도록 하겠다. 지금부터 다루는 모든 내용은 최대 힙을 기준으로 한다.

 

 

 

힙(Heap)의 삽입

우선, 힙은 완전 이진 트리이다. 따라서 노드가 삽입될 때마다 왼쪽 최하단부터 채워진다.

위의 예시에서 "2"를 삽입하면 다음과 같이 힙은 다음과 같이 변경된다.

마찬가지로, 여기에 1을 추가하면 다음과 같다.

그런데, 지금까지는 삽입되는 값들이 힙의 최솟값이어서 별 문제가 발생하지 않았지만, 만약 힙에 삽입되는 값이 해당 노드의 부모 노드보다 커버리면 최대 힙 속성을 만족하지 못하는 문제가 발생한다. 이러한 문제는 어떻게 해결할까?

힙에 데이터를 삽입할 때마다 부모 노드와 비교하여, 부모 노드보다 크면 자리를 맞바꾸는 과정을 반복함으로써 해결할 수 있다.

다음의 예시를 보자

위와 같은 힙에 20을 삽입해보자

왼쪽 최하단부터 삽입을 진행했다. 그런데, 20의 부모 노드인 7은 20보다 작다. 따라서 위치를 변경해준다.

다음과 같은 결과가 도출된다. 이번에도 부모 노드와 비교를 해서, 부모 노드의 값이 작으면 서로의 위치를 변경한다.

예시에서도 부모 노드의 값인 10이 20보다 작으니, 위치를 바꿔주고, 그 다음의 부모 노드 값인 15도 20보다 작기 때문에 위치를 변경해준다. 이러한 과정을 거치면 최종적으로는 다음과 같은 힙이 완성된다.

 

힙(Heap)의 삭제

우선, 우리는 힙을 통해 최댓값(혹은 최솟값)을 얻고 싶어한다. 따라서 보통은 최상단의 root node의 값을 참조하고, 삭제하게 된다.

이렇게 데이터를 삭제하고 나면, 다음과 같이 변경된다.

root node가 존재하지 않는 상태이기 때문에, 이 부분을 채워줘야만 한다. 이 부분을 어떻게 채워줘야 할까?

힙의 삭제도 삽입과 원리가 비슷하다. 우선, 최하단부 가장 왼쪽의 노드를 root node로 올려준다.

그 다음, root node의 값이 자식 노드보다 작을 경우, 자식 노드들 중 가장 큰 값과 위치를 바꿔준다. 위 예시에서는 15와 바꿔주겠다.

 

여기서 다시 한번 자식 노드들과 값을 비교해서, 자식 노드보다 작은 값을 가지면 자식 노드 중 가장 큰 값과 위치를 바꿔준다.

최종적으로는 다음과 같은 형태의 힙이 완성된다.

 

 

 

힙(Heap)의 구현

힙은 완전 이진 트리이기에, 배열로 쉽게 구현할 수 있다.

구현할 때 편의를 위해 root node의 index는 1로 지정한다. 이를 위해, index 0에는 none값을 넣어주었다.

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        # 리스트 인덱스 1부터 시작하도록
        self.heap_array.append(None)
        self.heap_array.append(data)
        
    def move_up(self, inserted_idx):
        # 삽입된 값의 인덱스가 1보다 작으면(root node이면), 혹은 비어있으면, 바꿀 필요가 없음
        if inserted_idx <= 1:
            return False
        
        # 삽입된 값의 parent node의 index
        parent_idx = inserted_idx // 2
        # 삽입된 값이 parent node보다 크면
        if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
            # True 반환
            return True
        # 삽입된 값이 parent node보다 작거나 같으면
        else:
            # False 반환
            return False
        
    def insert(self, data):
        # 힙이 비어있으면
        if len(self.heap_array) == 0:
            # root node index 1로 설정하기 위해 None 먼저 삽입
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True
        

        self.heap_array.append(data)
        
        inserted_idx = len(self.heap_array) - 1
        
        # 바꿀지 말지 결정해서 True인 경우
        while self.move_up(inserted_idx):
            # 삽입된 값의 parent node의 index
            parent_idx = inserted_idx // 2
            # 삽입된 값과 삽입된 값의 parent node를 바꿔줌
            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):
        # pop된 이후 맨 밑에서 root node로 이동한 node의 child index 구하기
        left_child_popped_idx = popped_idx * 2
        right_child_popped_idx = popped_idx * 2 + 1
        
        # case1: 왼쪽 자식 노드도 없을 때
        if left_child_popped_idx >= len(self.heap_array):
            return False
        # case2: 오른쪽 자식 노드만 없을 때
        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
        # case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
        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

            # case2: 오른쪽 자식 노드만 없을 때
            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
            # case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
            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