[자료구조] 힙(Heap)- 힙 동작과정, 힙의 시간복잡도, 파이썬 코드로 구현하기

 

[파이썬 자료구조] 트리(Tree), 이진 트리(Binary Tree), 트리 순회

[파이썬 자료구조와 알고리즘] 시간 복잡도, 빅오 표기법

---

힙(Heap)이란?

힙은 완전 이진 트리를 기반으로 한 자료구조이다.
각 노드가 자식 노드보다 작거나 같은(최소 힙) 또는
크거나 같은(최대 힙) 순서를 가지고 있는 자료구조이다.
 
최소 힙에서는 루트 노드가 항상 가장 작은 값을 가지고있으며,
최대 힙에선 가장 큰 값을 가지게 된다.

---

❓ 힙과 완전 이진트리는 어떤 관계를 가지고 있을까?

힙과 완전 이진트리는 알맹이와 그릇의 관계이다.
 
완전 이진트리는 노드를 왼쪽부터 빈틈없이 채워나가는 형태(그릇)이며,
힙은 이 구조를 그대로 가져와 부모 노드가 자식 노드보다 항상 크거나 작아야한다는 규칙(알맹이)를 채운 자료구조이다.
 
힙이 굳이 완전 이진트리를 사용하는 이유는
빈틈이 없는 완전 이진트리의 특성상 메모리낭비가 없고 일반 배열로 구현할 수 있으며
자식과 부모의 위치를 인덱스의 곱셉, 나눗셈 연산으로만 빠르게 구할 수 있기 때문이다.
 
결론적으로 힙은 항상 완전 이진트리의 구조를 갖추고 있지만
완전 이진트리는 항상 힙을 만족하는것은 아니다.

---

❓ 그럼 왜 배열 기반으로 구현할까?

힙은 완전 이진 트리 구조를 사용하고 있기 때문에
연결 리스트나 포인터 없이 일반 배열만으로도 구현이 가능하다.
 
예를 들어 아래의 힙 구조를 배열로 표현하면
[10, 20, 30, 40, 50]과 같다.

# 힙구조
      10
     /  \
   20    30
  / \
40  50

배열에선 자식과 부모의 위치를 인덱스의 곱셉, 나눗셈 연산으로만 빠르게 구할 수 있기 때문에
힙은 메모리에서 사용량이 적고 구현도 간단한 배열을 기반으로 구현하고 있다.

---

❓ 일반 이진트리와는 어떤것이 다를까?

일반 이진트리는 각 노드가 최대 두 개의 자식을 가진다는 특징이 있다.
 
하지만 힙은 완전 이진트리의 구조를 유지하면서
부모와 자식 사이의 정렬 규칙도 만족해야한다.
 
아래의 트리 구조는 이진트리이긴 하지만 
부모 노드가 자식보다 크거나 작다는 일관성있는 규칙을 만족하지 않아
힙 구조가 될 순 없다.

# 트리 구조
      10
     /  \
   100    3

즉, 모든 힙은 이진 트리이지만 모든 이진트리는 힙이 아니다.
 

💡 Tip : 힙은 최대/최소값 확인에만 최적화되어 있다. (전체 탐색엔 효율적이지 않음)

---

최대 힙과 최소 힙

힙은 부모 노드와 자식 노드 사이의 대소 관계만 유지하고 있다.
최대 힙에선 부모 노드가 자식 노드보다 크거나 같아야 하며,
최소 힙에선 부모 노드가 자식 노드보다 작거나 같아야 한다.
 
이때 중요한점은 형제 노드끼리는 비교를 하지 않는다!
예를 들어 아래 이미지처럼 최대 힙에서 70과 60이 형제 노드라면
두 값의 크기에 대한 관계는 크게 중요하지 않다.
 
부모와 자식 사이의 규칙만 지킨다면 힙 구조가 될 수 있다.

---

최대 힙 (Max Heap)

