[파이썬][자료구조] 힙 (Heap)

힙

• 힙은 데이터에서 최댓값과 최솟값을 빠르게 찾기 위한 완전 이진트리 (Complete Binary Tree)이다.

힙을 사용하는 이유

• 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 알고리즘 구현에 사용된다.
• 이진트리의 경우 한번 연산이 진행되면 데이터가 1/2가 되므로 시간 복잡도가 O($log {n}$)이 걸린다.
  • 따라서 힙도 O($log {n}$)이 걸린다 (배열의 경우 최악의 경우에 O(n)이 걸림).

 

힙의 구조

• 최댓값을 구하는 최대 힙 (Max Heap)과 최솟값을 구하는 최소 힙 (Min Heap)으로 구분된다.
  • 최대 힙 : 각 노드의 값은 자식 노드의 값보다 크거나 같다 (가장 위가 가장 큰 값).
  • 최소 힙 : 각 노드의 값은 자식 노드의 값보다 작거나 같다 (가장 위가 가장 작은 값).
    • 데이터는 맨 위에 있는 Root Node를 가져온다. 이 때문에 시간이 적게 걸린다.
• 완전 이진트리의 형태를 갖는다.
  • 데이터를 항상 왼쪽 노드부터 채워 나가는 구조

 

01234

힙과 이진 탐색 트리의 차이점

• 힙은 각 노드의 값이 자식 노드보다 크거나 같다 (또는 작거나 같다).
• 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 오른쪽 자식 노드의 값이 가장 크다.
  • 힙에서는 왼쪽 자식 노드와 오른쪽 자식 노드에 들어가는 데이터에 대해 이진 탐색 트리와 같은 조건이 따로 없다.
• 이진 탐색 트리는 전체 탐색을 빠르게 하기 위한 구조이며 힙은 최소/최댓값을 빠르게 구하기 위한 구조이다.

 

데이터 삽입

최대 힙에서 삽입 데이터가 힙의 데이터보다 클 경우

1. 가장 아래 왼쪽부터 채운다.
2. 현재 위치에서 부모 노드와 비교하여 위치를 바꿔준다.

012

 

• 부모 노드가 더 크거나 Root 노드까지 갈 때까지 위치를 바꿔준다.
• 최소 힙의 경우 최대 힙과 반대로 해주면 된다.

 

데이터 삭제하기

최대 힙

• 보통 삭제는 root 노드를 삭제하는 것이 일반적이다.

1. 가장 마지막에 추가한 노드를 root 노드로 이동시킨다.
2. root 노드의 자식 노드와 비교하여 작을 경우 자식 노드 중 큰 값과 위치를 바꾼다.

 

012

 

힙 구현

• 힙은 배열을 활용하여 구현한다.
• root 노드의 인덱스를 1로 지정하여 구현한다.
  • 부모 노드 인덱스 = 자식 노드 인덱스 // 2
  • 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2
  • 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1

# 힙 클래스 구현
class Heap:
    def __init__(self, num):
        self.heap_list = list()
        self.heap_list.append(None) # root node의 인덱스를 1로 하기 위함
        self.heap_list.append(num)

heap = Heap(20)
heap.heap_list

[None, 20]

데이터 추가 기능 추가

# 힙 클래스 구현
class Heap:
    def __init__(self, num):
        self.heap_list = list()
        self.heap_list.append(None) # root node의 인덱스를 1로 하기 위함
        self.heap_list.append(num)

    def switch(self, num_index):
        if num_index == 1:
            return False # root node 일때

        parent_index = num_index // 2
        if self.heap_list[num_index] > self.heap_list[parent_index]:
            return True

        return False

    # 데이터 삽입
    def insert(self, num):
        if len(self.heap_list) == 0:
            self.heap_array.append(None)
            self.heap_list.append(num)
            return True
        self.heap_list.append(num)

        #추가한 num이 부모 노드보다 크면 자리바꾸기 위한 코드
        num_index = len(self.heap_list) - 1

        while self.switch(num_index):
            parent_index = num_index // 2
            self.heap_list[num_index], self.heap_list[parent_index]\
            = self.heap_list[parent_index], self.heap_list[num_index]
            num_index = parent_index
        return True

heap = Heap(20)
heap.insert(15)
heap.insert(10)
heap.insert(7)
heap.insert(5)
heap.insert(25)
heap.heap_list

