[Daily morning study] 힙(Heap) 자료구조와 우선순위 큐

12 Aug 2026 in Daily morning study / DSA

#daily morning study

힙(Heap)이란?

힙은 완전 이진 트리(Complete Binary Tree) 기반의 자료구조로, 부모 노드와 자식 노드 사이에 항상 일정한 우선순위 관계가 유지된다.

힙의 두 가지 종류:

최대 힙(Max-Heap): 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같다. 루트가 전체 최댓값.
최소 힙(Min-Heap): 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같다. 루트가 전체 최솟값.

힙은 완전 이진 트리이기 때문에 배열(Array)로 효율적으로 표현할 수 있다.

배열로 힙 표현하기

인덱스 1부터 시작할 때의 부모·자식 관계:

관계	인덱스 계산
부모 노드	`i / 2`
왼쪽 자식	`i * 2`
오른쪽 자식	`i * 2 + 1`

인덱스 0부터 시작할 때:

관계	인덱스 계산
부모 노드	`(i - 1) / 2`
왼쪽 자식	`i * 2 + 1`
오른쪽 자식	`i * 2 + 2`

예: 최소 힙을 배열로 표현하면

배열: [1, 3, 5, 7, 9, 8, 6]

          1          (index 0)
        /   \
       3     5       (index 1, 2)
      / \   / \
     7   9 8   6     (index 3, 4, 5, 6)

핵심 연산

삽입 (Insert) — O(log N)

배열의 마지막에 새 원소를 추가한다.
부모 노드와 비교하면서 힙 조건이 만족될 때까지 위로 올린다 (Heapify Up / Sift Up).

def push(heap, val):
    heap.append(val)
    i = len(heap) - 1
    while i > 0:
        parent = (i - 1) // 2
        if heap[parent] > heap[i]:   # 최소 힙 조건
            heap[parent], heap[i] = heap[i], heap[parent]
            i = parent
        else:
            break

삭제 (Delete / Pop) — O(log N)

최소/최대 힙에서 루트(최솟값 또는 최댓값)를 꺼내는 과정:

루트 값을 저장한다.
배열의 마지막 원소를 루트 자리로 옮기고 배열 크기를 1 줄인다.
자식 노드와 비교하면서 힙 조건이 만족될 때까지 아래로 내린다 (Heapify Down / Sift Down).

def pop(heap):
    if not heap:
        return None
    root = heap[0]
    heap[0] = heap[-1]
    heap.pop()
    
    i = 0
    n = len(heap)
    while True:
        left, right = 2 * i + 1, 2 * i + 2
        smallest = i
        if left < n and heap[left] < heap[smallest]:
            smallest = left
        if right < n and heap[right] < heap[smallest]:
            smallest = right
        if smallest == i:
            break
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest
    
    return root

조회 (Peek) — O(1)

루트를 제거하지 않고 확인만 한다. heap[0]이 항상 최솟값(최소 힙) 또는 최댓값(최대 힙)이므로 O(1).

배열에서 힙 만들기 — O(N)

임의의 배열을 힙으로 변환하는 방법은 Heapify 연산이다.

나이브하게 원소를 하나씩 삽입하면 O(N log N)이지만, 마지막 내부 노드(leaf가 아닌 노드 중 가장 뒤에 있는 것)부터 루트까지 Heapify Down을 역순으로 수행하면 O(N)에 가능하다.

def build_heap(arr):
    n = len(arr)
    # 마지막 내부 노드 인덱스: (n // 2) - 1
    for i in range(n // 2 - 1, -1, -1):
        heapify_down(arr, n, i)

이 방법이 O(N)인 이유: 트리 하단부에 있는 노드들은 heapify down 거리가 짧고, 상단부로 갈수록 노드 수가 적기 때문에 전체 작업량의 합이 O(N)으로 수렴한다.

우선순위 큐(Priority Queue)

우선순위 큐는 가장 높은 우선순위를 가진 원소를 먼저 꺼내는 추상 자료형(ADT)이다. 힙은 우선순위 큐를 구현하는 가장 효율적인 방법이다.

연산	배열(정렬 안됨)	배열(정렬됨)	힙
삽입	O(1)	O(N)	O(log N)
최솟값 삭제	O(N)	O(1)	O(log N)
최솟값 조회	O(N)	O(1)	O(1)

힙 기반 우선순위 큐가 삽입과 삭제 모두 O(log N)으로 균형 잡힌 성능을 제공한다.

Python의 heapq 모듈

Python은 최소 힙을 기본으로 제공한다.

import heapq

# 힙 생성
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)

print(heapq.heappop(heap))  # 1 (최솟값)
print(heapq.heappop(heap))  # 3

# 리스트를 힙으로 변환 — O(N)
arr = [5, 3, 8, 1, 9]
heapq.heapify(arr)
print(arr[0])  # 1

