2025-07-30 22:13

Status:

Tags:자료구조 알고리즘

힙

• 최댓값, 최솟값을 빠르게 찾기 위한 자료구조
• 힙 자료구조 자체가 사실상 힙정렬 그 자체. 만들면 그냥 바로 루트에 최대나 최소값 나오니까
• 삽입 삭제 모두 O(log n)

구조

• 완전 이진트리
• 맥스 힙이면 부모가 자식보다 크고, 민 힙이면 반대
• 트리 구조를 배열로 표현

주요 연산

연산	설명	시간복잡도
힙 생성	주어진 배열을 힙 구조로 변환 (heapify)	$O(n)$
삽입(insert)	배열 끝에 요소 추가 후 “up-heap” (또는 sift-up)으로 속성 복원	$O(\log n)$
삭제(extract)	루트 요소 교체 및 “down-heap”(sift-down)으로 힙 속성 복원	$O(\log n)$
최대/최소 조회	getMax()/getMin()로 루트 요소 반환	$O(1)$

파이썬 코드

7. 예제 코드 (Python)

진짜 파이썬에서 쓸때는 파이썬에서 힙 사용법 핸드북 heapq 쓰면 된다.

References

큐 트리 이진트리 힙(Heap) 자료구조 핸드북 파이썬에서 힙 사용법 핸드북