Algorithm Guidecomplexity: 삽입/삭제 O(log n)

힙 (Heap)

부모가 항상 자식보다 작은(최소 힙) 완전 이진 트리로, 배열로 구현됩니다. 루트가 항상 최솟값이라 우선순위 큐의 표준 구현이며, 다익스트라·힙 정렬의 핵심입니다.

01힙 (Heap)

알고리즘 작동 원리 탐색

최소 힙. 부모가 항상 자식보다 작은 완전 이진 트리로, 루트에 늘 최솟값이 옵니다.

push(3) · 맨 끝에 3을 추가하고, 부모 8과 비교합니다. 3 < 8이므로 위로 올라가야 합니다.

3과 8을 교환합니다. 3이 루트로 올라가 최솟값 자리를 차지합니다.

push(5) · 맨 끝에 5를 추가하고 부모 3과 비교합니다. 5 > 3이므로 그대로 멈춥니다.

push(1) · 맨 끝에 1을 추가하고 부모 8과 비교합니다. 1 < 8이므로 위로 올라갑니다.

1과 8을 교환한 뒤, 다시 부모 3과 비교합니다. 1 < 3이므로 한 번 더 올라갑니다.

1과 3을 교환합니다. 1이 루트까지 올라왔습니다.

완료 · 루트가 항상 최솟값(1)입니다. 우선순위 큐는 이 성질로 '가장 급한 것'을 O(log n)에 꺼냅니다.

Live Python

1def heappush(heap, val):

2 heap.append(val) # 맨 끝에 추가

3 i = len(heap) - 1

4 while i > 0:

5 parent = (i - 1) // 2

6 if heap[i] < heap[parent]:

7 heap[i], heap[parent] = heap[parent], heap[i]

8 i = parent # 위로 한 칸

9 else:

10 break # 제자리

1 / 8

02 쉽게 이해하기

For Everyone

🔑핵심 동작

부모가 자식보다 늘 크거나 같습니다. 전체를 정렬하지 않고도 가장 큰 값을 꼭대기에서 바로 꺼냅니다.

💡쉽게 말하면

부모가 늘 자식보다 작은(또는 큰) 나무 모양입니다.

맨 위가 항상 최솟값이라 '최우선 항목'을 즉시 꺼낼 수 있어요.

📍어디에 쓰나

–우선순위 큐
–급한 작업 먼저 처리
–다익스트라 최단 경로
–힙 정렬

03 파이썬 구현 코드

힙 (Heap)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 8)

smallest = heapq.heappop(heap)  # 1

# 배열을 한 번에 힙으로 (O(n))
data = [5, 1, 8, 3, 2]
heapq.heapify(data)

04 자주 묻는 질문

FAQ

힙 (Heap)란 무엇인가요?+

힙 (Heap)의 시간복잡도는 어떻게 되나요?+

힙 (Heap)의 시간복잡도는 삽입/삭제 O(log n) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

힙 (Heap)은(는) 어디에 사용하나요?+

우선순위 큐, 급한 작업 먼저 처리, 다익스트라 최단 경로, 힙 정렬.

힙 (Heap)를 쉽게 비유하면?+

부모가 자식보다 늘 크거나 같습니다. 전체를 정렬하지 않고도 가장 큰 값을 꼭대기에서 바로 꺼냅니다.

📦연결 리스트 (Linked List)