[13일차 과제] 자료구조(힙)

1. 힙이란?

 

2. 힙의 동작 과정

• 삽입
• 삭제
• Heapify
• 루트 제거 과정

3. 시간 복잡도

 

4. 힙 구현

• insert()
• delete()
• print_heap()
• 최대 힙/ 최소 힙 둘 다 구현

---

1. 힙(Heap)이란?

 

1. 힙의 개념 및 특징

• 특정한 순서에 따라 정렬된 요소들을 저장하는 트리 기반의 자료구조
• 여러 개의 값들 중 최댓값이나 최솟값을 빠르게 찾기 위해 만들어진 자료구조
• 힙 트리에서는 중복된 값을 허용 (이진 탐색 트리에서는 중복값 허용 x)
• 우선 순위가 가장 높은 데이터(최댓값)가 루트에 위치
• 완전 이진 트리로 구현:
  마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 채워져 있는 형태
• 부모-자식 노드 관계 :
  
  • 최대 힙에서는 부모 노드가 항상 자식노드보다 크거나 같은 값
  • 최소 힙에서는 부모 노드가 항상 자식 노드보다 작거나 같은 값
• 배열 기반으로 구현하는 이유
  • 완전 이진 트리의 특성을 활용해 부모-자식 노드 간의 이동을 간단히 해결하기 위함
  • 트리를 탐색할 필요 없이 인덱스 연산만으로 접근이 가능
    • (왼쪽 자식 인덱스) = (부모 인덱스) x 2 
    • (오른쪽 자식 인덱스) = (부모 인덱스) x 2 + 1
    • (부모 인덱스) = (자식 인덱스) / 2
• 일반 이진 트리와의 차이점 

	일반 이진 트리	힙 (완전 이진 트리)
정의	자식 노드를 최대 2개까지만 가지는 트리	마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 채워져 있는 형태
노드 규칙	부모-자식 노드 간의 특별한 규칙이 없음	부모 노드는 항상 자식 노드보다 크거나 같음 (최대 힙) 또는 작거나 같음 (최소 힙)
주요 목적	데이터의 계층적 표현 및 탐색	우선순위 큐 구현, 최댓값/최솟값 탐색
구현 방식	주로 포인터를 이용해 노드 연결하여 구현	중간에 빈 공간이 없어, 메모리 낭비가 없는 배열로 구현

 

3. 힙 종류

• 최대 힙(Max Heap)
  • 최대 트리 : 각 노드의 키 값이 자식 노드가 있다면 그 자식의 키 값보다 크거나 같은 트리
  • 최대 힙 : 최대 트리이면서 완전 이진 트리
• 최소 힙(Min Heap)
  • 최소 트리 : 각 노드의 키 값이 자식노드가 있다며녀 그 자식의 키 값보다 작거나 같은 트리
  • 최소 힙 : 최소 트리이면서 완전 이진 트리
• 그 외 : 이진 힙, 피보나치 힙, 이항 힙, Min-Max 힙

---

2. 힙의 동작과정

1. 삽입(Insert)

1. 트리의 가장 마지막 자리에 새로운 원소를 삽입
2. 새로 삽입한 노드와 부모 노드 값 비교 (Heapify Up)
   • 최대 힙 : 부모 노드보다 값이 크면 위치를 교환
   • 최소 힙 : 부모 노드보다 값이 작으면 위치를 교환
3. 부모 노드와 비교하여 올바른 위치를 찾을 때까지 반복

 

2. 삭제(Delete)

• 힙의 삭제는 루트 노드에서만 삭제가 이루어짐
  • 최대 힙일 경우, 최댓값을 삭제
  • 최소 힙일 경우, 최솟값을 삭제

1. 루트 노드를 삭제
2. 트리의 가장 마지막 노드를 루트 노드로 옮김
3. 루트 노드와 자식 노드 값을 비교 (Heapify Down)
   • 최대 힙 : 두 자식 중 큰 값과 비교하여 자식이 더 크면 위치를 교환
   • 최소 힙 : 두 자식 중 작은 값과 비교하여 자식이 더 작으면 위치를 교환
