DSA Interview Prep · 강의

힙화, 삽입, 삭제를 처음부터 구현

Q: “힙화, 삽입, 삭제를 처음부터 구현” 강의는 무료인가요?

네 — “힙화, 삽입, 삭제를 처음부터 구현” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

Q: DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.

Q: “힙화, 삽입, 삭제를 처음부터 구현” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

Q: 이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

삽입을 위한 위로 힙화와 삭제를 위한 아래로 힙화를 구현한 뒤, Floyd 알고리즘으로 정렬되지 않은 배열을 O(n)에 힙으로 만듭니다.

레슨 2/413개 단계

힙화, 삽입, 삭제를 처음부터 구현은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

MinHeap 클래스 구축

힙을 처음부터 구현하면 내부 작동 원리를 완전히 이해할 수 있으며, 시니어 면접에서 가끔 요구되기도 합니다. MinHeap 클래스는 배열을 감싸고 push, pop, peek, size 연산을 제공합니다. 내부적으로 push 후에는 상향 조정을, pop 후에는 하향 조정을 호출하여 힙 속성을 유지합니다. 이 구현을 이해하면 Python의 heapq 모듈이 완전히 투명하게 느껴집니다.

class MinHeap:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)
        self._sift_up(len(self._data) - 1)

    def pop(self):
        if len(self._data) == 1:
            return self._data.pop()
        min_val = self._data[0]
        self._data[0] = self._data.pop()  # move last to root
        self._sift_down(0)
        return min_val

    def peek(self):
        return self._data[0] if self._data else None

    def size(self):
        return len(self._data)

    def _parent(self, i): return (i - 1) // 2
    def _left(self, i):   return 2 * i + 1
    def _right(self, i):  return 2 * i + 2

print('MinHeap class skeleton defined')

상향 조정 구현

상향 조정은 힙 속성(최소 힙에서는 parent <= 자식)을 위반하는 동안 노드를 parent와 비교하고 위쪽으로 교환합니다. 핵심은 새로 삽입된 원소가 끝에 있으며 올바른 위치까지 위로 이동한다는 점입니다. while 반복문은 트리의 높이인 floor(log n)번 이하로 실행됩니다. 각 단계에서 i = parent를 대입하여 계속 위로 이동합니다.

class MinHeap:
    def __init__(self):
        self._data = []

    def _parent(self, i): return (i - 1) // 2
    def _left(self, i):   return 2 * i + 1
    def _right(self, i):  return 2 * i + 2

    def _sift_up(self, i):
        while i > 0:
            p = self._parent(i)
            if self._data[p] > self._data[i]:  # parent > child: swap
                self._data[p], self._data[i] = self._data[i], self._data[p]
                i = p
            else:
                break  # heap property satisfied

    def push(self, val):
        self._data.append(val)
        self._sift_up(len(self._data) - 1)

h = MinHeap()
for v in [5, 3, 8, 1, 4]:
    h.push(v)
print(h._data)  # valid min-heap

하향 조정 구현

하향 조정은 노드를 가장 작은 자식(최소 힙의 경우)과 반복해서 교환하며 아래로 이동시킵니다. 두 자식 중 어느 쪽도 더 작지 않거나 노드가 리프에 도달할 때까지 계속합니다. 힙 속성을 유지하려면 항상 두 자식을 모두 비교하고 더 작은 자식과 교환해야 합니다. 값을 비교하기 전에 자식 인덱스가 유효한 범위 안에 있는지도 확인해야 합니다.

def _sift_down(data, i):
    n = len(data)
    while True:
        smallest = i
        l = 2 * i + 1
        r = 2 * i + 2
        if l < n and data[l] < data[smallest]:
            smallest = l
        if r < n and data[r] < data[smallest]:
            smallest = r
        if smallest == i:
            break  # already the smallest among i, l, r
        data[i], data[smallest] = data[smallest], data[i]
        i = smallest

