힙과 우선순위 큐 (Heap and Priority Queue)¶

개요¶

힙은 완전 이진 트리 기반의 자료구조로, 최댓값/최솟값을 O(1)에 접근하고 O(log n)에 삽입/삭제할 수 있습니다.

목차¶

힙 개념
힙 연산
힙 정렬
우선순위 큐
활용 문제
연습 문제

1. 힙 개념¶

힙 속성¶

최대 힙 (Max Heap):
- 부모 노드 ≥ 자식 노드
- 루트가 최댓값

       (16)
      /    \
    (14)   (10)
    /  \   /  \
  (8) (7)(9) (3)

최소 힙 (Min Heap):
- 부모 노드 ≤ 자식 노드
- 루트가 최솟값

        (1)
       /   \
     (3)   (2)
     / \   /
   (6)(5)(4)

배열 표현¶

힙은 완전 이진 트리 → 배열로 효율적 표현

       (16)                 인덱스:
      /    \                0: 16
    (14)   (10)             1: 14, 2: 10
    /  \   /  \             3: 8, 4: 7, 5: 9, 6: 3
  (8) (7)(9) (3)

배열: [16, 14, 10, 8, 7, 9, 3]

인덱스 관계 (0-based):
- 부모: (i - 1) / 2
- 왼쪽 자식: 2 * i + 1
- 오른쪽 자식: 2 * i + 2

2. 힙 연산¶

2.1 삽입 (Insert)¶

삽입 과정 (최대 힙, 15 삽입):

1. 마지막 위치에 삽입
       (16)
      /    \
    (14)   (10)
    /  \   /  \
  (8) (7)(9) (3)
  /
(15)

2. 부모와 비교하며 위로 이동 (Bubble Up)
       (16)
      /    \
    (15)   (10)
    /  \   /  \
  (14)(7)(9) (3)
  /
(8)

시간 복잡도: O(log n)

// C
#define MAX_SIZE 1000

int heap[MAX_SIZE];
int heapSize = 0;

void insert(int value) {
    heap[heapSize] = value;
    int i = heapSize;
    heapSize++;

    // Bubble up
    while (i > 0 && heap[(i - 1) / 2] < heap[i]) {
        int parent = (i - 1) / 2;
        int temp = heap[i];
        heap[i] = heap[parent];
        heap[parent] = temp;
        i = parent;
    }
}

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

    def insert(self, value):
        self.heap.append(value)
        self._bubble_up(len(self.heap) - 1)

    def _bubble_up(self, i):
        while i > 0:
            parent = (i - 1) // 2
            if self.heap[parent] >= self.heap[i]:
                break
            self.heap[parent], self.heap[i] = self.heap[i], self.heap[parent]
            i = parent

2.2 삭제 (Extract)¶

최댓값 삭제 과정:

1. 루트(최댓값) 제거, 마지막 원소를 루트로
       (3)
      /    \
    (14)   (10)
    /  \   /
  (8) (7)(9)

2. 자식과 비교하며 아래로 이동 (Bubble Down)
       (14)
      /    \
    (8)    (10)
    /  \   /
  (3) (7)(9)

시간 복잡도: O(log n)

// C
int extractMax() {
    if (heapSize <= 0) return -1;

    int max = heap[0];
    heap[0] = heap[heapSize - 1];
    heapSize--;

    // Bubble down
    int i = 0;
    while (1) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < heapSize && heap[left] > heap[largest])
            largest = left;
        if (right < heapSize && heap[right] > heap[largest])
            largest = right;

        if (largest == i) break;

        int temp = heap[i];
        heap[i] = heap[largest];
        heap[largest] = temp;
        i = largest;
    }

    return max;
}

class MaxHeap:
    def extract_max(self):
        if not self.heap:
            return None

        max_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()

        if self.heap:
            self._bubble_down(0)

        return max_val

    def _bubble_down(self, i):
        n = len(self.heap)

        while True:
            left = 2 * i + 1
            right = 2 * i + 2
            largest = i

            if left < n and self.heap[left] > self.heap[largest]:
                largest = left
            if right < n and self.heap[right] > self.heap[largest]:
                largest = right

            if largest == i:
                break

            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            i = largest

2.3 Heapify (배열을 힙으로)¶

배열을 힙으로 변환

방법 1: 삽입 반복 - O(n log n)
방법 2: Bottom-up heapify - O(n)

Bottom-up:
- 마지막 비-리프 노드부터 루트까지 bubble down
- 비-리프 노드 인덱스: n/2 - 1부터 0까지

