[과제 7] 힙(Heap)

송정근·2026년 6월 8일
python

랭체인 AI 영상객체탐지분석 플랫폼 구축

목록 보기
32/113
post-thumbnail

힙(Heap) 은 우선순위가 높은 데이터를 빠르게 꺼내기 위해 사용하는 자료구조이다.

일반적으로 완전 이진트리 (Complete Binary Tree) 구조를 기반으로 하며, 부모 노드와 자식 노드 사이에 일정한 우선순위 규칙을 가진다.

힙은 대표적으로 다음 상황에서 사용한다.

  • 가장 큰 값 또는 가장 작은 값을 빠르게 꺼낼 때
  • 우선순위 큐 (Priority Queue) 를 구현할 때
  • 힙 정렬 (Heap Sort) 를 구현할 때
  • 작업 스케쥴링, 다익스트라 알고리즘 같은 우선순위 기반 알고리즘에서 사용할 때

1. 힙이란?

힙은 부모 노드가 자식 노드보다 우선순위가 높도록 유지되는 완전 이진 트리 기반 자료구조이다.

여기서 우선순위는 구현 방식에 따라 달라진다.

  • 최대 힙(Max Heap) : 큰 값이 더 높은 우선순위를 가진다.
  • 최소 힙(Min Heap) : 작은 값이 더 높은 우선순위를 가진다.

힙에서 가장 중요한 특징은 루트 노드에 항상 우선순위가 가장 높은 값이 위치한다는 점이다.

최대 힙 : 루트에 가장 큰 값
최소 힙 : 루트에 가장 작은 값

2. 완전 이진 트리와 힙의 관계

힙은 완전 이진 트리 형태를 유지한다.

완전 이진 트리 (Complete Binary Tree) 는 마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워지는 이진 트리이다.

완전 이진 트리 예시

        10
      /    \
     8      7
    / \    /
   5   3  2

힙은 항상 완전 이진 트리 형태를 유지해야 한다.

그래서 삽입할 때는 항상 마지막 위치의 다음 자리, 즉 왼쪽부터 차례대로 새 노드를 넣는다.

3. 최대 힙과 최소 힙

3.1 최대 힙 (Max Heap)

최대 힙은 부모 노드의 값이 자식 노드의 값보다 크거나 같은 힙이다.

        50
      /    \
     30     40
    / \    /
   10 20  35

가장 큰 값은 항상 루트 노드에 있다.

최대 힙의 루트 = 전체 데이터 중 최댓값

3.2 최소 힙 (Min Heap)

최소 힙은 부모 노드의 값이 자식 노드의 값보다 작거나 같은 힙이다.

 				10
      /    \
     20     15
    / \    /
   40 30  25

가장 작은 값은 항상 루트 노드에 있다.

최소 힙의 루트 = 전체 데이터 중 최솟값

3.3 최대 힙과 최소 힙 비교

구분최대 힙최소 힙
루트 노드가장 큰 값가장 작은 값
부모-자식 관계부모 >= 자식부모 <= 자식
사용 예높은 점수 먼저 처리낮은 비용 먼저 처리
대표 활용최대값 빠른 추출최소값 빠른 추출

4. 힙의 특징

힙은 다음 특징을 가진다.

  1. 완전 이진 트리 구조이다.
  2. 루트 노드에 우선순위가 가장 높은 값이 있다.
  3. 부모와 자식 사이에는 힙 조건이 유지된다.
  4. 같은 레벨의 노드끼리는 정렬되어 있지 않아도 된다.
  5. 보통 배열을 이용해 구현한다.

중요한 점은 힙이 전체적으로 정렬된 자료구조는 아니라는 것이다.

힙은 전체 정렬이 아니라 부모-자식 관계만 보장한다.

5. 부모 노드와 자식 노드의 관계

힙은 보통 배열로 구현한다.

완전 이진 트리는 빈 공간 없이 왼쪽부터 차례대로 채워지기 때문에 배열로 표현하기 좋다.

