Heap - 컴퓨터공학 > 자료구조 | AI Insight Note

힙(Heap)은 완전 이진 트리 구조에서 부모 노드가 자식 노드보다 항상 크거나(최대 힙) 작은(최소 힙) 조건을 만족하는 자료구조다. 우선순위 큐(큐의 확장), 힙 정렬, 다익스트라 알고리즘에 핵심적으로 활용된다.

힙의 특성

•완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 꽉 채워져 있음
•느슨한 정렬(반정렬) 상태: BST와 달리 왼쪽/오른쪽 자식 간 순서 없음, 부모-자식 관계만 보장
•중복 허용: BST와 달리 같은 값이 여러 개 존재 가능

우선순위 큐 구현 비교

구현 방식	삽입	삭제(최솟값)
정렬 없는 배열	O(1)	O(n)
정렬 없는 연결 리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결 리스트	O(n)	O(1)
힙 (Heap)	O(log n)	O(log n)

→ 힙이 삽입·삭제 모두 O(log n)으로 가장 균형 잡힌 성능을 제공한다.

힙의 종류

최대 힙 (Max Heap):      최소 힙 (Min Heap):
       100                      1
      /   \                   /   \
    19     36               4      3
   /  \   /  \             /  \  /  \
  17  3  25  1            7   8  5   2

규칙: 부모 ≥ 자식    규칙: 부모 ≤ 자식

힙 연산

삽입 — O(log n)

최소 힙에 값 2 삽입:
1. 맨 끝에 삽입
2. 부모와 비교 → 부모보다 작으면 교환 (Bubble Up)

       1                    1
      / \       →          / \
     4   3                2   3
    / \                  / \
   7   2(삽입)          7   4

삭제 (최솟값 추출) — O(log n)

1. 루트(최솟값) 제거
2. 맨 끝 원소를 루트로 이동
3. 자식과 비교 → 더 작은 자식과 교환 (Bubble Down)

Peek (최솟값/최댓값 조회) — O(1)

루트 노드를 제거하지 않고 반환. 힙에서 유일한 O(1) 조회 연산.

python

import heapq
heap = [3, 1, 4, 1, 5]
heapq.heapify(heap)
print(heap[0])    # 1 — O(1) peek (제거 안 함)
print(heapq.heappop(heap))  # 1 — O(log n) 제거

Heapify (힙 재구조화)

힙에 원소를 삽입하거나 삭제하면 힙 조건이 깨질 수 있다. 이를 복구하는 과정이 heapify다.

Heapify-Up (삽입 시): 새 원소를 맨 끝에 삽입 → 부모와 비교하며 조건 만족 시까지 위로 이동

삽입 연산 자체: O(1)  +  Heapify-Up: O(log n)  →  전체: O(log n)

Heapify-Down (삭제 시): 루트 삭제 → 마지막 원소를 루트로 이동 → 더 작은/큰 자식과 비교하며 아래로 이동

삭제 연산 자체: O(1)  +  Heapify-Down: O(log n)  →  전체: O(log n)

Build Heap (배열 → 힙 변환): 아무 배열을 힙으로 만들기

방법: 마지막 내부 노드(n//2 - 1)부터 루트까지 역순으로 heapify-down 적용
시간 복잡도: O(n)  (heapify를 n번 하지만 수학적으로 O(n)이 됨)

import heapq
arr = [3, 1, 4, 1, 5, 9, 2]
heapq.heapify(arr)  # in-place, O(n)

힙 정렬 (Heap Sort)

내림차순 정렬 → 최대 힙 사용
오름차순 정렬 → 최소 힙 사용

1. 배열로 최대 힙 구성: O(n)
2. 루트(최댓값)와 마지막 원소 교환 후 힙 크기 1 감소: O(1)
3. heapify-down으로 힙 복구: O(log n)
4. 2~3을 n-1번 반복: O(n log n)

힙 정렬은 추가 메모리가 불필요(In-place)하고 항상 O(n log n)을 보장하지만, 퀵 정렬 대비 캐시 지역성이 낮아 실제로는 더 느린 경우가 많다.

힙 정렬의 장점: N개 중 상위 K개만 필요할 때 O(n + k log n)으로 효율적.

배열로 표현하는 힙

인덱스:  0   1   2   3   4   5   6
힙:     [1,  4,  3,  7,  8,  5,  2]

부모(i) = (i-1) // 2
왼쪽 자식(i) = 2*i + 1
오른쪽 자식(i) = 2*i + 2

코드 예시 (Python heapq)

python

import heapq

# 최소 힙 (Python 기본)
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)

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

# 최대 힙 — 값을 음수로 저장
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -3)
-heapq.heappop(max_heap)  # 5 (최댓값)

# 상위 K개 효율적으로 추출
data = [3, 1, 4, 1, 5, 9, 2, 6, 5]
top3 = heapq.nlargest(3, data)   # [9, 6, 5]
bot3 = heapq.nsmallest(3, data)  # [1, 1, 2]

java

// Java — PriorityQueue (최소 힙 기본)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(3); minHeap.offer(1); minHeap.offer(4);
minHeap.peek();  // 1 — O(1) 조회
minHeap.poll();  // 1 — O(log n) 삭제

// 최대 힙
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

힙의 활용

활용	설명
우선순위 큐	가장 높은(낮은) 우선순위 원소를 O(log n)에 추출
힙 정렬	O(n log n) 정렬, 추가 메모리 불필요
다익스트라	최단 경로 탐색 시 최소 거리 노드 추출
중앙값 유지	최대 힙 + 최소 힙으로 스트리밍 중앙값
작업 스케줄링	운영체제의 CPU 스케줄링
허프만 코딩	빈도 기반 최적 압축 코드 생성

시간 복잡도

연산	복잡도
삽입	O(log n)
최솟값(최댓값) 조회 (Peek)	O(1)
최솟값(최댓값) 삭제	O(log n)
힙 생성 (heapify)	O(n)
k번째 최솟값	O(k log n)

참고문헌

•Cormen et al. Introduction to Algorithms — Chapter 6
•Williams, J.W.J. (1964). Algorithm 232 — Heapsort
•Python 공식 문서 — heapq module

Heap힙