최대 힙은 부모 노드가 자식 노드보다 항상 크거나 같은 구조를 의미한다.
즉, 가장 큰 값이 루트에 위치하고 있으며
힙 정렬(Heap Sort)은 보통 최대 힙을 사용하고 있다.

---

최소 힙 (Min Heap)

최소 힙은 부모 노드가 자식 노드보다 항상 작거나 같은 구조로
가장 작은 값이 루트에 위치하게 된다.

---

힙의 동작 과정

힙은 데이터를 추가, 삭제할때마다 부모와 자식 노드의 대소 관계를 유지해야한다.
그렇기 때문에 삽입, 삭제의 연산이 발생하면
힙의 규칙이 깨지지 않도록 하기 위해 재정렬(Heapify)과정을 수행하게 된다.

---

1) 삽입 (Insert)

기존의 힙에 새로운 데이터를 삽입할때는 
완전 이진트리의 구조를 유지하기 위해 가장 마지막 위치에 노드를 추가한다.
 
그 후 추가한 노드의 부모노드와 비교하면서 힙 조건을 만족할 때 까지 위로 이동한다.
이 과정을 Up Heap 이나 Bubble UP이라고 부르기도 한다.
 

예제 ) 최대 힙에 25 삽입하기.

1. 25 추가하기
2. 25가 부모 5보다 크기때문에 위치 교환
3. 교환된 위치의 부모인 40보단 작기때문에 조건 만족, 재정렬 종료

---

2) 삭제 (Delete)

특정 노드를 삭제하면 완전 이진트리의 구조가 깨질수도 있다.
그렇기 때문에 마지막 노드를 삭제된 위치로 이동시킨 후
힙 조건을 만족시킬 수 있도록 재정렬하는 과정이 필요하다.
 

예제) 최대 힙에서 40 삭제하기

1. 삭제 할 노드 40선택
2. 마지막 노드 15를 삭제된 위치로 이동
3. 이동한 위치의 부모 노드 50보단 작기때문에 조건 만족, 재정렬 종료

---

3) Heapify

Heapify는 힙의 규칙이 져있을 때 이를 다시 힙 구조로 만드는 과정을 말한다.
삽입이나 삭제가 발생하면 부모와 자식의 대소관계가 깨질 수 있는데,
Heapify를 통해 위치를 이동하면서 힙을 재정렬한다.
 

예제 ) 최대 힙 재정렬하기

1. 루트 노드 10에서 조건비교 시작
2. 자식 노드 30과 40중 더 큰 값인 40과 비교
3. 40이 더 크기때문에 위치 교환
4. 이동한 10을 다시 자식 노드인 15와 비교
5. 15가 더 크기 때문에 위치 교환
6. 모든 조건을 만족하면 Heapify 종료

※ 삽입 : 아래에서 위로 올라가며 Heapify 실행
※ 삭제 : 위에서 아래로 내려가며 Heapify 실행

---

4) root 제거

최대 힙의 가장 큰 특징은 최댓값이 항상 루트 노드에 위치한다는 점이다.
그렇기 때문에 힙에서 최댓값을 꺼내기 위해 루트 노드를 제거하고 나면,
원래 그 자리에 있던 기준이 사라져 힙의 규칙이 깨지게 된다.
그래서 비어버린 루트 자리를 채워가며 힙 구조를 복구한다.
 

예제) 최대 힙에서 root 제거하기

1. 루트 노드 50을 결과로 저장
2. 마지막 노드인 15를 루트 위치로 이동
3. 자식 노드 중 더 큰 값인 40과 비교
4. 40이 더 크기 때문에 위치 교환
5. 힙 조건 만족, 재정렬 종료

 

💡 root노드 제거는 언제 사용할까?

루트 노드를 제거하는 연산은 보통 우선순위 큐에서 가장 우선순위가 높은 데이터를 꺼내거나,
힙 정렬을 수행할 때 사용된다.
 
