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

힙 (Heap)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

Min-Heap · sift-up

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

Logic Node1 / 8

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 # 제자리

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)

Guide Progress0%