(6) Tree - Heap

■ Heap

1) 정의 :

연관된 데이터에서 최대값 / 최소값을 빠르게 찾기 위해 고안된 "완전 이진 트리"

※ 완전이진트리 : 노드 삽입시 최하단 왼쪽 노드부터 차례로 삽입하는 트리

 

2) 사용 이유 :

- array( and python list)에서 배열 길이만큼 index searching시간 소요 O(N)

- heap에 데이터를 넣으면 O(log N) 평균시간이 걸림

- 최대 최소를 빠르게 찾아야 하는 경우 유용

  ( PS 문제에 최소/최대 이용하여 문제 빠르게 해결하는 경우 있었음 )

 

3) 종류

(1) min heap

- 정의 :

   (a) 각 노드의 값은 해당 노드의 자식 값보다 작음

   (b) 완전 이진트리 형태를 가짐

- python 기본 heapq library 경우 min heap으로 구성

 

 

■ heap 구성 방법

1) 데이터 삽입

(1) 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입

(2) 부모노드보다 작으면 swap해주고 반복 (min-heap의 경우)

---

2) 데이터 삭제

(1) 최상단 노드 삭제, 가장 마지막에 추가한 item을 최상단과 swap

(2) root node의 child와 값을 swap( min heap의 경우 root가 더 크면 오른쪽→왼쪽 child와 바꿔줌 )

 

※ heap의 노드 index 위치

• 부모 노드 인덱스 번호 (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

 

 

■ 코드 구현

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    

> 테스트 코드

myheap = Heap()
myheap.insert(4)
myheap.insert(2)
myheap.insert(3)
myheap.insert(78)
myheap.insert(9)
myheap.insert(10)
print(myheap.heap_array)

while myheap.heap_array:
    tmp_poped = myheap.pop()
    print(tmp_poped)
    if not tmp_poped:
        break

>>>
[None, 78, 9, 10, 2, 4, 3]
78
10
9
4
3
2
None

---

참조 :

gyoogle.dev/blog/computer-science/data-structure/Heap.html

힙(Heap) | 👨🏻‍💻 Tech Interview

https://velog.io/@sossont/Python-heapq-%EB%AA%A8%EB%93%88

[Python] heapq 모듈