Heap

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 Complete Binary Tree
- 완전 이진 트리 Complete Binary Tree
  - node 삽입시 최하단 왼쪽 node부터 차례대로 삽입하는 Tree

사용하는 이유

배열의 최대값 최소값 찾기 복잡도 \( O_{n} \) (데이터 넣고 빼는 거 까지)
heap의 최대값 최소값 찾기 복잡도 \( O_{logn} \) (데이터 넣고 빼는 거 까지)
우선 순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 경우에 사용함

구조

Max Heap : 최대값을 구하기 위한 구조
Min Heap : 최소값을 구하기 위한 구조
2가지 조건
- Max Heap의 경우 각 node의 값은 해당 mode의 자식 node가 가진 값보다 크거나 같아야 함.(Min Heap은 반대)
- 완전 이진 트리 형태를 가짐

Heap 과 Binary Search Tree

Heap

Max Heap의 경우 Parent Node의 값이 Child Node보다 크거나 같음
Child Node는 따로 정해진 규칙없이 배치된다
최대, 최소값을 구하기 위한 구조

Binary Search Tree

Parent Node의 값이 가장 크고 left Child Node의 값이 right Chile Node값보다 작다
탐색을 위한 구조

Heap 구현¶

배열 구현¶

배열은 인덱스가 0부터 시작하지만, 편의를 위해 root node의 인덱스는 1로 지정 (0에는 유의미한 값이 들어가지 않음)
- Parent Node's index = Child Node's index // 2
- Left Child Node's index = Parent Node's index * 2
- Righ Child Node's index = Parent Node's index * 2 + 1

heap class

In [156]:

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: No left node
        if left_child_popped_idx >= len(self.heap_array):
            return False
        # case2: No right node
        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: exgist both node
        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: No right node
            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: exgist both node
            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    

In [157]:

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

[None, 20, 10, 15, 5, 4, 8]

In [158]:

heap.pop()

Out[158]:

In [159]:

heap.heap_array

Out[159]:

[None, 15, 10, 8, 5, 4]

In [160]:

heap.heap_array

Out[160]:

[None, 15, 10, 8, 5, 4]

728x90