Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Tags
- docker
- 오블완
- nginx
- 쿠키(cookie)
- django
- redis
- web
- Python
- 아티클 스터디
- 파이썬
- Wil
- viewsets
- github
- 장고
- 티스토리챌린지
- 코딩테스트
- JWT
- 도커
- Til
- NoSQL
- Doker
- CS
- 개발공부
- SQL
- git
- flask
- 세션(Session)
- ERD
- 연습
- 자료구조
Archives
- Today
- Total
SteadyDrills
[자료구조] 힙(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) # 리스트를 힙으로 변환
'알고리즘 & 자료구조' 카테고리의 다른 글
[자료구조] 데큐 (Deque) (0) | 2024.11.15 |
---|---|
[자료구조] 큐 (Queue) (0) | 2024.11.14 |
[자료구조] 비선형 구조 - 트리(Tree) (0) | 2024.07.26 |
[TIL] Stack 자료구조 & Node (0) | 2024.07.15 |