[None, 25, 15, 20, 7, 5, 10]

데이터 삭제 기능 추가

# 힙 클래스 구현
class Heap:
    def __init__(self, num):
        self.heap_list = list()
        self.heap_list.append(None) # root node의 인덱스를 1로 하기 위함
        self.heap_list.append(num)

    def switch(self, num_index):
        if num_index == 1:
            return False # root node 일때

        parent_index = num_index // 2
        if self.heap_list[num_index] > self.heap_list[parent_index]:
            return True

        return False

    def switch_child(self, switch_index): # 자식 노드와 비교하여 작으면 자리 바꾸기 위함
        left_child_index = switch_index * 2
        right_child_index = switch_index * 2 + 1

        # 왼쪽 차일드 노드가 없을 때
        if left_child_index >= len(self.heap_list):
            return False

        # 왼쪽 차일드 노드만 있을 때
        elif right_child_index >= len(self.heap_list):
            if self.heap_list[switch_index] < self.heap_list[left_child_index]:
                return True
            else:
                return False

        #왼쪽 오른쪽 모두 있을 때
        else:
            if self.heap_list[left_child_index] > self.heap_list[right_child_index]:
                if self.heap_list[switch_index] < self.heap_list[left_child_index]:
                    return True
                else:
                    return False
            else:
                if self.heap_list[switch_index] < self.heap_list[right_child_index]:
                    return True
                else:
                    return False

    # 데이터 삽입
    def insert(self, num):
        if len(self.heap_list) == 0:
            self.heap_array.append(None)
            self.heap_list.append(num)
            return True
        self.heap_list.append(num)

        #추가한 num이 부모 노드보다 크면 자리바꾸기 위한 코드
        num_index = len(self.heap_list) - 1

        while self.switch(num_index):
            parent_index = num_index // 2
            self.heap_list[num_index], self.heap_list[parent_index]\
            = self.heap_list[parent_index], self.heap_list[num_index]
            num_index = parent_index
        return True

    # 데이터 삭제
    def delete(self):
        if len(self.heap_list) <= 1:
            return None

        pop_num = self.heap_list[1] # root node 출력
        self.heap_list[1] = self.heap_list[-1] # root node에 가장 마지막 데이터 바꿔 줌
        del self.heap_list[-1]
        switch_index = 1

        while self.switch_child(switch_index):
            left_child_index = switch_index * 2
            right_child_index = switch_index * 2 + 1

            # 왼쪽 차일드 노드만 있을 때
            if right_child_index >= len(self.heap_list):
                if self.heap_list[switch_index] < self.heap_list[left_child_index]:
                    self.heap_list[switch_index], self.heap_list[left_child_index]\
                    = self.heap_list[left_child_index], self.heap_list[switch_index]
                    switch_index = left_child_index

            #왼쪽 오른쪽 모두 있을 때
            else:
                if self.heap_list[left_child_index] > self.heap_list[right_child_index]:
                    if self.heap_list[switch_index] < self.heap_list[left_child_index]:
                        self.heap_list[switch_index], self.heap_list[left_child_index]\
                        = self.heap_list[left_child_index], self.heap_list[switch_index]
                        switch_index = left_child_index
                else:
                    if self.heap_list[switch_index] < self.heap_list[right_child_index]:
                        self.heap_list[switch_index], self.heap_list[right_child_index]\
                        = self.heap_list[right_child_index], self.heap_list[switch_index]
                        switch_index = right_child_index

        return pop_num

heap = Heap(20)
heap.insert(15)
heap.insert(10)
heap.insert(7)
heap.insert(5)
heap.heap_list

[None, 20, 15, 10, 7, 5]

heap = Heap(20)
heap.insert(15)
heap.insert(10)
heap.insert(7)
heap.insert(5)
heap.insert(25)
heap.heap_list

[None, 25, 15, 20, 7, 5, 10]

heap.delete()

25

heap.heap_list

[None, 20, 15, 10, 7, 5]

힙의 시간 복잡도

• n개의 노드를 가진 힙에 데이터를 입력 또는 삭제 시 최악의 경우 트리의 높이만큼 비교해야 한다.
  • $h = log_2 {n}$이므로 시간 복잡도는 $O(log {n})$이다