Data Structure - Heap (힙) | Python 구현

Heap은 이진트리의 변형된 자료구조라고 할 수 있는데, 최댓값 최솟값을 빠르게 찾아야 할 때 많이 사용된다.

 

📌Heap

: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Complete Binary Tree) 

• 트리를 기반으로 변형된 구조!
• 완전 이진 트리(Complete Binary Tree): 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리
• 힙을 사용하는 이유
  • 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨.
  • array vs. heap
    : 배열에서 최댓값/최솟값을 탐색하는데 걸리는 시간복잡도는 $O(n)$, 힙에서 최댓값/최솟값을 찾는데 걸리는 시간복잡도는  $O(log n)$

📌Heap 구조

• 최대값을 구하기 위한 구조(최대 힙, Max Heap)와, 최솟값을 구하기 위한 구조(최소 힙, Min Heap)로 분류
• 힙은 다음 두가지 조건을 가진다.
  1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다(Max Heap) / 작거나 같다(Min Heap)
     → 즉, max heap에서는 가장 큰 값이, min heap에서는 가장 작은 값이 루트 노드(최상위 노드)에 위치하게 된다.
  2. 완전 이진 트리 형태(항상 왼쪽 부터 채워지는 방식 + 자식 노드는 최대 2개)

Heap Vs. BST(Binary Search Tree)

• 공통점: 힙과 이진탐색트리는 모두 이진트리이다.
• 차이점
  1. 힙은 Max Heap의 경우, 각 노드의 값이 자식 노드보다 크거나 같음
  2. 이진탐색트리는 왼쪽자식노드 < 부모모드 < 오른쪽 자식 노드
• 힙은 자식노드에서 크기에 따라 위치 결정되지 않음. (그냥 조건 없이 들어오는 순서대로 왼쪽부터 위치함)
• 이진 탐색트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조로 이해

 

📌Heap 동작 및 구현(python)

**max_heap 기준

0) 리스트 사용과 인덱스 설정

class MaxHeap:
    def __init__(self, value):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(value)

• 일반적으로 힙 구현시 배열(리스트)의 자료구조를 활용한다. (완전이진트리의 형태이기 때문에 가능 -> index만 알면 부모 노드, 자식 노드를 알수 있음)
• 힙 구현의 편의를 위해 root node의 index 번호는 1로 지정한다.
  • parent node's index = child node's index // 2
  • left child node's index = parent node's index * 2
  • right child node's index = (parent node's index * 2) + 1

1) 데이터 삽입

• 완전이진트리 형태이므로, 삽입할 노드는 무조건 왼쪽 최하단부 노드부터 삽입한다.
• 삽입된 데이터가 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꾸어주는 수행을 반복한다.

class MaxHeap:
    def __init__(self, value):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(value)

    def move_up(self, inserted_idx):
        if inserted_idx <= 1:
            return False
        parent_idx = inserted_idx // 2
        if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
            return True
        else:
            return False

    def insert(self, value):
        if len(self.heap_array) < 1:
            self.heap_array.append(None)
            self.heap_array.append(value)
            return True

        self.heap_array.append(value)
        inserted_idx = len(self.heap_array) - 1
        while self.move_up(inserted_idx):
            parent_idx = inserted_idx // 2
            self.heap_array[parent_idx], self.heap_array[inserted_idx] = \
                self.heap_array[inserted_idx], self.heap_array[parent_idx]
            inserted_idx = parent_idx
        return True

• heap class: root node의 index는 1번부터 시작하도록 초기화
• move_up(self, inserted_idx): 삽입 후, 삽입된 값(heap_array[inserted_idx])이 parent node보다 커서 swap을 수행해야 하는 경우, TRUE 반환 (즉, max heap 조건이 성립되는지를 판단하는 역할)

• insert(self, value): 
  
  • 완전이진트리이므로 바로 list 맨 끝에 추가(append) - 왼쪽 최하단부터 삽입하는 규칙
  • 위치를 바꿔야 하면(=삽입된 값이 parent node보다 크면, =move_up()함수가 true를 반환하면), swap 진행

 

2) 데이터 삭제

• root node 삭제 후, 가장 최하단부 왼쪽에 위치한 노드(가장 마지막에 추가한 노드)를 root node의 빈자리로 올려준다.
• 이후, 올려준 노드의 값이 자식 노드보다 작을 경우, swap을 반복하여 완전이진트리의 규칙에 벗어나지 않도록 만들어준다.

class MaxHeap:
    def __init__(self, value):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(value)

    def move_up(self, inserted_idx):
		...

    def insert(self, value):
		...

    def move_down(self, idx):
        if len(self.heap_array) > idx * 2:
            if len(self.heap_array) > idx * 2 + 1:
                if self.heap_array[idx] < max(self.heap_array[idx * 2], self.heap_array[idx * 2 + 1]):
                    return True
                else:
                    return False
            else:
                if self.heap_array[idx] < self.heap_array[idx * 2]:
                    return True
                else:
                    return False
        else:
            return False

    def pop(self):
        if len(self.heap_array) <= 1:
            print(0)
            return True
        returned_data = self.heap_array[1]
        self.heap_array[1] = self.heap_array[-1]
        self.heap_array.pop()
        idx = 1
        while self.move_down(idx):
            if len(self.heap_array) > idx * 2 + 1:
                if self.heap_array[idx * 2] >= self.heap_array[idx * 2 + 1]:
                    self.heap_array[idx], self.heap_array[idx * 2] = \
                        self.heap_array[idx * 2], self.heap_array[idx]
                    idx = idx * 2
                else:
                    self.heap_array[idx], self.heap_array[idx * 2 + 1] = \
                        self.heap_array[idx * 2 + 1], self.heap_array[idx]
                    idx = idx * 2 + 1
            else:
                self.heap_array[idx], self.heap_array[idx * 2] = \
                    self.heap_array[idx * 2], self.heap_array[idx]
                idx = idx * 2
        print(returned_data)
        return True

• move_down(self, check_idx):  대소비교해서 swap해야(내려줘야) 할 때만 true 반환
  • case 1: 자식이 아예 없음 (swap 진행 필요 X)
  • case 2: 왼쪽 자식만 있음
  • case 3: 오른쪽 자식만 있음
• pop(self): 위치를 바꿔야 하면(=올라간 값이 child node보다 작면, =move_down()함수가 TRUE를 반환하면), swap 진행
  : move_down()에서 TRUE가 반환되어 pop()함수가 수행되는 거지만 어떤 case로 true가 반환되었는지는 pop()함수에서 다시 판단해주어야함!

 

📌Heap 시간 복잡도

• 트리의 depth가 h라면, n개의 node를 가지는 tree에서 h는 $log(n)$에 가까우므로, 시간 복잡도는 $O(log n)$
  : 즉, 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉, 50%의 실행시간을 단축시킬 수 있다는 것을 의미