힙 속성과 배열 표현
배열에 저장되는 완전 이진 트리 구조를 이해하고 부모·자식 인덱스 공식을 도출하며 sift-up과 sift-down 연산을 시각화합니다.
힙 속성과 배열 표현은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
힙이란 무엇인가
힙은 힙 속성을 만족하는 특수한 완전 이진 트리입니다. 최소 힙에서는 모든 parent가 자식보다 작거나 같고, 최대 힙에서는 모든 parent가 자식보다 크거나 같습니다. 이 속성은 최솟값 또는 최댓값 원소가 항상 루트에 있도록 보장하므로, 극값 원소에 O(1)로 접근할 수 있습니다. 힙은 우선순위 큐를 구현하는 자료 구조입니다.
# Min-heap example:
# 1
# / \
# 3 2
# / \ / \
# 7 4 5 6
# Every parent <= its children
# Root (1) is always the minimum
# Max-heap example:
# 9
# / \
# 7 8
# / \ / \
# 3 4 5 6
# Every parent >= its children
# Root (9) is always the maximum
print('Heap property: parent dominates all descendants')완전 이진 트리 구조
힙은 완전 이진 트리로 저장됩니다. 마지막 레벨을 제외한 모든 레벨은 완전히 채워져 있고, 마지막 레벨은 왼쪽에서 오른쪽으로 채워집니다. 이 구조 덕분에 낭비되는 공간이나 포인터 없이 우아한 배열 표현을 사용할 수 있습니다. 완전성으로 인해 힙의 높이는 항상 floor(log₂ n)이므로 push와 pop 연산이 O(log n)에 수행됩니다.
# Complete binary tree properties:
# 1. All levels filled except possibly the last
# 2. Last level filled from LEFT to right
# 3. For n nodes: height = floor(log2(n))
# NOT complete (last level not left-filled):
# 1
# / \
# 2 3
# \
# 4 <- right child without left sibling
# Valid complete binary tree with 4 nodes:
# 1
# / \
# 2 3
# /
# 4
print('Complete BT: height = floor(log2(n)) always')힙의 배열 표현
완전 이진 트리 구조 덕분에 힙을 포인터 없이 일반 배열에 저장할 수 있습니다. 인덱스 i(0부터 시작)에 있는 노드의 parent는 (i-1) // 2에 있고, 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2에 있습니다. 이러한 정수 연산은 포인터 탐색을 대신하며 힙을 캐시에 매우 친화적으로 만듭니다.
# Array representation (0-indexed):
# Index: 0 1 2 3 4 5 6
# Array: [1, 3, 2, 7, 4, 5, 6]
# Tree: 1 (index 0)
# / \
# 3 2 (indices 1, 2)
# / \ / \
# 7 4 5 6 (indices 3,4,5,6)
# Index formulas (0-based):
def parent(i): return (i - 1) // 2
def left_child(i): return 2 * i + 1
def right_child(i): return 2 * i + 2
heap = [1, 3, 2, 7, 4, 5, 6]
print('Parent of index 3:', parent(3), '-> value', heap[parent(3)])
print('Left child of 1:', left_child(1), '-> value', heap[left_child(1)])상향 조정: 삽입 후 힙 복원
상향 조정(bubble-up 또는 heapify-up이라고도 함)은 힙 배열의 끝에 새 원소를 삽입한 후 사용합니다. 새 원소를 parent와 비교하고, 힙 속성을 위반하면 두 원소를 교환한 뒤 위쪽으로 계속 이동합니다. 원소가 올바른 위치에 놓이거나 루트에 도달할 때까지 반복합니다. 트리의 높이가 O(log n)이므로 이 연산은 O(log n)에 수행됩니다.
def sift_up(heap, i):
while i > 0:
p = (i - 1) // 2 # parent index
if heap[p] > heap[i]: # min-heap: parent should be smaller
heap[p], heap[i] = heap[i], heap[p]
i = p
else:
break # heap property restored
# Demonstrate: insert 0 into an existing min-heap
heap = [1, 3, 2, 7, 4, 5, 6]
heap.append(0) # add at end
print('Before sift-up:', heap)
sift_up(heap, len(heap) - 1)
print('After sift-up:', heap) # 0 should bubble to root하향 조정: 삭제 후 힙 복원
하향 조정(heapify-down)은 루트를 제거한 후 사용합니다. 마지막 원소를 루트로 옮긴 다음, 더 작은 자식(최소 힙의 경우)과 반복해서 교환하며 아래로 이동시켜 힙 속성을 복원합니다. 이 연산 역시 O(log n)에 수행됩니다. 상향 조정과 하향 조정은 모든 힙 연산의 기본 구성 요소입니다.
def sift_down(heap, i, n):
while True:
smallest = i
l = 2 * i + 1 # left child
r = 2 * i + 2 # right child
if l < n and heap[l] < heap[smallest]:
smallest = l
if r < n and heap[r] < heap[smallest]:
smallest = r
if smallest == i:
break # already in correct position
heap[i], heap[smallest] = heap[smallest], heap[i]
i = smallest
heap = [1, 3, 2, 7, 4, 5, 6]
# Pop min: move last to root, then sift-down
heap[0] = heap[-1]
heap.pop()
print('After move last to root:', heap)
sift_down(heap, 0, len(heap))
print('After sift-down:', heap) # valid min-heap again배열에서 힙 만들기: Floyd 알고리즘
n개의 원소를 하나씩 순서대로 삽입하면 O(n log n)이 걸립니다. Floyd의 heapify 알고리즘은 마지막 비단말 노드(인덱스 n//2 - 1)에서 시작해 루트까지 거꾸로 이동하면서 모든 비단말 노드에 하향 조정을 적용하여 O(n)에 힙을 만듭니다. 리프 노드는 이미 그 자체로 유효한 힙이므로 내부 노드만 수정하면 됩니다. 따라서 전체 작업량은 O(n log n)이 아니라 O(n)의 합이 됩니다.
def build_heap(arr):
n = len(arr)
# Start from last non-leaf node: index n//2 - 1
for i in range(n // 2 - 1, -1, -1):
sift_down(arr, i, n)
return arr
arr = [5, 3, 8, 1, 9, 2, 7]
print('Before:', arr)
build_heap(arr)
print('After (min-heap):', arr) # root should be 1
# Why O(n)? Most nodes are near the bottom (leaves).
# Level k from bottom has ~n/2^k nodes, each needing
# at most k swaps. Sum = n * sum(k/2^k) = O(n).배열 힙을 사용한 힙 정렬
힙 정렬은 추가 공간 O(1)로 O(n log n)에 동작합니다. 1단계에서는 O(n)에 배열로부터 최대 힙을 만듭니다. 2단계에서는 정렬되지 않은 마지막 원소와 루트를 반복해서 교환한 다음, 크기가 줄어든 힙에 하향 조정을 적용하여 최댓값을 추출합니다. n번 추출하고 나면 배열이 오름차순으로 정렬됩니다. 이 제자리 알고리즘은 배열 표현을 이용하면 별도의 자료 구조를 할당하지 않고도 정렬할 수 있음을 보여 줍니다.
def sift_down_max(arr, i, n):
while True:
largest = i
l, r = 2*i+1, 2*i+2
if l < n and arr[l] > arr[largest]: largest = l
if r < n and arr[r] > arr[largest]: largest = r
if largest == i: break
arr[i], arr[largest] = arr[largest], arr[i]
i = largest
def heap_sort(arr):
n = len(arr)
# Build max-heap
for i in range(n // 2 - 1, -1, -1):
sift_down_max(arr, i, n)
# Extract elements one by one
for end in range(n - 1, 0, -1):
arr[0], arr[end] = arr[end], arr[0] # move max to end
sift_down_max(arr, 0, end)
arr = [5, 3, 8, 1, 9, 2, 7]
heap_sort(arr)
print(arr) # [1, 2, 3, 5, 7, 8, 9]최소 힙과 최대 힙 비교
최소 힙에서는 최솟값 원소가 루트에 있으므로 pop하면 항상 최솟값이 나옵니다. 최대 힙에서는 최댓값 원소가 루트에 있으므로 pop하면 항상 최댓값이 나옵니다. 두 힙은 구조와 연산이 동일하며 비교 방향만 다릅니다. Python의 heapq 모듈은 최소 힙만 구현하므로, 최대 힙을 흉내 내려면 값에 음수를 취해야 합니다.
import heapq
# Python heapq is a MIN-HEAP
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
print('Min-heap min:', heapq.heappop(min_heap)) # 1
# Simulate MAX-HEAP by negating values
max_heap = []
for val in [5, 1, 3]:
heapq.heappush(max_heap, -val) # negate on push
print('Max-heap max:', -heapq.heappop(max_heap)) # 5 (negate on pop)
# For tuples: heapq sorts by first element
print(min_heap, max_heap)힙 연산 복잡도 요약
모든 힙 연산은 상향 조정과 하향 조정에서 파생되며, 두 연산 모두 O(log n)입니다. 삽입: append + 상향 조정 = O(log n). 삭제: 루트와 마지막 원소 교환 + 하향 조정 = O(log n). 조회: 인덱스 0에 접근 = O(1). 힙 구성: Floyd 알고리즘을 통한 O(n). 힙 정렬: O(n log n). 이러한 복잡도 덕분에 힙은 동적으로 변하는 자료 모음에서 최솟값이나 최댓값을 반복해서 구해야 할 때 이상적인 구조입니다.
# Heap complexity summary:
# Operation | Time | Space
# --------------|------------|-------
# Push | O(log n) | O(1)
# Pop (min/max) | O(log n) | O(1)
# Peek | O(1) | O(1)
# Build from n | O(n) | O(1) in-place
# Heap sort | O(n log n) | O(1)
# nlargest(k,n) | O(n log k) | O(k)
import heapq
data = [5, 3, 8, 1, 9, 2, 7]
print('Top 3 largest:', heapq.nlargest(3, data)) # [9, 8, 7]
print('Top 3 smallest:', heapq.nsmallest(3, data)) # [1, 2, 3]면접에서 사용하는 실용적인 힙 패턴
힙은 공통된 패턴을 사용하는 일련의 면접 문제를 해결합니다. n개의 원소를 순차적으로 처리하는 동안 k개의 후보로 이루어진 우선순위 큐를 유지하는 방식입니다. 빈도가 높은 상위 k개 원소, 원점에 가장 가까운 k개 점, 작업 스케줄러가 모두 이 패턴을 사용합니다. "n개 항목의 입력이 주어질 때 가장 좋은 k개를 유지하라"는 유형을 보면 이 패턴을 알아보세요. 항상 크기 k인 힙이 필요하며 총 O(n log k) time이 걸립니다.
import heapq
# Top-K closest points to origin using a max-heap of size k
def k_closest(points, k):
# Use max-heap (negate distance) of size k
heap = []
for x, y in points:
dist = -(x*x + y*y) # negate for max-heap
heapq.heappush(heap, (dist, x, y))
if len(heap) > k:
heapq.heappop(heap) # remove farthest
return [[x, y] for _, x, y in heap]
points = [[1,3], [-2,2], [5,8], [0,1]]
print(k_closest(points, 2)) # 2 closest to origin힙과 정렬된 배열의 장단점
최솟값이나 최댓값에 반복해서 접근하기만 하면 되고 자료 모음이 동적으로 변경될 때는 힙을 선택합니다. 인덱스로 임의 접근하거나 범위 검색을 해야 할 때는 정렬된 배열을 선택합니다. 힙의 약점은 임의 원소를 검색하는 데 O(n)이 걸린다는 것이고, 강점은 삽입/삭제가 O(log n), 최솟값/최댓값 접근이 O(1)이라는 것입니다. 정렬된 배열은 삽입에 O(n)이 걸리지만 이진 탐색을 사용하면 검색에 O(log n)이 걸립니다.
# Trade-off comparison:
# Structure | insert | delete_min | search | range_query
# --------------|---------|------------|--------|------------
# Min-heap | O(logn) | O(logn) | O(n) | O(n)
# Sorted array | O(n) | O(n) | O(logn)| O(logn+k)
# BST (balanced)| O(logn) | O(logn) | O(logn)| O(logn+k)
# Hash map | O(1) | O(1) | O(1) | O(n)
# Interview heuristic:
# 'Find minimum repeatedly from dynamic collection' -> HEAP
# 'Binary search or range query' -> sorted array or BST
# 'Fast lookup by key' -> hash map
print('Heap = dynamic collection with priority access')빠른 확인
이 단원에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보세요.
단원 복습
이 단원에서는 힙 속성과 완전 이진 트리 구조, parent/자식 인덱스 공식이 포함된 배열 표현, 그리고 Floyd의 O(n) 구성과 모든 힙 연산의 기본 구성 요소인 상향 조정과 하향 조정을 배웠습니다. 다음으로 heapify를 구현하고 Python의 heapq 모듈을 살펴보겠습니다.
자주 묻는 질문
“힙 속성과 배열 표현” 강의는 무료인가요?
네 — “힙 속성과 배열 표현” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“힙 속성과 배열 표현”에서 뭘 배우나요?
배열에 저장되는 완전 이진 트리 구조를 이해하고 부모·자식 인덱스 공식을 도출하며 sift-up과 sift-down 연산을 시각화합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“힙 속성과 배열 표현” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.