# 최대 힙 흉내내기 — 값에 음수 붙이기
max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -20)
print(-heapq.heappop(max_heap))  # 20 (최댓값)

힙 정렬 (Heap Sort) — O(N log N)

배열 전체를 힙으로 만든다 (O(N)).
루트(최댓값)를 배열 끝과 교환하고 힙 크기를 1 줄인다.
루트에 대해 Heapify Down을 수행한다 (O(log N)).
2~3을 힙 크기가 1이 될 때까지 반복한다.

def heap_sort(arr):
    n = len(arr)
    # 최대 힙 구성
    for i in range(n // 2 - 1, -1, -1):
        heapify_down(arr, n, i)
    # 정렬
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify_down(arr, i, 0)

def heapify_down(arr, n, i):
    largest = i
    left, right = 2 * i + 1, 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify_down(arr, n, largest)

힙 정렬의 특성:

시간 복잡도: O(N log N) (항상 보장)
공간 복잡도: O(1) (제자리 정렬, In-place)
불안정 정렬(Unstable Sort): 동일한 값의 원소 순서 보장 안됨

힙의 실전 활용

1. K번째 최솟값 / 최댓값 찾기

크기 K인 최대 힙을 유지하면, 힙의 루트가 K번째 최솟값이 된다.

import heapq

def kth_smallest(nums, k):
    # 최대 힙으로 크기 k 유지 (Python은 음수로 최대 힙 흉내)
    heap = []
    for num in nums:
        heapq.heappush(heap, -num)
        if len(heap) > k:
            heapq.heappop(heap)
    return -heap[0]

2. 다익스트라(Dijkstra) 알고리즘

최단 경로 탐색 시 우선순위 큐(최소 힙)를 사용해 현재까지 가장 짧은 경로 노드를 빠르게 꺼낸다.

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]  # (거리, 노드)
    
    while pq:
        cost, u = heapq.heappop(pq)
        if cost > dist[u]:
            continue
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(pq, (dist[v], v))
    return dist

3. 중앙값 실시간 유지

최대 힙과 최소 힙 두 개를 결합해서 스트리밍 데이터의 중앙값을 O(log N)에 유지할 수 있다.

최대 힙(lower half): 중앙값 이하 원소들 저장 → 루트가 하반부 최댓값
최소 힙(upper half): 중앙값 초과 원소들 저장 → 루트가 상반부 최솟값
두 힙의 크기 차이를 1 이하로 유지하면 중앙값은 항상 힙 루트에서 O(1)에 접근 가능

시간 복잡도 요약

연산	시간 복잡도
삽입 (push)	O(log N)
최솟값/최댓값 삭제 (pop)	O(log N)
최솟값/최댓값 조회 (peek)	O(1)
임의 원소 삭제	O(N) — 위치 탐색 + log N heapify
배열에서 힙 생성 (heapify)	O(N)
힙 정렬	O(N log N)

핵심 정리

힙은 완전 이진 트리 + 부모-자식 우선순위 관계가 핵심이다.
배열로 구현할 수 있어 포인터 없이 메모리 효율이 좋다.
우선순위 큐의 표준 구현체이며, 다익스트라·K번째 원소·중앙값 유지 등 다양한 문제에서 핵심 역할을 한다.
Python에서는 heapq 모듈이 최소 힙을 제공하며, 최대 힙이 필요할 때는 값을 음수로 뒤집어 사용한다.

[Daily morning study] 힙(Heap) 자료구조와 우선순위 큐

힙(Heap)이란?

배열로 힙 표현하기

핵심 연산

삽입 (Insert) — O(log N)

삭제 (Delete / Pop) — O(log N)

조회 (Peek) — O(1)

배열에서 힙 만들기 — O(N)

우선순위 큐(Priority Queue)

Python의 heapq 모듈

힙 정렬 (Heap Sort) — O(N log N)

힙의 실전 활용

1. K번째 최솟값 / 최댓값 찾기

2. 다익스트라(Dijkstra) 알고리즘

3. 중앙값 실시간 유지

시간 복잡도 요약

핵심 정리

🐒🇰🇷

Error

힙(Heap)이란?

배열로 힙 표현하기

핵심 연산

삽입 (Insert) — O(log N)

삭제 (Delete / Pop) — O(log N)

조회 (Peek) — O(1)

배열에서 힙 만들기 — O(N)

우선순위 큐(Priority Queue)

Python의 heapq 모듈

힙 정렬 (Heap Sort) — O(N log N)

힙의 실전 활용

1. K번째 최솟값 / 최댓값 찾기

2. 다익스트라(Dijkstra) 알고리즘

3. 중앙값 실시간 유지

시간 복잡도 요약

핵심 정리

Templates (for web app):

Error