Heap

1. Heap이란?

• 데이터에서 min/max값을 빠르게 찾기 위해 고안된 완전이진트리
• 노드를 삽입할 때 최하단 왼쪽 노드부터 차례로 삽입(완전이진트리 특징)
• min/max값 찾는데 O(logn)
• 우선순위 큐와 같이 min/max를 빠르게 찾아야하는 자료구조 및 알고리즘 구현에 등에 활용됨

2. Max Heap 구조

• 각 노드의 값은 해당 노드의 자식노드가 가진 값보다 크거나 같다!
• 완전이진트리 형태

3. 힙 vs 이진 탐색트리

• 둘다 이진트리
• 이진 탐색트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조
• 힙은 이진 탐색트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰값은 오른쪽이라는 조건은 없음

4. 힙 동작

4-1. 힙에 데이터 삽입하기

4-2. 힙의 데이터 삭제하기

5. 힙 구현

(1) 힙에 데이터 삽입 구현
(2) 힙에 데이터 삭제 구현

# max heap 구현하기
class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None) # 인덱스 번호를 1부터하기 위해서!
        self.heap_array.append(data)

    def should_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 pop(self):
        if len(self.heap_array) <= 1:
            return None
        returned_data = self.heap_array[1]

        # 맨 마지막 자식을 꼭대기로(여기서는 1번 인덱스부터 채워가기로 했으니! 트리의 꼭데기는 1번!)
        self.heap_array[1] = self.heap_array[-1]
        del self.heap_array[-1]
        popped_idx = 1

        ## popped_idx라는 표현이 맘에 안듦
        while self.should_move_down(popped_idx):
            left_child_popped_idx = popped_idx * 2
            right_child_popped_idx = popped_idx * 2 + 1
            if right_child_popped_idx >= len(self.heap_array):
                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[left_child_popped_idx] > self.heap_array[right_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:
                    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

    def insert(self, data):
        # self.heap_array의 0번 인덱스는 비워두고, 데이터는 1번 인덱스부터 채워넣기로해서!
        if len(self.heap_array) == 1:
            self.heap_array.append(data)
            return True

        self.heap_array.append(data)
        inserted_idx = len(self.heap_array) - 1

        # 삽입된 위치에서부터 부모노드로 max heap 형태인지 체크하고
        # 아닐 경우, max_heap 형태로 바꿔줌!
        while self.should_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

    # 이 함수의 정체는 무엇인가....
    # popped_idx라는 표현이 맘에 안듦
    def should_move_down(self, popped_idx):
        left_child_popped_idx = popped_idx * 2
        right_child_popped_idx = popped_idx * 2 + 1
        if left_child_popped_idx >= len(self.heap_array):
            return False
        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
        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:
                    if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                        return True
                    else:
                        return False



heap = Heap(15)
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
heap.insert(20)
print(heap.heap_array)
print(heap.pop())
print(heap.heap_array)

6. 힙 시간 복잡도

• 트리의 높이(depth)
• 데이터 삽입/삭제 O(logn)

Reference

• https://www.fun-coding.org/Chapter11-heap.html