SteadyDrills

[자료구조] 힙(Heap) 본문

알고리즘 & 자료구조

[자료구조] 힙(Heap)

Drills 2024. 11. 21. 23:57

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)  # 리스트를 힙으로 변환

 

'알고리즘 & 자료구조' 카테고리의 다른 글

[자료구조] 데큐 (Deque)  (0) 2024.11.15
[자료구조] 큐 (Queue)  (0) 2024.11.14
[자료구조] 비선형 구조 - 트리(Tree)  (0) 2024.07.26
[TIL] Stack 자료구조 & Node  (0) 2024.07.15