예 :

        50
      /    \
     30     40
    / \    /
   10 20  35

다음 트리를 배열로 표현하면 다음과 같다.

인덱스 :	0	 1	 2	 3	 4	 5 
값 	 : 50	30	40	10	20	35 
heap = [50, 30, 40, 10, 20, 35]

배열 인덱스는 아래 관계를 갖는다.

관계공식
부모 인덱스(현재 인덱스 - 1) // 2
왼쪽 자식 인덱스현재 인덱스 * 2 + 1
오른쪽 자식 인덱스현재 인덱스 * 2 + 2

6. 배열 기반으로 구현하는 이유

힙은 완전 이진 트리이기 때문에 배열로 구현하기 좋다.

포인터로 연결된 트리 구조를 사용하면 각 노드마다 왼쪽 자식, 오른쪽 자식 참조를 저장해야 한다.

하지만 배열로 구현하면 인덱스 계산만으로 부모와 자식 위치를 찾을 수 있다.

포인터 기반 트리: 
	node.left
	node.right
	node.parent

배열 기반 힙:
	parent = (index - 1) // 2
	left = index * 2 + 1
	right = index * 2 + 2

6.2 배열 기반 구현은 장점

  1. 구현이 간단하다.
  2. 메모리를 연속적으로 사용한다.
  3. 부모와 자식 인덱스를 계산으로 찾을 수 있다.
  4. 완전 이진 트리의 빈 공간이 거의 없어서 배열 낭비가 적다.

7. 일반 이진 트리와 힙의 차이점

구분일반 이진 트리힙
구조노드마다 최대 2개의 자식완전 이진 트리
값의 규칙특별한 규칙이 없을 수 있음부모-자식 우선순위 규칙이 있음
루트 의미특별한 의미가 없을 수 있음최댓값 또는 최솟값
구현 방식노드와 포인터 기반이 많음배열 기반이 많음
목적계층 구조 표현우선순위가 높은 값 빠르게 추출

힙은 이진 탐색 트리(BST) 와도 다르다.

BST 는 왼쪽 자식이 부모보다 작고, 오른쪽 자식이 부모보다 큰 구조를 유지한다.

힙은 왼쪽과 오른쪽의 대소 관계는 중요하지 않고, 부모와 자식 사이의 관계만 중요하다는 차이점이 있다.

8. 힙의 동작 과정

8.1 삽입(Insert)

힙에서 새로운 값을 삽입할 때는 다음 순서로 진행된다.

  1. 완전 이진 트리 구조를 유지하기 위해 배열의 마지막에 값을 추가한다.
  2. 부모 노드와 비교한다.
  3. 힙 조건을 만족하지 않으면 부모와 위치를 바꾼다.
  4. 힙 조건을 만족할 때까지 위로 올라간다.

이 과정을 Bubble Up, Up Heap, Heapify Up 이라고 부른다.

예 : 최대 힙에 45를 삽입

삽입 전:

        50
      /    \
     30     40
    / \
   10 20

배열: [50, 30, 40, 10, 20]

마지막 위치에 45를 추가한다.

        50
      /    \
     30     40
    / \    /
   10 20  45

배열: [50, 30, 40, 10, 20, 45]

45의 부모는 40이다. 최대 힙에서는 부모가 자식보다 커야 한다.

45 > 40

힙 조건이 깨졌으므로 두 값을 교환한다.

        50
      /    \
     30     45
    / \    /
   10 20  40

배열: [50, 30, 45, 10, 20, 40]

이제 45의 부모는 50이다.

45 < 50

최대 힙 조건을 만족하므로 삽입이 끝난다.

8.2 삭제(Delete) 와 루트 제거 과정

힙에서 삭제는 보통 루트 노드를 제거하는 것을 의미한다.

최대 힙에서는 최댓값을 제거하고, 최소 힙에서는 최솟값을 제거한다.