# Test: put a large value at root and sift down
heap = [10, 1, 2, 3, 4, 5, 6]
print('Before sift-down:', heap)
_sift_down(heap, 0)
print('After sift-down:', heap)  # 1 should reach top, 10 sink

pop을 포함한 완전한 MinHeap

pop 연산은 루트(최소 힙에서는 최솟값)를 제거하고 반환합니다. 완전 이진 트리 형태를 유지하려면 마지막 원소를 루트 위치로 옮긴 다음 하향 조정을 적용합니다. 이렇게 하면 배열에 빈칸이 생기지 않고 표현이 유효하게 유지됩니다. 예외 경우: 원소가 하나만 남았다면 하향 조정 없이 바로 pop하여 반환합니다.

class MinHeap:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)
        i = len(self._data) - 1
        while i > 0:
            p = (i - 1) // 2
            if self._data[p] > self._data[i]:
                self._data[p], self._data[i] = self._data[i], self._data[p]
                i = p
            else: break

    def pop(self):
        if not self._data: return None
        if len(self._data) == 1: return self._data.pop()
        result = self._data[0]
        self._data[0] = self._data.pop()  # last -> root
        i, n = 0, len(self._data)
        while True:
            s, l, r = i, 2*i+1, 2*i+2
            if l < n and self._data[l] < self._data[s]: s = l
            if r < n and self._data[r] < self._data[s]: s = r
            if s == i: break
            self._data[i], self._data[s] = self._data[s], self._data[i]
            i = s
        return result

h = MinHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)])  # [1,2,3,4,5,8] sorted

Floyd의 heapify 알고리즘

