[자료구조] 힙(Heap)

힙이란

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

힙을 사용하는 이유

• 배열에서 최대/최소값 찾는 시간 복잡도: O(n) → 모든 데이터를 검색해야함
• 힙에서 최대/최소값 찾는 시간 복잡도: O(logn)
• 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현에 활용

---

힙 구조

• 최대값을 구하기 위한 최대 힙(Max Heap)과 최소값을 구하기 위한 최소 힙(Min Heap)으로 구분됨
• 힙은 두 가지 조건을 가지고 있는 자료구조임

1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)
   → 최대 힙의 경우 가장 위에 있는 노드가 최댓값~ 최소 힙의 경우 가장 위에 있는 노드가 최솟값
   → 힙의 구조를 갖추면 항상 데이터를 가장 위에 있는 루트 노드를 가져옴. 미트이 데이터를 모두 탐색할 필요 없이 루트 노드만 빼오면 됨~ 시간이 적게 걸리는 이유.
2. 완전 이진 트리의 형태를 가진다
   → 데이터를 넣을 때 항상 왼쪽부터 채워가게 돼 있음

• 완전 이진 트리
  → 이진 트리라서 자식은 두 개밖에 못 가짐

---

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

공통점 : 모두 이진 트리임

차이점:

• 힙은 각 노드가 자식 노드보다 크거나 같음 / 이진 탐색 트리는 왼쪽 자식 < 부모 < 오른쪽 자식 순으로 크기가 큼
• 힙은 자식 노드들의 크기 비교가 불가능함, 누가 더 크고 작은지 알 수 없음
• 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조

---

힙 데이터 변경

힙에 데이터 넣기

왼쪽 자식 노드를 우선시해서 데이터 채워넣기

루트 노드보다 삽입할 데이터가 더 클 경우 (max heap의 경우)

1. 일단 완전 이진 트리 구조에 맞춰서 데이터 삽입
2. 자식 노드와 부모 노드의 크기 비교 → 자식 노드가 더 클 경우 swap → 비교비교비교... → 자식이 더 크면 계속 swap

힙의 데이터 삭제

데이터 삭제 = 힙에서 데이터를 끄집어 내는거

1. 루트 노드에 있는 값을 끄집어 내기 (중간에 있는 값을 삭제하는 경우는 없음)
2. 가장 마지막에 들어갔던 데이터를 루트 노드로 올림
3. 루트 노드가 자식 노드보다 작을 경우,자식 노드 중 더 큰 값과 루트 노드를 바꿈

힙 구현

힙을 배열로 표현 → 완전 이진 트리의 형태라서 가능한 것
루트 노드는 index : 1 (편의상)

• 부모 노드 인덱스 = 자식노드//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_up(self, inserted_idx):
        #idx가 1이라면 루트 노드이기 때문에 바꿀 필요x
        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)
            retrun 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 = Heap(15)
heap.insert(10)
heap.insert(8)
heap.insert(5)
heap.insert(4)
heap.insert(20)
heap.heap_array

---

힙 데이터 삭제 코드 구현

#루트 노드를 다시 채워가면서 힙의 구조 만들어가기
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

        #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]:
                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:
                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]:
                    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:
                    return False
            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
                else:
                    return False
    
        return returned_data

---

힙 시간 복잡도

O(logn)