이 과정을 Bubble Down, Down Heap, Heapify Down 이라고 한다.

예시 : 최대 힙에서 루트 50 을 제거

제거할 값: 50

마지막 노드 40을 루트 자리로 올린다.

        40
      /    \
     30     45
    / \
   10 20

배열: [40, 30, 45, 10, 20]

최대 힙에서는 부모가 자식보다 커야 한다.
현재 40의 자식 중 더 큰 값은 45이다.

40 < 45

힙 조건이 깨졌으므로 40과 45를 교환한다.

        45
      /    \
     30     40
    / \
   10 20

배열: [45, 30, 40, 10, 20]

이제 힙 조건을 만족하므로 삭제가 끝난다.

8.3 Heapify

Heapify 는 힙 조건이 깨진 위치에서 다시 힙 조건을 만족하도록 정리하는 작업이다.

Heapify 는 크게 두 방향으로 나눌 수 있다.

종류사용 상황방향
Heapify Up삽입 후아래에서 위로
Heapify Down루트 삭제 후위에서 아래로

Heapify Up

새로운 값을 마지막에 넣은 뒤 부모와 비교하며 위로 올라간다.

새로운 값 삽입
    ↓
부모와 비교
    ↓
힙 조건이 깨졌으면 교환
    ↓
루트까지 반복

Heapify Down

루트를 삭제하고 마지막 값을 루트로 올린 뒤 자식과 비교하며 아래로 내려간다.

루트 제거
    ↓
마지막 값을 루트로 이동
    ↓
자식 중 우선순위가 높은 값과 비교
    ↓
힙 조건이 깨졌으면 교환
    ↓
리프 노드까지 반복

9. 시간 복잡도

힙의 높이는 log n 이다.

힙은 완전 이진 트리이므로 노드 개수가 늘어나도 높이는 천천히 증가한다.

9.1 삽입 시간 복잡도 : O(log n)

삽입은 마지막 위치에 값을 추가한 뒤, 부모와 비교하며 위로 올라간다.

최악의 경우 새로운 값이 루트까지 올라갈 수 있다.

힙의 높이가 log n 이므로 삽입 시간 복잡도는 O(log n) 이다.

9.2 삭제 시간 복잡도 : O(log n)

삭제는 루트를 제거하고 마지막 값을 루트로 올린 뒤, 자식과 비교하여 아래로 내려간다.

최악의 경우 루트에서 리프 노드까지 내려갈 수 있다.

힙의 높이가 log n 이므로 삭제 시간 복잡도는 O(log n) 이다.

9.3 탐색 시간 복잡도 : O(n)

힙의 최댓값 또는 최솟값을 루트에서 빠르게 찾을 수 있다.

하지만 특정 값이 힙 안에 있는지 찾는 일반 탐색은 빠르지 않다.

➡ 힙은 전체 정렬 구조가 아니기 때문.

따라서 특정 값을 찾으려면 최악의 경우 모든 노드를 확인해야 한다.

9.4 시간 복잡도 표

연산시간 복잡도이유
삽입O(log n)새 노드가 힙의 높이만큼 위로 올라갈 수 있음
삭제O(log n)루트로 올라온 값이 힙의 높이만큼 아래로 내려갈 수 있음
루트 조회O(1)루트는 배열의 0번 인덱스
일반 탐색O(n)전체 정렬이 아니므로 모든 노드를 볼 수 있음
print_heapO(n)모든 원소를 출력해야 함

10. 파이썬으로 직접 구현하기

힙은 배열을 사용해서 직접 구현할 수 있다.

배열의 0번 인덱스를 루트 노드로 사용하고, 부모와 자식 인덱스는 아래 공식으로 계산한다.

관계공식
부모 인덱스(현재 인덱스 - 1) // 2
왼쪽 자식 인덱스현재 인덱스 * 2 + 1
오른쪽 자식 인덱스현재 인덱스 * 2 + 2

