[개념정리] 힙

힙이란?

완전 이진 트리 O
       1
     /   \\
    2     3
   / \\   /
  4   5 6

완전 이진 트리 O
       1
     /   \\
    2     3
   / \\   / \\
  4   5 6   7

완전 이진 트리 X
       1
     /   \\
    2     3
   /     / \\
  4     6   7
(5가 없어서 완전 이진 트리가 아님)

트리의 일종으로, 완전 이진 트리 형태의 자료구조입니다. 다음과 같은 특징을 가집니다.

• 피라미드처럼 생긴 트리 구조
• 부모 노드와 자식 노드 간의 특별한 규칙 존재
• 가장 크거나 작은 값을 빠르게 찾을 수 있음

완전 이진 트리

• 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있음
• 마지막 레벨의 노드들은 왼쪽부터 차례대로 채워져 있어야 함

 트리의 특징

• 노드 번호가 1부터 시작할 때:
  • 노드 i의 왼쪽 자식: 2i
  • 노드 i의 오른쪽 자식: 2i + 1
  • 노드 i의 부모: i/2 (정수 나눗셈)
• 노드 번호가 0부터 시작할 때:
  • 노드 i의 왼쪽 자식: 2i + 1
  • 노드 i의 오른쪽 자식: 2i + 2
  • 노드 i의 부모: (i-1)/2 (정수 나눗셈)

 

힙의 종류

힙의 종류는 크게 두 가지가 있습니다.

1. 최대 힙
   1. 부모 노드가 자식 노드보다 항상 크다
   2. 루트 노드가 가장 큰 값이 된다
2. 최소 힙
   1. 부모 노드가 자식 노드보다 항상 작다
   2. 루트 노드가 가장 작은 값이 된다

 

Python heapq 라이브러리

heapq는 파이썬에서 제공하는 이진 힙 알고리즘을 구현한 라이브러리입니다. 기본적으로 최소 힙을 제공하며, 우선순위 큐를 구현하는데 매우 효율적입니다.

기본적인 heapq 사용법은 다음과 같습니다.

import heapq

# 1. 빈 힙 생성
heap = []

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

# 3. 원소 제거 (가장 작은 값)
min_value = heapq.heappop(heap)  # 1 반환

# 4. 가장 작은 값 확인 (제거하지 않음)
peek = heap[0]  # 3 반환

# 5. 기존 리스트를 힙으로 변환
numbers = [4, 1, 7, 3]
heapq.heapify(numbers)  # 리스트를 힙으로 변환

 

heapq를 사용한 우선순위 큐의 시간 복잡도는 다음과 같습니다.

• 삽입: O(log n)
• 삭제: O(log n)
• 최소/최대값 확인: O(1)
• 힙 생성(heapify): O(n)

실제로 구현할 때 위 내용을 잘 알고있다면 시간 복잡도를 줄이는데 큰 도움이 될 것 같습니다ㅎㅎ

 

 

heapq를 사용할 때는 다음과 같은 점을 고려하여야 합니다.

• heapq는 기본적으로 최소 힙만 제공합니다. 최대 힙이 필요한 경우 값을 음수로 변환하는 방법을 사용해야 합니다.
• 힙의 모든 원소를 순회할 때는 정렬된 순서를 보장하지 않습니다. 정렬된 순서가 필요하다면 heappop을 반복적으로 호출해야 합니다.
• 인덱스로 직접 접근(heap[i])은 힙의 특성을 해칠 수 있으므로 주의해야 합니다.

 

최소 힙만 제공하는 heapq의 특성으로 다음과 같이 음수 변환을 활용하여 최대 힙을 구현할 수 있습니다.

import heapq

# 최대 힙 구현
max_heap = []
heapq.heappush(max_heap, -10)  # -10을 추가
heapq.heappush(max_heap, -5)  # -5 추가
heapq.heappush(max_heap, -7)  # -7 추가

# 최대값 확인 (음수 변환 복원)
max_value = -heapq.heappop(max_heap)  # 10 반환
print(max_value)

 

힙과 이진 탐색 트리 비교

힙은 부모-자식 간의 관계만 중요하고, 형제 노드 간의 크기는 관계가 없습니다. 또한 완전 이진 트리 형태를 반드시 만족해야 합니다.

 

하지만 이진 탐색 트리는 모든 노드 간의 관계가 중요하고, 완전 이진 트리일 필요가 없습니다.

모든 노드간의 관계가 중요하다는 것은 다음과 같은 조건을 만족해야함을 의미합니다.

• 왼쪽 서브트리의 모든 노드 < 현재 노드
• 오른쪽 서브트리의 모든 노드 > 현재 노드

 

특성	힙	이진 탐색 트리
정렬 순서	부모-자식 간 관계만 유지	전체 트리 정렬
최댓값/최솟값 접근	O(1)	O(log n)
데이터 삽입/삭제	O(log n)	O(log n)
순차 데이터 처리	지원하지 않음	중위 순회로 정렬된 데이터 제공

 

우선순위 큐와 힙의 관계

우선순위 큐는 추상적인 자료구조이고, 힙은 이를 구현하는 방법 중 하나입니다.

우선순위 큐는 다음과 같은 특징을 가집니다.

1. 각 원소가 우선 순위를 가짐
2. 높거나 낮은 우선순위의 원소가 먼저 처리됨

⇒ 힙은 이러한 우선순위 큐의 특성을 효율적으로 구현할 수 있는 자료 구조입니다.

 

실제 힙 활용 사례

• 작업 스케줄링
  • 프로세스 우선순위 관리
  • 이벤트 처리 시스템
• 네트워크 패킷 우선순위
  • QoS(Quality of Service) 구현
  • 네트워크 트래픽 관리
• 알고리즘
  • Dijkstra 알고리즘
  • Prim 알고리즘
  • 중간값 찾기
• 코테 유형
  • K번째 최소/최대값 찾기
  • 힙 정렬
  • 스트림 데이터 처리