힙은 항상 최댓값 또는 최솟값이 루트 노드에 위치하고 있기 때문에
전체 데이터를 탐색하지 않고도 원하는 값을 빠르게 추출할 수 있어 사용한다.

• 최대 힙의 루트 제거 : 전체 데이터 중 최댓값을 꺼내고 싶을 때 사용
• 최소 힙의 루트 제거 : 전체 데이터 중 최소값을 꺼내고 싶을 때 사용

---

힙의 시간복잡도

힙은 완전 이진트리 구조를 사용하여 트리의 높이가 불필요하게 커지는것을 막을 수 있다.
그렇기 때문에 삽입, 삭제와 같은 주요 연산들을 효율적으로 처리할 수 있고,
우선순위 큐와 같은 기능을 구현하는데 주로 활용된다.

---

1) 삽입 : O(log n)

새로운 노드는 완전 이진트리의 마지막 위치에 삽입된다.
그리고 부모 노드와 비교하며 힙 조건을 만족할때까지 위로 이동한다.
 
이때 최악의 경우 리프 노드에서 루트 노드까지 이동해야할수도 있으며,
이동 거리는 트리의 높이와 같기 때문에 삽입의 시간 복잡도는 O(log n)이다.

---

2) 삭제 : O(log n)

노드를 삭제한 후 힙 구조의 마지막 노드를 삭제한 노드의 위치로 이동시킨다.
이동된 위치에서 부모 또는 자식노드와 비교하며 올바를 위치를 찾을때까지 이동한다.
 
이것도 삽입과 같은 개념으로
최악의 경우 트리의 가장 아래 레벨까지 이동할 수 있기 때문에 시간 복잡도는 O(log n)이다.

---

3) 탐색 : O(n)

힙은 부모와 자식 노드 사이의 대소 관계만 유지하면 된다. (전체 정렬이 된 구조는 아님)
그렇기 때문에 특정 값을 찾기 위해서는 모든 노드를 하나씩 다 확인해야할수도 있다.
 
최악의 경우 전체 노드를 모두 다 탐색해야하기 때문에 O(n)의 시간 복잡도를 가지게 된다.

---

💡 힙 정렬 원리

1. 주어진 리스트를 최대 힙으로 만든다.
2. 루트에 있는 가장 큰 값을 리스트의 맨 뒤와 바꾼다.
3. 맨 뒤로 간 값은 정렬이 끝난 값으로 본다.
4. 남은 부분만 다시 최대 힙으로 만든다.
5. 과정을 반복하면 오름차숨 정렬, 즉 힙 정렬이 완성된다.

# 예시 리스트
[4, 2, 7, 1]

# 1단계 : 최대 힙 만들기
[7, 2, 4, 1]

# 2단계 : 루트7을 맨 뒤와 교환 > 7 정렬 완료
[1, 2, 4, 7]

# 3단계 : 남은 부분을 최대 힙으로 구성
[4, 2, 1], [7]

# 4단계 : 루트4와 맨 뒤 교환 > 4 정렬 완료
[1, 2, 4], [7]

# 최종 정렬
[1, 2, 4, 7]

---

힙을 파이썬 코드로 구현해보면?

파이썬의 리스트(배열)을 활용하여 이진 트리 구조를 구현한다. (가장 효율적)
인덱스 계산을 쉽게 만들기 위해
리스트 0번 인덱스는 비워두고(None), 1번 인덱스부터 루트노드로 사용한다.
 

📌 구현 주요사항

• 부모 노드 인덱스 : 현재 인덱스 // 2
• 왼쪽 자식 노드 인덱스 : 현재 인덱스 + 2
• 오른쪽 자식 노드 인덱스 : 현재 인덱스 * 2 + 1

---

1) 최대 힙으로 구현