직접 구현할 때 핵심은 두 가지이다.

  1. 값을 삽입한 뒤에는 heapify_up()으로 위로 올라가며 힙 조건을 맞춘다.
  2. 루트를 삭제한 뒤에는 heapify_down()으로 아래로 내려가며 힙 조건을 맞춘다.

10.1 최대 힙 수도 코드

최대 힙은 부모 노드가 자식 노드보다 크거나 같아야 한다.

MaxHeap
    heap 배열을 만든다.

insert(value)
    heap 마지막에 value를 추가한다.
    마지막 인덱스에서 heapify_up을 실행한다.

delete()
    heap이 비어 있으면 None을 반환한다.
    heap에 값이 하나만 있으면 그 값을 꺼내 반환한다.
    루트 값을 따로 저장한다.
    마지막 값을 루트 위치로 옮긴다.
    루트 인덱스에서 heapify_down을 실행한다.
    처음 저장해 둔 루트 값을 반환한다.

heapify_up(index)
    현재 노드가 루트가 아닐 동안 반복한다.
    부모 인덱스를 구한다.
    부모 값이 현재 값보다 크거나 같으면 중단한다.
    부모 값과 현재 값을 교환한다.
    현재 인덱스를 부모 인덱스로 바꾼다.

heapify_down(index)
    반복한다.
    왼쪽 자식, 오른쪽 자식 인덱스를 구한다.
    현재 노드, 왼쪽 자식, 오른쪽 자식 중 가장 큰 값의 인덱스를 찾는다.
    현재 노드가 가장 크면 중단한다.
    현재 노드와 가장 큰 자식 노드를 교환한다.
    현재 인덱스를 교환한 자식 인덱스로 바꾼다.

10.2 최대 힙 파이썬 구현

class MaxHeap:
    def __init__(self):
        # 힙 데이터를 저장할 리스트
        self.heap = []

    def insert(self, value):
        # 새 값을 완전 이진 트리의 마지막 위치에 추가
        self.heap.append(value)

        # 마지막에 추가한 값이 최대 힙 조건을 만족하도록 위로 이동
        self.heapify_up(len(self.heap) - 1)

    def delete(self):
        # 힙이 비어 있으면 꺼낼 값이 없으므로 None 반환
        if not self.heap:
            return None

        # 값이 하나만 있으면 그 값을 바로 꺼내 반환
        if len(self.heap) == 1:
            return self.heap.pop()

        # 루트에는 최대 힙에서 가장 큰 값이 들어 있다.
        root = self.heap[0]

        # 마지막 값을 루트 위치로 옮겨 완전 이진 트리 구조 유지
        self.heap[0] = self.heap.pop()

        # 루트로 올라온 값이 최대 힙 조건을 만족하도록 아래로 이동
        self.heapify_down(0)

        # 처음 저장해 둔 최댓값 반환
        return root

    def heapify_up(self, index):
        # 현재 노드가 루트가 될 때까지 반복
        while index > 0:
            # 부모 노드의 인덱스 계산
            parent_index = (index - 1) // 2

            # 부모가 현재 값보다 크거나 같으면 최대 힙 조건 만족
            if self.heap[parent_index] >= self.heap[index]:
                break

            # 부모보다 현재 값이 더 크면 두 값을 교환
            self.heap[parent_index], self.heap[index] = (
                self.heap[index],
                self.heap[parent_index],
            )

            # 교환 후 현재 위치를 부모 위치로 변경
            index = parent_index

    def heapify_down(self, index):
        # 힙의 전체 크기 저장
        size = len(self.heap)

        while True:
            # 왼쪽 자식과 오른쪽 자식의 인덱스 계산
            left_index = index * 2 + 1
            right_index = index * 2 + 2

            # 현재 노드를 가장 큰 값의 위치라고 가정
            largest_index = index

            # 왼쪽 자식이 존재하고 현재 가장 큰 값보다 크면 갱신
            if left_index < size and self.heap[left_index] > self.heap[largest_index]:
                largest_index = left_index

            # 오른쪽 자식이 존재하고 현재 가장 큰 값보다 크면 갱신
            if right_index < size and self.heap[right_index] > self.heap[largest_index]:
                largest_index = right_index

            # 현재 노드가 가장 크면 최대 힙 조건을 만족하므로 중단
            if largest_index == index:
                break

            # 현재 노드와 더 큰 자식 노드를 교환
            self.heap[index], self.heap[largest_index] = (
                self.heap[largest_index],
                self.heap[index],
            )

            # 교환한 자식 위치에서 다시 heapify_down 진행
            index = largest_index

    def print_heap(self):
        # 현재 힙 배열 출력
        print(self.heap)

