힙 (Heap)

개요

• 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전이진트리
  • 완전이진트리(Complete Binary Tree): 노드를 삽입할 때 최하단 왼쪽 노드부터 삽입하는 트리.

사용하는 이유

• 최대값, 최소값을 빠르게 찾기 위함이다.
• 데이터를 마구마구 넣다가 중간에 그 순간의 최대값, 최소값을 빠르게 찾기 좋다.

힙의 구조

• 힙은 두 가지로 분류할 수 있다. 최대값을 찾기 위한 최대 힙(Max Heap)과 최소값을 찾기 위한 최소 힙(Min Heap)
• 힙은 두 가지 조건을 가긴 자료구조이다.
  • 최대 힙의 경우, 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다.
  • 최소 힙의 경우 각 노드의 값은 자식 노드가 가진 값보다 작거나 같다.
• 완전 이진 트리 형태를 가진다.

힙 vs 이진탐색트리

• 공통점
  • 둘 다 이진트리다. 자식 노드가 최대 2개인 트리.
• 차이점
  • 최대 힙의 경우, 힙은 각 노드의 값이 자식 노드의 값보다 크거나 같지만, 이진탐색트리에서는 왼쪽자식 < 부모 < 오른쪽자식 순으로 커진다.
  • 이진탐색트리에서는 한 노드의 왼쪽 자식이 오른쪽 자식보다 작지만 힙에서는 알 수 없다. 그러한 조건이 없음.

힙은 최소값/최대값을 찾기 위한 자료구조, 이진탐색트리는 탐색을 위한 자료구조!!

힙에 데이터 삽입하기

1. 완전이진트리 구조에 따라 데이터를 삽입한다.
2. 삽입한 노드와 부모 노드의 값을 비교한다.
3. 최대 힙의 경우. 부모 노드의 값이 더 작으면 삽입한 노드(자식 노드)와 부모 노드의 자리를 바꾼다.
4. 2번으로 돌아가 반복하며, 삽입한 노드가 루트노드이거나, 부모 노드보다 작으면 삽입이 완료된다. 

힙에서 데이터 삭제하기

(최대 힙의 경우) 보통 힙에서 데이터 삭제는 최대값 삭제인 경우가 일반적이다. 또한 삭제라기 보다는 최대값 혹은 최소값 pop이 일반적이다.

1. 최대값(루트 노드)을 뽑아내 삭제한다.
2. 가장 마지막에 존재하는 노드를 루트 노드로 올린다.
3. 루트 노드가 된 노드, 그 노드의 자식 노드들 (총 3개의 노드)를 비교하여 최대값을 루트 노드로 만든다.
4. 힙의 조건에 부합하거나(부모 노드는 자식노드보다 크거나 같다) 자식 노드가 없을 때 까지 3번 과정 반복

힙의 구현

• 힙은 완전이진트리의 구조를 갖기 때문에 배열로 구현이 가능하다. (인덱스를 붙이는 것이 가능하기 때문)
• 이번 구현에서는 편의를 위해 0번 인덱스에는 데이터를 비우고, 1번 인덱스를 루트 node로 둠.
  • 부모 노드의 인덱스 번호: 자식 노드의 인덱스 // 2
  • 왼쪽 자식의 인덱스 번호: 부모 노드의 인덱스 * 2
  • 오른쪽 자식의 인덱스 번호: 부모 노드의 인덱스 * 2 + 1

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)

    def have_to_move_up(self, insert_idx):
        # root node라면 바꿀 필요 없으므로 False 리턴
        if insert_idx <= 1:
            return False
        
        # parent node 인덱스를 구하고 child node와 값을 비교해서 child node가 더 크면 True 리턴
        parent_idx = insert_idx // 2
        if self.heap_array[insert_idx] > self.heap_array[parent_idx]:
            return True
        else:
            False

    def insert(self, data):
        # 데이터 추가
        self.heap_array.append(data)

        # 삽입한 노드의 인덱스 구하기
        inserted_idx = len(self.heap_array) -1

        # 인덱스를 통해 부모 노드와 값을 비교하고 자리를 바꾸어야 한다면
        while self.have_to_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

    def have_to_move_down(self, poped_idx):
        left_child_idx = poped_idx * 2
        right_child_idx = poped_idx * 2 + 1

        # child node가 없는 경우
        if left_child_idx >= len(self.heap_array):
            return False
        # 왼쪽 child node만 있는 경우
        elif right_child_idx >= len(self.heap_array):
            if self.heap_array[poped_idx] < self.heap_array[left_child_idx]:
                return True
            else:
                return False
        # 왼쪽, 오른쪽 child node가 모두 있는 경우
        else:
            # 자식 노드끼리 비교했는데 왼쪽이 클 경우
            if self.heap_array[left_child_idx] > self.heap_array[right_child_idx]:
                # 왼쪽 노드가 부모 노드보다 클 경우
                if self.heap_array[poped_idx] < self.heap_array[left_child_idx]:
                    return True
                else:
                    return False
            # 자식 노드끼리 비교했는데 오른쪽이 클 경우
            else:
                # 오른쪽 노드가 부모 노드보다 클 경우
                if self.heap_array[poped_idx] < self.heap_array[right_child_idx]:
                    return True
                else:
                    return False



    def pop(self):
        if len(self.heap_array) <= 1:
            return None
        
        returned_data = self.heap_array[1]
        # 힙의 마지막 데이터를 root node로 만든다.
        self.heap_array[1] = self.heap_array[-1]
        del self.heap_array[-1]
        poped_idx = 1

        # child node와 자리를 바꾸어야 하는지 확인하고,
        while self.have_to_move_down(poped_idx):
            left_child_idx = poped_idx * 2
            right_child_idx = poped_idx * 2 + 1

            # 왼쪽 child node만 있는 경우
            if right_child_idx >= len(self.heap_array):
                if self.heap_array[poped_idx] < self.heap_array[left_child_idx]:
                    self.heap_array[poped_idx], self.heap_array[left_child_idx] = \
                        self.heap_array[left_child_idx], self.heap_array[poped_idx]
            # 왼쪽, 오른쪽 child node가 모두 있는 경우
            else:
                # 자식 노드끼리 비교했는데 왼쪽이 클 경우
                if self.heap_array[left_child_idx] > self.heap_array[right_child_idx]:
                    # 왼쪽 노드가 부모 노드보다 클 경우
                    if self.heap_array[poped_idx] < self.heap_array[left_child_idx]:
                        self.heap_array[poped_idx], self.heap_array[left_child_idx] = \
                        self.heap_array[left_child_idx], self.heap_array[poped_idx]
                # 자식 노드끼리 비교했는데 오른쪽이 클 경우
                else:
                    # 오른쪽 노드가 부모 노드보다 클 경우
                    if self.heap_array[poped_idx] < self.heap_array[right_child_idx]:
                        self.heap_array[poped_idx], self.heap_array[right_child_idx] = \
                        self.heap_array[right_child_idx], self.heap_array[poped_idx]
        return returned_data
        


if __name__ == "__main__":
    h = Heap(15)
    h.insert(10)
    h.insert(8)
    h.insert(5)
    h.insert(4)
    h.insert(20)
    print(h.heap_array)
    h.pop()
    print(h.heap_array)