[패스트캠퍼스 :: 코딩테스트 인강] 5주차 ① 힙 (Heap)

알고리즘/기술면접 완전 정복 올인원 패키지 Online

 

자료구조(힙) - 01. 힙 구조

자료구조(힙) - 02. 힙 구조 파이썬 구현 - 1

자료구조(힙) - 03. 힙 구조 파이썬 구현 - 2

자료구조(힙) - 04. 힙에 데이터 삭제 구현

 

---

 

2021.03.19

 

지금 수강하고 있는 강의는 "자료구조 + 알고리즘 + 유형별 문제 풀이 + 기술 면접 대비"

이렇게 4가지 파트로 구분되어 있고, 그중 자료구조의 마지막 부분이 이번 주에 수강한 힙(Heap) 구조에 관련된 내용이다.

 

자료구조 부분을 들을 때마다 느끼는 바는,

지금까지 다양한 유튜브 영상/강의, 책, 다른 블로그 글들을 읽으면서 차근차근 이해해왔다고 생각한 부분들, 

막 얽혀있고, 정리가 다 되지 못한 부분을 확실하게 정리할 수 있게 설명해주신다는 것이다.

 

자료구조를 코드로 표현하고, 구현하는 방식은 언제나 그렇듯, 정답이 없듯이,

수 많은 플랫폼에서, 혹은 개인이 표현하고 있는 것들이 다 다르지만

개념 하나는 확실하게 잡고 갈 수 있어서 좋다.

 

이번 주도 머릿속에서 굴러다니던 힙 구조를 한 80% 정도 이해했다.

 

나머지 20%는 다시 반복해서 강의를 들으면서 여러 번 코드로 구현해 보면 채워질 것 같다.

 

---

1. 힙 (Heap) 이란?

 

• 힙: 데이터에서 최대값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리(Complete Binary Tree)
  • 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

• 힙을 사용하는 이유
  • 배열에 데이터를 넣고, 최댓값과 최솟값을 찾으려면 O(n) 이 걸림
  • 이에 반해, 힙에 데이터를 넣고, 최대값과 최솟값을 찾으면, 𝑂(𝑙𝑜𝑔𝑛)O(logn) 이 걸림
  • 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨

 

2. 힙 (Heap) 구조

• 힙은 최댓값을 구하기 위한 구조 (최대 힙, Max Heap)와, 최솟값을 구하기 위한 구조 (최소 힙, Min Heap)로 분류할 수 있음
• 힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조임
  1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)
     • 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음
  2. 완전 이진트리 형태를 가짐

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

• 공통점: 힙과 이진 탐색 트리는 모두 이진트리임
• 차이점:
  • 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우)
  • 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼
  • 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
    • 힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음
• 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최솟값 검색을 위한 구조 중 하나로 이해하면 됨 

  

 

 

 

4. 힙과 배열

• 일반적으로 힙 구현 시 배열 자료구조를 활용함
• 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 좀 더 수월함
  • 부모 노드 인덱스 번호 (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 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)
        return True   

 

 

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    

 

 

 

 

---

힙 구조를 구현해 보면서 좀 더 이해가 더 잘되고,

이진트리와도 차이를 느꼈고, 어느 분야에 활용할 수 있는 구조인지 조금은 알 것 같아서 좋았다.

 

 

힙 구조를 마지막으로 자료구조 파트는 마무리되었고, 

다음부터는 알고리즘과 코딩 테스트를 위한 유형 문제풀이 하게 된다.

 

 

[패스트캠퍼스 100% 환급 챌린지 미션 중입니다.]

 

 

 

 

알고리즘 / 기술면접 완전 정복 올인원 패키지 Online. | 패스트캠퍼스