// C++
void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void buildHeap(vector<int>& arr) {
    int n = arr.size();

    // 마지막 비-리프 노드부터
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 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(arr, n, largest)

def build_heap(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

3. 힙 정렬 (Heap Sort)¶

알고리즘¶

1. 배열을 최대 힙으로 변환
2. 루트(최댓값)를 마지막과 교환
3. 힙 크기 줄이고 heapify
4. 반복

[4, 10, 3, 5, 1]

최대 힙: [10, 5, 3, 4, 1]

단계:
[1, 5, 3, 4, | 10]  ← 10 정렬됨
[5, 4, 3, 1, | 10]  ← heapify
[1, 4, 3, | 5, 10]  ← 5 정렬됨
[4, 1, 3, | 5, 10]  ← heapify
...
[1, 3, 4, 5, 10]    ← 완료

시간: O(n log n)
공간: O(1) - 제자리 정렬

// C++
void heapSort(vector<int>& arr) {
    int n = arr.size();

    // 최대 힙 구성
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 하나씩 추출
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

def heap_sort(arr):
    n = len(arr)

    # 최대 힙 구성
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 하나씩 추출
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

    return arr

4. 우선순위 큐¶

STL/라이브러리¶

// C++ - priority_queue (기본: 최대 힙)
#include <queue>

priority_queue<int> maxPQ;
maxPQ.push(3);
maxPQ.push(1);
maxPQ.push(4);
maxPQ.top();  // 4
maxPQ.pop();

// 최소 힙
priority_queue<int, vector<int>, greater<int>> minPQ;

// 커스텀 비교
auto cmp = [](int a, int b) { return a > b; };  // 최소 힙
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

import heapq

# Python heapq는 최소 힙만 지원

# 최소 힙
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 4)
heapq.heappop(min_heap)  # 1

# 최대 힙 (음수 트릭)
max_heap = []
heapq.heappush(max_heap, -3)  # -값으로 저장
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -4)
-heapq.heappop(max_heap)  # 4 (부호 변경)

# 배열을 힙으로
arr = [3, 1, 4, 1, 5, 9]
heapq.heapify(arr)  # O(n)

5. 활용 문제¶

5.1 K번째 최대/최소 원소¶

import heapq

def kth_largest(nums, k):
    # 방법 1: 정렬 O(n log n)
    return sorted(nums, reverse=True)[k - 1]

    # 방법 2: 최소 힙 (크기 k 유지) O(n log k)
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    return min_heap[0]

5.2 상위 K개 빈도 원소¶

from collections import Counter
import heapq

def top_k_frequent(nums, k):
    count = Counter(nums)

    # 빈도 기준 최소 힙 (크기 k 유지)
    min_heap = []
    for num, freq in count.items():
        heapq.heappush(min_heap, (freq, num))
        if len(min_heap) > k:
            heapq.heappop(min_heap)

    return [num for freq, num in min_heap]

5.3 정렬된 배열 합치기¶

import heapq

def merge_k_sorted(lists):
    min_heap = []
    result = []

    # 각 리스트의 첫 원소 삽입
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(min_heap, (lst[0], i, 0))

    while min_heap:
        val, list_idx, elem_idx = heapq.heappop(min_heap)
        result.append(val)

        # 다음 원소 삽입
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(min_heap, (next_val, list_idx, elem_idx + 1))

    return result

5.4 중앙값 스트림¶

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # 최대 힙 (작은 절반)
        self.large = []  # 최소 힙 (큰 절반)

    def add_num(self, num):
        heapq.heappush(self.small, -num)
        heapq.heappush(self.large, -heapq.heappop(self.small))

        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def find_median(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

6. 연습 문제¶

난이도	문제	플랫폼	유형
⭐⭐	최대 힙	백준	힙 기초
⭐⭐	Kth Largest	LeetCode	K번째
⭐⭐	가운데를 말해요	백준	중앙값
⭐⭐⭐	Merge K Sorted Lists	LeetCode	병합
⭐⭐⭐	Top K Frequent	LeetCode	빈도

힙 연산 복잡도 정리¶

┌────────────┬─────────────┐
│ 연산       │ 시간 복잡도 │
├────────────┼─────────────┤
│ 최대/최소  │ O(1)        │
│ 삽입       │ O(log n)    │
│ 삭제       │ O(log n)    │
│ 힙 구성    │ O(n)        │
│ 힙 정렬    │ O(n log n)  │
└────────────┴─────────────┘

다음 단계¶

11_Trie.md - 트라이

참고 자료¶

Heap Visualization
Introduction to Algorithms (CLRS) - Chapter 6

힙과 우선순위 큐 (Heap and Priority Queue)¶

개요¶

목차¶

1. 힙 개념¶

힙 속성¶

배열 표현¶

2. 힙 연산¶

2.1 삽입 (Insert)¶

2.2 삭제 (Extract)¶

2.3 Heapify (배열을 힙으로)¶

3. 힙 정렬 (Heap Sort)¶

알고리즘¶

4. 우선순위 큐¶

STL/라이브러리¶

5. 활용 문제¶

5.1 K번째 최대/최소 원소¶

5.2 상위 K개 빈도 원소¶

5.3 정렬된 배열 합치기¶

5.4 중앙값 스트림¶

6. 연습 문제¶

추천 문제¶

힙 연산 복잡도 정리¶

다음 단계¶

참고 자료¶