# 최대 힙 구현 클래스
class MaxHeap:
    def __init__(self):
        # 숫자 저장할 리스트 생성
        self.heap = [None]

    # 삽입
    def insert(self, data):
        # 맨 뒤에 데이터 추가
        self.heap.append(data)
        # 마지막에 추가한 데이터의 방 번호(인덱스) 변수지정
        idx = len(self.heap) - 1
        
        # 추가한 데이터를 부모 노드와 비교하며 위로 올림
        while idx > 1:
            # 부모 노드의 방 번호 계산, 변수지정
            parent_idx = idx // 2

            # 만약 부모 노드의 숫자가 현재 내 숫자보다 작다면 (최대 힙 규칙 위반!)
            if self.heap[parent_idx] < self.heap[idx]:
                # 부모와 나의 위치를 서로 바꿈 (위로 올림)
                self.heap[parent_idx], self.heap[idx] = self.heap[idx], self.heap[parent_idx]
                # 바꾼 후 내 방 인덱스를 부모의 방 인덱스로 변경 (내 위치 추적)
                idx = parent_idx
            else:
                # 부모가 나보다 크거나 같다면 조건 만족, 반복 종료
                break

    # 삭제
    def delete(self):
        # 뽑아낼 데이터가 없으면(0번 방 None만 남았다면) 빈 값 반환
        if len(self.heap) <= 1:
            return None

        # 데이터가 1개만 있으면 바로 반환
        if len(self.heap) == 2:
            return self.heap.pop()
        
        # 1번 인덱스(루트노드)에 있는 최댓값 데이터를 root_data 변수에 저장
        root_data = self.heap[1]

        # 맨 마지막 칸의 데이터를 뽑아내서 비어버린 1번 인덱스에 대입
        self.heap[1] = self.heap.pop()
        
        # 임시로 1번 방에 있는 데이터의 방 번호(위치) 변수지정
        idx = 1

        # 왼쪽 자식 노드가 존재하는 동안 계속 반복 (자식이 없으면 바닥에 도달)
        while idx * 2 < len(self.heap):

            # 왼쪽 자식과 오른쪽 자식의 방 번호 계산, 변수지정
            left = idx * 2
            right = idx * 2 + 1

            # 우선 왼쪽 자식이 더 크다고 가정, 가장 큰 자식 방 번호로 지정
            largest = left
            
            # 만약 오른쪽 자식도 존재하고, 오른쪽 자식이 왼쪽 자식보다 더 크다면
            if right < len(self.heap) and self.heap[right] > self.heap[left]:
                # 가장 큰 자식 방 번호를 오른쪽 자식으로 변경
                largest = right
            
            # 만약 현재 내 숫자가 가장 큰 자식의 숫자보다 작다면 (최대 힙 규칙 위반!)
            if self.heap[idx] < self.heap[largest]:
                # 나와 가장 큰 자식의 위치를 서로 바꿈 (아래로 내림)
                self.heap[idx], self.heap[largest] = self.heap[largest], self.heap[idx]
                # 바꾼 후 내 방 인덱스를 자식의 방 인덱스로 변경 (내 위치 추적)
                idx = largest
            else:
                # 내가 자식들보다 크거나 같다면 규칙 맞음, 종료
                break
                
        # 진짜 최댓값 데이터(루트 노드 값)를 최종 반환
        return root_data

    # 출력
    def print_heap(self):
        # 비워둔 0번 인덱스(None)를 제외하고, 1번 방부터 실제 데이터만 출력
        print(self.heap[1:])

# 구현 테스트
print("----- 최대 힙 -----")

max_heap = MaxHeap()

max_heap.insert(10)
max_heap.insert(30)
max_heap.insert(20)
max_heap.insert(50)
max_heap.insert(40)

max_heap.print_heap()

print("삭제:", max_heap.delete())
max_heap.print_heap()

print("삭제:", max_heap.delete())
max_heap.print_heap()

실행 결과 ▶

---

2)  최소 힙으로 구현