4. 자식 노드와 비교하여 올바른 위치를 찾을 때까지 이 과정을 반복

최대 힙 삽입	최대 힙 삭제
최대 힙 삽입	최대 힙 삭제

 

3. Heapify

• 데이터나 배열을 힙 구조로 재배열하는 과정
• 일반 배열 상태에서 힙 성질(부모-자식 노드간 관계)을 만족하도록, 노드 위치를 아래로 내리며 질서를 잡는 과정
• 삽입 / 삭제 후 힙 조건을 만족하도록 하는 과정에서 사용되는 연산
  • 삽입 후 -> Heapify Up (상향식)
  • 삭제 후 -> Heapify Down (하향식)

 

4. 루트 제거 과정

• 힙에서 루트 노드의 값을 반환하고 제거하는 연산
  • 최대 힙 : 최댓값 반환 및 제거
  • 최소 힙 : 최솟값 반환 및 제거
• 삭제와 동일한 과정이지만, 반환 값을 활용하는 것에 초점
  
  • 삭제 : 노드 제거를 위함, 반환 값 없음
  • 루트 제거 : 값을 꺼내서 활용하기 위함, 루트 값 반환

1. 루트 노드의 값을 저장 (반환하기 위해서)
2. 트리의 가장 마지막 노드를 루트 자리로 이동
3. 마지막 노드였던 자리 제거
4. 루트와 자식 노드 비교 (Heapify Down)
   • 최대 힙 : 두 자식 중 큰 값과 비교하여 자식이 더 크면 위치를 교환
   • 최소 힙 : 두 자식 중 작은 값과 비교하여 자식이 더 작으면 위치를 교환
5. 올바른 위치를 찾을 때까지 반복
6. 저장해둔 루트 값을 반환

---

3. 시간 복잡도

연산	시간 복잡도	설명
최대/최소 조회	O(1)	루트 노드 참조만 하면 됨
삽입	O(log n)	원소를 맨 끝에 추가 후, 부모 노드와 비교하여 위로 올라감 (상향식)
삭제	O(log n)	루트 노드를 삭제하고, 맨 마지막 노드를 루트로 올린 뒤, 자식 노드와 비교하며 내려감 (하향식)
Heapify	O(n)	n개의 데이터를 가진 배열을 힙으로 한 번에 구성

---

4. 힙 구현

# class MaxHeap 최대 힙 구현

• init 생성자 :
  • 힙은 초기에 데이터를 담을 배열만 있으면 됨
• insert() :
  
  • 삽입할 요소를 매개변수로 받아옴
  • 배열에 값 삽입
  • 방금 삽입한(=마지막) 원소의 인덱스 cur = (배열길이) - 1
  • 삽입한 위치(cur)부터 heapify_up 수행
