[자료구조] 힙(Heap)

241121

 

힙(Heap)

힙은 완전 이진트리 구조를 가지는 비선형 자료구조로, 특정한 정렬 조건(최대 힙 또는 최소 힙)을 만족한다.
이러한 힙이 사용되는 곳은 그래프 알고리즘을 구현해 네트워크 경로 최적화, 지도의 최단 경로 계산 등에 사용되기도 하고, 데이터 스트림 처리를 구현해 주식, 실시간 센서 데이터 분석에도 사용된다.

 

힙(Heap)의 특징

• 완전 이진트리: 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 채워짐.
• 정렬 조건:
  최대 힙: 부모 노드가 자식 노드보다 크거나 같음.
  최소 힙: 부모 노드가 자식 노드보다 작거나 같음.
• 효율적인 연산: 삽입과 삭제 연산은 O(log n) 시간 복잡도를 가짐.

 

힙(Heap)의 장단점

 

장점

• 우선순위 큐 구현에 적합하다.
• 최대/최솟값을 빠르게 찾을 수 있다.
• 동적 데이터 관리에 유리하다.

 

단점

• 상대적으로 임의접근이 비효율적이다.

 

 

파이썬을 이용한 힙(Heap) 코드 예시

#최소 힙을 구현하며, 최대 힙을 사용하고 싶다면 음수 값을 사용하여 변환할 수 있다.

import heapq

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

# 요소 추가
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)

# 최소값 추출
min_val = heapq.heappop(heap)  # 1
print(min_val)

# 현재 힙의 상태
print(heap)  # [3, 5, 8]

# 여러 요소를 한 번에 추가
heapq.heappush(heap, 4)
heapq.heappop(heap)  # 최소값 제거
heapq.heapify(heap)  # 리스트를 힙으로 변환