# 최소 힙 구현 클래스
class MinHeap:
    def __init__(self):
        # 숫자 저장할 리스트 생성
        self.heap = [None]

    # 삽입
    def insert(self, data):
        # 맨 뒤에 데이터 추가
        self.heap.append(data)
        # 마지막에 추가한 데이터의 방 번호(인덱스) 변수지정
        idx = len(self.heap) - 1
        
        # 추가한 데이터 부모 노드와 비교하며 위로 올림
        while idx > 1:
            # 부모 노드의 방 번호 계산, 변수지정
            parent_idx = idx // 2

            # 만약 부모 노드의 숫자가 현재 내 숫자보다 크다면 (최소 힙 규칙 위반!)
            if self.heap[parent_idx] > self.heap[idx]:
                # 부모와 나의 위치를 서로 바꿈 (위로 올림)
                self.heap[parent_idx], self.heap[idx] = self.heap[idx], self.heap[parent_idx]
                # 바꾼 후 내 방 인덱스를 부모의 방 인덱스로 변경 (내 위치 추적)
                idx = parent_idx
            else:
                # 부모가 나보다 작거나 같다면 조건 만족, 반복 종료
                break

    # 삭제
    def delete(self):
        # 뽑아낼 데이터 없으면(0번 방 None만 남았다면) 빈 값 반환
        if len(self.heap) <= 1:
            return None

        # 데이터가 1개만 있으면 바로 반환
        if len(self.heap) == 2:
            return self.heap.pop()
        
        # 1번 인덱스(루트노드)에 있는 최솟값 데이터를 root_data 변수에 저장
        root_data = self.heap[1]

        # 맨 마지막 칸의 데이터를 뽑아내서 비어버린 1번 인덱스에 대입
        self.heap[1] = self.heap.pop()
        
        # 임시로 1번 방에 있는 데이터의 방 번호(위치) 변수지정
        idx = 1

        # 왼쪽 자식 노드가 존재하는 동안 계속 반복 (자식이 없으면 바닥에 도달)
        while idx * 2 < len(self.heap):

            # 왼쪽 자식과 오른쪽 자식의 방 번호 계산 및 변수지정
            left = idx * 2
            right = idx * 2 + 1

            # 일단 왼쪽 자식이 더 작다고 가정, 가장 작은 자식 방 번호로 지정
            smallest = left
            
            # 만약 오른쪽 자식도 존재하고, 오른쪽 자식이 왼쪽 자식보다 더 작다면
            if right < len(self.heap) and self.heap[right] < self.heap[left]:
                # 가장 작은 자식 방 번호를 오른쪽 자식으로 변경
                smallest = right
            
            # 만약 현재 내 숫자가 가장 작은 자식의 숫자보다 크다면 (최소 힙 규칙 위반!)
            if self.heap[idx] > self.heap[smallest]:
                # 나와 가장 작은 자식의 위치를 서로 바꿈 (아래로 내림)
                self.heap[idx], self.heap[smallest] = self.heap[smallest], self.heap[idx]
                # 바꾼 후 내 방 인덱스를 자식의 방 인덱스로 변경 (내 위치 추적)
                idx = smallest
            else:
                # 내가 자식들보다 작거나 같다면 조건 만족, 종료
                break
                
        # 최솟값 데이터(루트 노드 값) 최종 반환
        return root_data

    # 출력
    def print_heap(self):
        # 비워둔 0번 인덱스(None)를 제외하고, 1번 방부터 실제 데이터만 출력
        print(self.heap[1:])

# 구현 테스트
print("----- 최소 힙 -----")

min_heap = MinHeap()

min_heap.insert(50)
min_heap.insert(30)
min_heap.insert(20)
min_heap.insert(10)
min_heap.insert(40)

min_heap.print_heap()

print("삭제:", min_heap.delete())
min_heap.print_heap()

print("삭제:", min_heap.delete())
min_heap.print_heap()

실행 결과 ▶