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

힙 (Heap)

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

01 Explore How It Works

Interactive Step-by-Step

HOVER OR SCROLL

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 Understand It Simply

For Everyone

🔑Analogy

'가장 급한 일이 항상 맨 위'로 정리되는 응급실 대기 명단.

💡In Plain Words

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

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

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 힙 (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 Frequently Asked Questions

FAQ

What is 힙 (Heap)?+

What is the time complexity of 힙 (Heap)?+

The time complexity of 힙 (Heap) is 삽입/삭제 O(log n). Follow the step-by-step visualization to see exactly why.

Where is 힙 (Heap) used?+

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

What's a simple analogy for 힙 (Heap)?+

'가장 급한 일이 항상 맨 위'로 정리되는 응급실 대기 명단.

→ Data Structures — see allRelated

📦연결 리스트 (Linked List)

Guide Progress0%