Floyd 알고리즘은 마지막 내부 노드(n//2 - 1)에서 시작해 루트 방향으로 이동하면서 모든 비리프 노드에 하향 조정을 호출하여 정렬되지 않은 배열로부터 O(n)에 최소 힙을 만듭니다. 리프는 이미 원소 하나로 이루어진 유효한 힙입니다. O(n) time이 걸리는 이유는 대부분의 노드가 트리의 아래쪽에 있어 짧은 거리만 하향 조정하면 되기 때문입니다.

def heapify(arr):
    n = len(arr)
    # Start from last non-leaf: index n//2 - 1
    # Work backward to root (index 0)
    for i in range(n // 2 - 1, -1, -1):
        # Sift down node at index i
        j = i
        while True:
            s = j
            l, r = 2*j+1, 2*j+2
            if l < n and arr[l] < arr[s]: s = l
            if r < n and arr[r] < arr[s]: s = r
            if s == j: break
            arr[j], arr[s] = arr[s], arr[j]
            j = s
    return arr

arr = [9, 7, 5, 3, 1, 8, 2, 4, 6]
print('Before:', arr)
heapify(arr)
print('After (min-heap):', arr)  # arr[0] should be 1

Floyd 알고리즘이 O(n)인 이유

O(n)의 증명은 다음과 같습니다. 트리에는 높이 k에 n/2^(k+1)개의 노드가 있습니다. 높이 k의 각 노드는 하향 조정 중 최대 k번 교환합니다. 전체 작업량은 모든 높이 k에 대한 합인 n/2^(k+1) * k입니다. 이 등비급수는 O(n)에 수렴합니다. 순진한 일대일 삽입과 비교해 보세요. 각 push가 O(log n)이므로 n번의 push에는 O(n log n)이 걸립니다. 따라서 Floyd 알고리즘은 일괄 구성에 엄밀히 더 효율적입니다.

import time
import random

# Compare: O(n) heapify vs O(n log n) one-by-one
n = 100000
data = list(range(n, 0, -1))  # reverse sorted = worst case for push

# Method 1: Floyd's O(n)
data1 = data[:]
start = time.time()
for i in range(n // 2 - 1, -1, -1):
    j = i
    while True:
        s = j; l, r = 2*j+1, 2*j+2
        if l < n and data1[l] < data1[s]: s = l
        if r < n and data1[r] < data1[s]: s = r
        if s == j: break
        data1[j], data1[s] = data1[s], data1[j]; j = s
print(f'Floyd heapify: {time.time()-start:.4f}s')

# Method 2: One-by-one insertion
import heapq
start = time.time()
heap = []
for x in data: heapq.heappush(heap, x)
print(f'Push one-by-one: {time.time()-start:.4f}s')

기존 자료 모음에 힙 삽입

Python의 heapq.heappushpop과 heapq.heapreplace는 효율적인 결합 연산입니다. heappushpop(heap, item)은 새 항목을 삽입한 직후 최솟값을 삭제하므로, 두 번의 호출을 따로 수행하는 것보다 효율적입니다. heapreplace(heap, item)은 한 번의 과정으로 최솟값을 삭제하고 새 항목을 삽입합니다(정확하게 동작하려면 새 항목이 기존 최솟값 이상이어야 합니다). 이러한 연산은 상위 k개를 유지하는 스트리밍 알고리즘에 유용합니다.

import heapq

heap = [1, 3, 5, 7, 9]
heapq.heapify(heap)

# heappushpop: push 2, then pop minimum
# More efficient than push + pop separately
result = heapq.heappushpop(heap, 2)
print('heappushpop(2):', result, '| heap:', heap)

# heapreplace: pop minimum, then push new item
# New item does NOT need to be larger (different from heappushpop)
result2 = heapq.heapreplace(heap, 4)
print('heapreplace(4):', result2, '| heap:', heap)

# Use case: maintaining a fixed-size top-k heap
# heappushpop is the standard pattern

처음부터 MaxHeap 구현

MaxHeap은 비교 방향을 뒤집습니다. parent는 모든 자손보다 크거나 같아야 합니다. 상향 조정과 하향 조정에서 비교만 반대로 바꾸면 됩니다. 또는 값을 부호 반전 클래스에 감싸거나 Python의 heapq에서처럼 정수에 음수를 취할 수 있습니다. 처음부터 구현해 보면 최소 힙과 최대 힙은 비교 연산자만 다를 뿐 구조는 동일하다는 사실을 확인할 수 있습니다.

class MaxHeap:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)
        i = len(self._data) - 1
        while i > 0:
            p = (i - 1) // 2
            if self._data[p] < self._data[i]:  # FLIP: parent < child = violation
                self._data[p], self._data[i] = self._data[i], self._data[p]
                i = p
            else: break

    def pop(self):
        if not self._data: return None
        if len(self._data) == 1: return self._data.pop()
        result = self._data[0]
        self._data[0] = self._data.pop()
        i, n = 0, len(self._data)
        while True:
            g = i; l, r = 2*i+1, 2*i+2
            if l < n and self._data[l] > self._data[g]: g = l  # FLIP
            if r < n and self._data[r] > self._data[g]: g = r  # FLIP
            if g == i: break
            self._data[i], self._data[g] = self._data[g], self._data[i]; i = g
        return result

h = MaxHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)])  # [8,5,4,3,2,1]

힙에서 임의의 원소 삭제

힙에서 임의의 원소(루트가 아닌 원소)를 삭제하는 작업은 O(log n)이지만 해당 원소의 인덱스를 알고 있어야 합니다. 원소를 마지막 원소로 바꾸고 마지막 원소를 제거한 다음, 대체된 원소를 상향 조정하거나 하향 조정합니다. 힙 속성을 위반하는 방향은 한쪽뿐입니다. 이 기법은 지연 삭제를 사용하는 Dijkstra 알고리즘과 키 감소 연산을 지원하는 우선순위 큐에서 사용됩니다.

def delete_at_index(heap, i):
    n = len(heap)
    heap[i] = heap[n - 1]
    heap.pop()
    if i >= len(heap):
        return  # deleted the last element
    # Try sift-up first
    p = (i - 1) // 2
    if i > 0 and heap[i] < heap[p]:
        while i > 0:
            p = (i - 1) // 2
            if heap[p] > heap[i]:
                heap[p], heap[i] = heap[i], heap[p]; i = p
            else: break
    else:  # sift down
        j = i; n2 = len(heap)
        while True:
            s = j; l, r = 2*j+1, 2*j+2
            if l < n2 and heap[l] < heap[s]: s = l
            if r < n2 and heap[r] < heap[s]: s = r
            if s == j: break
            heap[j], heap[s] = heap[s], heap[j]; j = s