• heapify_up() :
  • 인덱스가 0이면 루트이므로 return (끝)
  • 현재 노드의 부모 인덱스 구하기
    (힙 배열의 인덱스가 0부터 시작하기 때문에 cur // 2는 안됨)
  • 현재 노드 요소가 부모 노드 요소보다 크면 두 요소의 자리를 바꿈
  • 삽입했던 요소가 parent 위치에 있다. 완벽히 heap 될 때까지 heapify_up 재귀호출
• delete() :
  • 배열이 비어 있으면 return (끝)
• heapify_down() :
  • 왼쪽, 오른쪽 자식 노드 인덱스
  • 현재 왼쪽, 오른쪽 중 가장 큰 값의 인덱스를 담을 변수 (초기값 = cur)
  • 자식이 배열 범위 안에 있을 때, 왼쪽(오른쪽) 자식이 더 크면 big 갱신
  • cur이 가장 크면 힙 조건 만족하므로 종료
  • 두 요소의 자리를 바꾸고 완벽히 heap 될 때까지 heapify_down 재귀호출
• get_max() : 
  • delete와 다르게 요소 삭제 없이 루트 값(=최댓값)만 반환
  • 배열이 비어있으면 None 리턴
    아니면 루트 노드 리턴
• print_heap() :
  • 배열 전체 출력

# 1. MaxHeap 구현
class MaxHeap:
    def __init__(self):     
        self.h_arr = []     # 힙은 초기에 데이터를 담을 배열만 있으면 됨

    # 삽입
    def insert(self, value):            # 삽입할 요소 매개변수로 받아옴
        self.h_arr.append(value)        # 배열에 값 삽입
        cur = len(self.h_arr) - 1      # 방금 삽입한(=마지막) 원소의 인덱스 cur = (배열길이) - 1
        self.heapify_up(cur)           # 삽입한 위치(cur)부터 heapify_up 수행

    def heapify_up(self, cur):
        if cur == 0:                    # 인덱스가 0이면 루트이므로 return (끝)
            return
        parent = (cur - 1) // 2         # 현재 노드의 부모 인덱스 구하기. 힙 배열의 인덱스가 0부터 시작 하기 때문에 cur // 2는 안됨
        if self.h_arr[cur] > self.h_arr[parent]:    # 현재 노드 요소가 부모 노드 요소보다 크면
            self.h_arr[cur], self.h_arr[parent] = self.h_arr[parent], self.h_arr[cur]   # 두 요소의 자리를 바꿈 (튜플로 처리하는 swap)
            # i = self.h_arr[cur]
            # self.h_arr[cur] = self.h_arr[parent]
            # self.h_arr[parent] = i
            self.heapify_up(parent)         # 삽입했던 요소가 parent 위치에 있다. 완벽히 heap이 될 때까지 heapify_up 재귀호출

    # 삭제
    def delete(self):
        if len(self.h_arr) == 0:     # 배열이 비어 있으면 return (끝)
            return 
        self.h_arr[0] = self.h_arr[-1]     # 마지막 노드를 루트 노드로 이동 (-1 = len(self.h_arr) - 1)
        self.h_arr.pop()                   # 마지막 노드 제거
        self.heapify_down(0)               # 루트에 대해 heapify_down 수행

    def heapify_down(self, cur):
        left = 2 * cur + 1      # 왼쪽 자식 노드 인덱스
        right = 2 * cur + 2     # 오른쪽 자식 노드 인덱스
        big = cur               # 현재 왼쪽, 오른쪽 중 가장 큰 값의 인덱스 (초기값 = cur)

        # 자식이 배열 범위 안에 있을 때만 비교
        if left < len(self.h_arr) and self.h_arr[left] > self.h_arr[big]:       # 왼쪽 자식이 더 크면 big 갱신
            big = left
        if right < len(self.h_arr) and self.h_arr[right] > self.h_arr[big]:     # 오른쪽 자식이 더 크면 big 갱신
            big = right

        if big == cur:      # cur이 가장 크면 힙 조건 만족 -> 종료
            return

        self.h_arr[big], self.h_arr[cur] = self.h_arr[cur], self.h_arr[big]     # 두 요소의 자리를 바꿈
        self.heapify_down(big)      # 완벽히 heap이 될 때까지 heapify_down 수행

    # 최댓값 조회 (삭제 없이 루트 값만 반환)
    def get_max(self):
        if len(self.h_arr) == 0:        # 배열이 비어있으면 delete와 달리 값을 반환해야하므로
            return None                 # None 리턴
        return self.h_arr[0]            # 루트 노드 = 최댓값

    # heap 데이터 출력
    def print_heap(self):
        print(self.h_arr)       # 배열 전체를 프린트

# 2. 최대 힙 생성
h = MaxHeap()

# 3. 삽입 및 조회
h.insert(5)
h.insert(10)
h.insert(3)
h.insert(15)
h.print_heap()  # [15, 10, 3, 5]

# 4. 삭제 및 조회
h.delete()
h.print_heap()  # [10, 5, 3]

 

# 최소 힙 구현

• 최대 힙을 활용해 최소 힙 구현
• >를 <로, big을 small로 

# MinHeap 구현
class MinHeap:
    def __init__(self):     
        self.h_arr = []     # 힙은 초기에 데이터를 담을 배열만 있으면 됨

    # 삽입
    def insert(self, value):            # 삽입할 요소 매개변수로 받아옴
        self.h_arr.append(value)        # 배열에 값 삽입
        cur = len(self.h_arr) - 1      # 방금 삽입한(=마지막) 원소의 인덱스 cur = (배열길이) - 1
        self.heapify_up(cur)           # 삽입한 위치(cur)부터 heapify_up 수행

    def heapify_up(self, cur):
        if cur == 0:                    # 인덱스가 0이면 루트이므로 return (끝)
            return
        parent = (cur - 1) // 2         # 현재 노드의 부모 인덱스 구하기. 힙 배열의 인덱스가 0부터 시작 하기 때문에 cur // 2는 안됨
        if self.h_arr[cur] < self.h_arr[parent]:    # 현재 노드 요소가 부모 노드 요소보다 작으면
            self.h_arr[cur], self.h_arr[parent] = self.h_arr[parent], self.h_arr[cur]   # 두 요소의 자리를 바꿈 (튜플로 처리하는 swap)
            # i = self.h_arr[cur]
            # self.h_arr[cur] = self.h_arr[parent]
            # self.h_arr[parent] = i
            self.heapify_up(parent)         # 삽입했던 요소가 parent 위치에 있다. 완벽히 heap이 될 때까지 heapify_up 재귀호출

    # 삭제
    def delete(self):
        if len(self.h_arr) == 0:     # 배열이 비어 있으면 return (끝)
            return 
        self.h_arr[0] = self.h_arr[-1]     # 마지막 노드를 루트 노드로 이동 (-1 = len(self.h_arr) - 1)
        self.h_arr.pop()                   # 마지막 노드 제거
        self.heapify_down(0)               # 루트에 대해 heapify_down 수행

    def heapify_down(self, cur):
        left = 2 * cur + 1      # 왼쪽 자식 노드 인덱스
        right = 2 * cur + 2     # 오른쪽 자식 노드 인덱스
        small = cur               # 현재 왼쪽, 오른쪽 중 가장 작은 값의 인덱스 (초기값 = cur)

        # 자식이 배열 범위 안에 있을 때만 비교
        if left < len(self.h_arr) and self.h_arr[left] < self.h_arr[small]:       # 왼쪽 자식이 더 크면 small 갱신
            small = left
        if right < len(self.h_arr) and self.h_arr[right] < self.h_arr[small]:     # 오른쪽 자식이 더 크면 small 갱신
            small = right

        if small == cur:      # cur이 가장 작으면 힙 조건 만족 -> 종료
            return

        self.h_arr[small], self.h_arr[cur] = self.h_arr[cur], self.h_arr[small]     # 두 요소의 자리를 바꿈
        self.heapify_down(small)      # 완벽히 heap이 될 때까지 heapify_down 수행

    # 최솟값 조회 (삭제 없이 루트 값만 반환)
    def get_min(self):
        if len(self.h_arr) == 0:        # 배열이 비어있으면 delete와 달리 값을 반환해야하므로
            return None                 # None 리턴
        return self.h_arr[0]            # 루트 노드 = 최솟값

    # heap 데이터 출력
    def print_heap(self):
        print(self.h_arr)       # 배열 전체를 프린트

---

 

* 힙을 구현할 때는 init 함수에 배열만 있으면 된다.

 

* 다른 언어와 달리 파이썬에서는 두 변수의 위치를 바꿀 때 튜플을 사용해 바꿔줄 수 있어 편리하다.

 

* 부모와 자식의 인덱스를 넣는 과정에서 틀리지 않도록 주의하자.

 

* 힙을 구현한 코드를 C언어로 본 적은 있어도 직접 구현한 적은 처음이라 해시테이블과 마찬가지로 시간이 오래 걸렸지만 뿌듯하다.