10.3 최대 힙 실행 예시

max_heap = MaxHeap()

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

max_heap.print_heap()

print(max_heap.delete())
max_heap.print_heap()

결과 예시:

[50, 40, 30, 10, 20]
50
[40, 20, 30, 10]

최대 힙에서는 가장 큰 값이 루트에 있으므로 delete()를 실행하면 가장 큰 값이 먼저 제거된다.

10.4 최소 힙 수도 코드

최소 힙은 부모 노드가 자식 노드보다 작거나 같아야 한다.

최대 힙과 전체 구조는 거의 같지만, 비교 방향이 반대이다.

MinHeap
    heap 배열을 만든다.

insert(value)
    heap 마지막에 value를 추가한다.
    마지막 인덱스에서 heapify_up을 실행한다.

delete()
    heap이 비어 있으면 None을 반환한다.
    heap에 값이 하나만 있으면 그 값을 꺼내 반환한다.
    루트 값을 따로 저장한다.
    마지막 값을 루트 위치로 옮긴다.
    루트 인덱스에서 heapify_down을 실행한다.
    처음 저장해 둔 루트 값을 반환한다.

heapify_up(index)
    현재 노드가 루트가 아닐 동안 반복한다.
    부모 인덱스를 구한다.
    부모 값이 현재 값보다 작거나 같으면 중단한다.
    부모 값과 현재 값을 교환한다.
    현재 인덱스를 부모 인덱스로 바꾼다.

heapify_down(index)
    반복한다.
    왼쪽 자식, 오른쪽 자식 인덱스를 구한다.
    현재 노드, 왼쪽 자식, 오른쪽 자식 중 가장 작은 값의 인덱스를 찾는다.
    현재 노드가 가장 작으면 중단한다.
    현재 노드와 가장 작은 자식 노드를 교환한다.
    현재 인덱스를 교환한 자식 인덱스로 바꾼다.

10.5 최소 힙 파이썬 구현