heap = [1, 3, 2, 7, 4, 5, 6]
print('Before:', heap)
delete_at_index(heap, 2)  # delete element at index 2 (value=2)
print('After:', heap)  # 2 removed, heap still valid

빈도가 높은 상위 K개 원소를 힙으로 찾기

빈도가 높은 상위 K개 원소(LeetCode #347)는 크기 k인 최소 힙을 사용합니다. 각 항목이 (frequency, element)인 최소 힙을 유지합니다. 고유한 각 원소를 처리할 때 힙의 원소 수가 k보다 적으면 삽입합니다. 그렇지 않고 새 원소의 빈도가 힙의 최솟값보다 크면 최솟값을 삭제하고 새 원소를 삽입합니다. 최종 힙에는 O(n log k) time에 빈도가 가장 높은 k개의 원소가 들어 있습니다.

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    count = Counter(nums)
    # Min-heap of (frequency, num)
    heap = []
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)  # remove least frequent
    return [num for freq, num in heap]

print(top_k_frequent([1,1,1,2,2,3], 2))  # [1, 2]
print(top_k_frequent([4,4,4,3,3,2,1], 2)) # [4, 3]

스케줄링에서의 힙 활용

경쟁 프로그래밍을 넘어, 힙은 실제 스케줄링 시스템을 구동합니다. 운영 체제의 작업 스케줄러는 우선순위 큐(힙)를 사용하여 우선순위가 가장 높은 준비된 프로세스를 항상 실행합니다. 이벤트 기반 시뮬레이션은 이벤트 시간을 기준으로 하는 최소 힙을 사용해 시간 순서대로 이벤트를 처리합니다. 네트워크 패킷 스케줄러는 서비스 품질 클래스에 따라 트래픽의 우선순위를 지정합니다. 힙을 이해하면 이러한 모든 시스템을 파악하는 사고 모델을 얻을 수 있으며, 큐잉과 스케줄링에 관한 시스템 설계 면접에서도 자연스럽게 등장합니다.

import heapq

# Simple event-driven simulation using a heap
events = []  # (time, event_description)

def schedule(time, event):
    heapq.heappush(events, (time, event))

def process_next():
    time, event = heapq.heappop(events)
    print(f't={time}: {event}')
    return time, event

# Schedule events out of order:
schedule(10, 'Send email')
schedule(3,  'Open app')
schedule(7,  'Process request')
schedule(1,  'Start server')

# Process in time order:
while events:
    process_next()
# Output: t=1, t=3, t=7, t=10 -- always in time order

빠른 확인

이 단원에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 대비 개념에 대한 이해도를 테스트해 보세요.

인터랙티브 레슨에서 답해보세요

학습 내용 요약

이 단원에서 배운 내용: 처음부터 구현하는 MinHeap과 MaxHeap 및 위로 올리기와 아래로 내리기, 하나씩 삽입하는 O(n log n) 방식보다 효율적인 이유를 포함한 Floyd의 O(n) heapify 알고리즘, 그리고 빈도가 높은 상위 k개 원소와 인덱스로 삭제를 포함한 실용적인 활용입니다. 다음으로 파이썬의 heapq 모듈과 최대 힙 기법을 살펴봅니다.

무료로 시작

AI 튜터와 함께 Python을(를) 배우세요 — 무료

브라우저에서 실제 코드를 작성하고 실행하며, 24/7 AI 튜터로부터 즉각적인 도움을 받고, 웹이나 앱에서 중단한 부분부터 계속 학습하세요.

코스: 30
레슨: 120

무료로 학습 시작 전체 코스 보기

자주 묻는 질문