[코딩 + 알고리즘 완주반] 15일차. 힙

# 힙

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

완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

 

# 힙을 사용하는 이유

배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림

힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이 걸림

우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용

 

# 힙 구조

힙은 최대값을 구하기 위한 구조(최대힙) 와, 최소값을 구하기 위한 구조( 최소 힙) 으로 분류 가능

1. 각 노드의 값은 해당 노드의 자식노드가 가진 값보다 크거나 같다(최대힙)

• 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같음

2. 완전 이진 트리 형태

 

# 힙과 이진 탐색 트리의 공통점과 차이점

공통점 : 이진 트리

차이점 : 힙은 각 노드의 값이 자식 노드보다 크거나 같음

              이진 탐색 트리는 왼쪽 자식노드, 부모노드, 오른쪽 자식 노드 순서로 커짐

              힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른 쪽이라는 조건은 없음

                  - 자식 노드의 값은 왼쪽이 클 수도 있고 오른쪽이 클 수도 있음

              이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨

 

# 힙에 데이터 삽입하기

왼쪽 자식 노드 부터 채워가기

부모노드와 값을 비교해서 더 크면 자리 바꿔주기

 

# 힙의 데이터 삭제하기

보통 삭제는 최상단 노드를 삭제하는 것이 일반적임

(힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것)

상단의 데이터 삭제 시 가장 최하단부 왼쪽에 위치한 노드를 root 노드로 이동 ( 일반적으로 가장 마지막에 추가한 노드)

자식 노드와 값을 비교해서 위치를 바꿈 ( 큰 값을 root 노드로)

 

# 힙 구현

일반적으로 힙 구현시 배열 자료구조 활용

배열은 인덱스가 0번부터 시작하지만 힙 구현의 편의를 위해 root 노드 인덱스 번호를 1로 저장하면 구현이 좀 더 수월함

부모 노드 인덱스 번호  = 자식 노드 인덱스 번호 //2

왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 *2

오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호*2 + 1

 

# 힙에 데이터 삽입 구현 (Max Heap)

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(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) == 0:
            self.heap_array.append(None)
            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

# 힙에 데이터 삭제 구현 ( Max Heap )

    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

# 힙 시간 복잡도

depth (트리의 높이)를 h 라고 표기한다면,

n 개의 노드를 가지는 heap에 데이터 삽입 또는 삭제시 최악의 경우 root노드에서 leaf 노드까지 비교해야 하므로 h=logn에 가까우므로 시간 복잡도는 O(logn)