[알고리즘] Heap 구조

힙(Heap)이란?

힙(Heap)은 완전 이진 트리(Complete Binary Tree) 기반의 자료구조로, 최댓값 또는 최솟값을 빠르게 찾고 유지하는 데 최적화된 구조이다.

 

힙의 특징

1. 완전 이진 트리(Complete Binary Tree)

• 왼쪽부터 차례대로 채워지는 이진 트리
• 높이가 최소화되어서 연산 속도가 빠름

2. 힙 속성(Heap Property)

• 최소 힙(Min-Heap): 부모 노드가 자식 노드보다 항상 작음 → heap[0]이 최소값
• 최대 힙(Max-Heap): 부모 노드가 자식 노드보다 항상 큼 → heap[0]이 최대값
• 이 속성 덕분에 최솟값 또는 최댓값을 O(1)에 찾을 수 있다.

3. 탐색보다 삽입/삭제가 빠름

• 일반적인 트리나 리스트는 정렬을 해야 하지만 힙은 O(logN)만에 삽입/삭제 가능
• 다익스트라, 프림 알고리즘 등에서 필수적으로 사용됨

 

힙의 구조

1. 최소 힙(Min Heap)

       1
      / \
     3   5
    / \  / \
   7  9 8  10

• 부모 ≤ 자식 (최소값이 루트)
• heap[0] = 1 (항상 최소값)
  
  

2. 최대 힙(Max Heap)

       10
      /  \
     8    5
    / \  / \
   7   9 3  1

• 부모 ≥ 자식 (최대값이 루트)
• heap[0] = 10 (항상 최대값)

 

힙의 각 연산에 따른 시간 복잡도

삽입 (Insert)	O(logN)
삭제 (Extract Min/Max)	O(logN)
최솟값/최댓값 조회	O(1)
정렬된 요소 추출	O(N logN)

 

Python에서 힙(Heap) 사용법

1. heapq 모듈 (기본적으로 최소 힙)

heapq를 사용하려면 리스트를 힙처럼 다루어야 한다.heapq는 기본적으로 최소 힙을 제공하므로 최솟값이 먼저 나온다.

import heapq

# 빈 리스트를 힙으로 사용
heap = []

# 요소 추가 (heappush)
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 2)

print(heap)  # [1, 2, 4, 3] (내부 구조: 항상 최소값이 루트)

# new heap
heap = []

heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)

print(heapq.heappop(heap))  # 1 (최소값 제거)
print(heapq.heappop(heap))  # 3
print(heapq.heappop(heap))  # 5

 

2. 우선순위가 가장 높은 요소(최소값) 꺼내기

min_value = heapq.heappop(heap)
print(min_value)  # 1 (가장 작은 값이 제거됨)
print(heap)       # [2, 3, 4] (힙이 다시 정렬됨)

 

3. 여러 개의 값을 한 번에 힙으로 만들기 (heapify)

이미 리스트가 존재할 때, heapify( )를 사용하면 한 번에 최소 힙으로 변환할 수 있다.

nums = [5, 3, 8, 1, 2]
heapq.heapify(nums)
print(nums)  # [1, 2, 8, 3, 5] (내부적으로 최소 힙 구조 유지)

        1
       / \
      2   8
     / \
    3   5

 

4. 최대 힙 만들기 (음수 활용)

Python의 heapq는 최소 힙만 지원하기 때문에 음수 값을 사용하면 최대 힙처럼 동작할 수 있다.

max_heap = []
heapq.heappush(max_heap, -3)  # 3을 음수로 변환하여 저장
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -4)
heapq.heappush(max_heap, -2)

print(-heapq.heappop(max_heap))  # 4 (가장 큰 값이 나옴)
print(-heapq.heappop(max_heap))  # 3

 

5. 우선순위가 있는 튜플 사용하기

튜플을 사용하면 우선순위가 낮은 순서대로 정렬된다.

tasks = []
heapq.heappush(tasks, (2, "write report"))  # 우선순위 2
heapq.heappush(tasks, (1, "fix bug"))       # 우선순위 1 (더 높음)
heapq.heappush(tasks, (3, "email client"))  # 우선순위 3

print(heapq.heappop(tasks))  # (1, 'fix bug')
print(heapq.heappop(tasks))  # (2, 'write report')

우선순위가 같은 경우, 입력 순서대로 처리된다.

 

6. nlargest()와 nsmallest()

최대값이나 최소값을 빠르게 구할 때 heapq.nlargest()와 heapq.nsmallest()를 사용할 수 있다.

nums = [5, 3, 8, 1, 2, 7]
print(heapq.nlargest(2, nums))  # [8, 7] (가장 큰 값 2개)
print(heapq.nsmallest(3, nums))  # [1, 2, 3] (가장 작은 값 3개)

 

 요약

• heapq는 기본적으로 최소 힙(min-heap)을 사용한다.
• heappush(), heappop()을 사용하여 요소를 추가/제거한다.
• heapify()를 사용하면 기존 리스트를 힙으로 변환할 수 있다.
• 최대 힙을 만들려면 음수를 활용한다.
• 튜플을 사용하면 (우선순위, 데이터) 형태로 정렬할 수 있다.
• nlargest()와 nsmallest()로 최댓값/최솟값을 빠르게 찾을 수 있다.

 

힙을 사용하는 대표적인 문제 유형

1. 최솟값/최댓값을 빠르게 찾는 문제

• 우선순위가 높은 작업을 먼저 처리하는 우선순위 큐
• heapq.heappop()으로 최솟값(또는 최댓값) 즉시 추출 가능

2. K번째 최소/최대값 찾기 (O(k logN))

• heapq.nlargest(k, arr) 또는 heapq.nsmallest(k, arr)

3. 다익스트라 최단 경로 알고리즘 (O((N + E) logN))

• 최단 거리를 우선순위 큐로 관리하여 효율적으로 탐색

4. 프림 알고리즘 (최소 신장 트리)

• 간선의 가중치를 기준으로 정렬하지 않고 O(logN)으로 최적의 선택 가능

 

힙(Heap)의 핵심 정리

완전 이진 트리	왼쪽부터 차곡차곡 채우는 구조
최소/최대 힙	부모 노드가 항상 자식보다 작거나 큼
삽입/삭제가 O(logN)	정렬 없이도 빠르게 데이터 유지
최솟값/최댓값 즉시 추출 (O(1))	heap[0]에 항상 최소/최대값이 위치
우선순위 큐로 활용	다익스트라, 작업 스케줄링, K번째 값 찾기에 사용

힙은 정렬 없이도 빠르게 우선순위를 관리할 수 있는 강력한 자료구조