class MinHeap:
    def __init__(self):
        # 힙 데이터를 저장할 리스트
        self.heap = []

    def insert(self, value):
        # 새 값을 완전 이진 트리의 마지막 위치에 추가
        self.heap.append(value)

        # 마지막에 추가한 값이 최소 힙 조건을 만족하도록 위로 이동
        self.heapify_up(len(self.heap) - 1)

    def delete(self):
        # 힙이 비어 있으면 꺼낼 값이 없으므로 None 반환
        if not self.heap:
            return None

        # 값이 하나만 있으면 그 값을 바로 꺼내 반환
        if len(self.heap) == 1:
            return self.heap.pop()

        # 루트에는 최소 힙에서 가장 작은 값이 들어 있다.
        root = self.heap[0]

        # 마지막 값을 루트 위치로 옮겨 완전 이진 트리 구조 유지
        self.heap[0] = self.heap.pop()

        # 루트로 올라온 값이 최소 힙 조건을 만족하도록 아래로 이동
        self.heapify_down(0)

        # 처음 저장해 둔 최솟값 반환
        return root

    def heapify_up(self, index):
        # 현재 노드가 루트가 될 때까지 반복
        while index > 0:
            # 부모 노드의 인덱스 계산
            parent_index = (index - 1) // 2

            # 부모가 현재 값보다 작거나 같으면 최소 힙 조건 만족
            if self.heap[parent_index] <= self.heap[index]:
                break

            # 부모보다 현재 값이 더 작으면 두 값을 교환
            self.heap[parent_index], self.heap[index] = (
                self.heap[index],
                self.heap[parent_index],
            )

            # 교환 후 현재 위치를 부모 위치로 변경
            index = parent_index

    def heapify_down(self, index):
        # 힙의 전체 크기 저장
        size = len(self.heap)

        while True:
            # 왼쪽 자식과 오른쪽 자식의 인덱스 계산
            left_index = index * 2 + 1
            right_index = index * 2 + 2

            # 현재 노드를 가장 작은 값의 위치라고 가정
            smallest_index = index

            # 왼쪽 자식이 존재하고 현재 가장 작은 값보다 작으면 갱신
            if left_index < size and self.heap[left_index] < self.heap[smallest_index]:
                smallest_index = left_index

            # 오른쪽 자식이 존재하고 현재 가장 작은 값보다 작으면 갱신
            if right_index < size and self.heap[right_index] < self.heap[smallest_index]:
                smallest_index = right_index

            # 현재 노드가 가장 작으면 최소 힙 조건을 만족하므로 중단
            if smallest_index == index:
                break

            # 현재 노드와 더 작은 자식 노드를 교환
            self.heap[index], self.heap[smallest_index] = (
                self.heap[smallest_index],
                self.heap[index],
            )

            # 교환한 자식 위치에서 다시 heapify_down 진행
            index = smallest_index

    def print_heap(self):
        # 현재 힙 배열 출력
        print(self.heap)

10.6 최소 힙 실행 예시

min_heap = MinHeap()

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

min_heap.print_heap()

print(min_heap.delete())
min_heap.print_heap()

결과 예시:

[10, 20, 50, 30, 40]
10
[20, 30, 50, 40]

최소 힙에서는 가장 작은 값이 루트에 있으므로 delete()를 실행하면 가장 작은 값이 먼저 제거된다.

11. 파이썬 내장 heapq

파이썬에는 힙을 쉽게 사용할 수 있는 heapq 모듈이 있다.

heapq 는 기본적으로 최소 힙으로 동작한다.

import heapq

heap = []

heapq.heappush(heap, 30)
heapq.heappush(heap, 10)
heapq.heappush(heap, 50)
heapq.heappush(heap, 20)

print(heap)

print(heapq.heappop(heap))
print(heap)

결과 :

[10, 20, 50, 30]
10
[20, 30, 50]

최대 힙처럼 사용하고 싶다면 음수로 값을 넣는 방법을 자주 사용한다.

import heapq

heap = []

heapq.heappush(heap, -30)
heapq.heappush(heap, -10)
heapq.heappush(heap, -50)

print(-heapq.heappop(heap))
print(-heapq.heappop(heap))

결과 : 

50
30

핵심 요약

개념설명
힙우선순위가 높은 값을 빠르게 꺼내기 위한 자료구조
완전 이진 트리마지막 레벨을 제외하고 꽉 차 있으며, 마지막 레벨은 왼쪽부터 채워지는 트리
최대 힙부모가 자식보다 크거나 같은 힙
최소 힙부모가 자식보다 작거나 같은 힙
배열 구현인덱스 계산으로 부모와 자식 위치를 찾을 수 있음
삽입마지막에 추가 후 위로 올리며 정렬
삭제루트 제거 후 마지막 값을 루트로 올리고 아래로 내리며 정렬
Heapify힙 조건을 다시 만족하도록 정리하는 과정

결론 :

힙은 완전 이진 트리 구조를 유지하면서, 루트에 항상 가장 우선순위가 높은 값을 두는 자료구조이다.

profile
송정근
기록하며 성장하는 개발자
이전 포스트

[13일차] Data Analysis

다음 포스트

[14일차] Data Analysis

0개의 댓글