Heap (힙) 정리

👨🏼‍💻 Heap (힙) 정리 With Python

🥝 Heap 이란?

데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리(Complete Binary Tree)입니다.

 

완전 이진트리?

• Node를 삽입할 때 최하단 왼쪽 Node부터 차례대로 삽입하는 Tree

 

배열에 데이터를 넣고, 최댓값과 최솟값을 찾으려면 O(n) 이 걸리지만

힙에 데이터를 넣고, 최댓값과 최솟값을 찾으면 O(logn) 이 걸리기 때문에

최댓값, 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘에 활용됩니다.

 

힙은 아래의 두 가지 조건을 가지고 있어야 합니다.

1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같습니다. 
2. 완전 이진트리 형태를 가집니다.

 

🍋 Heap VS Binary Search Tree

공통점

• 힙과 이진 탐색 트리는 모두 이진트리입니다.

차이점

• 힙은 각 노드의 값이 자식 노드보다 크거나 같습니다.
• 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그다음 부모 노드, 그다음 오른쪽 자식 노드 값이 가장 큽니다.
• 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건이 없습니다.
• 힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있습니다.
• 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최솟값 검색을 위한 구조입니다.

 

🍊 Heap에 데이터 넣기

Heap은 완전 이진트리이기 때문에 삽입할 Node는 왼쪽 최하단 Node부터 채워집니다.

 

 

채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복하게 됩니다.

 

🍉 Heap의 데이터 삭제하기

Heap에서 데이터를 꺼낼 경우 최상단 Node를 꺼내는 것이 일반적입니다.

(Heap의 목적인 최솟값, 최댓값을 알아내기 위해서...)

 

최상단 Node를 삭제 시,

맨 마지막에 입력된 Node가 최상단 Node로 이동하여 올바른 위치를 찾을 때까지 

Node의 위치를 바꿔주게 됩니다.

 

🍈 Heap 구현 With Python

 

힙 구현 시 배열 자료구조를 활용합니다.

규칙을 통해서 heap을 배열로 저장할 수 있습니다.

• 부모 노드 인덱스 번호 =  자식 노드 인덱스 번호 // 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 move_down(self, popped_idx):
        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
    
    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, data):
        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
        
        while self.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

 

🥥 Heap 시간 복잡도

depth를 h라고 표현한다면, n개의 노드를 가지는 heap에 데이터 삽입 또는 삭제 시,

최악의 경우 root노드에서 leaf노드까지 비교해야 하므로 h = log 2n에

시간 복잡도는 𝑂(𝑙𝑜𝑔𝑛)이 됩니다.

한번 실행시마다 50%의 실행할 수도 있는 명령을 제거한다는 의미입니다.

즉 50%의 실행시간을 단축시킬 수 있습니다.