• data-structure
  • tree
  • python

힙(Heap)과 우선순위 큐

완전 이진 트리 기반 힙의 성질과 배열 구현, 삽입·삭제 과정, 힙 정렬, 파이썬 heapq 사용법을 정리한다.

Manx4분 읽기
시리즈 · 자료구조 · 알고리즘7 / 13
  1. 시간 복잡도와 공간 복잡도
  2. 재귀 함수와 꼬리 재귀 최적화
  3. 연결 리스트(Linked List)
  4. 스택과 큐: 원형 큐 구현과 덱
  5. 해시 테이블: 해시 함수와 충돌 처리
  6. 트리와 이진 탐색 트리
  7. 힙(Heap)과 우선순위 큐
  8. 균형 이진 탐색 트리: AVL, Red-Black, B-Tree
  9. 그래프: 인접 행렬과 인접 리스트
  10. 최단 경로 알고리즘: BFS, 다익스트라, 벨만-포드, 플로이드-워셜, A*
  11. 최소 신장 트리(MST): Kruskal, Prim, Union-Find
  12. 정렬 알고리즘: 퀵·병합·기수 정렬부터 Timsort까지
  13. Thread-Safe 자료구조: Python GIL과 Java ConcurrentHashMap

힙이란

최댓값 또는 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리 기반의 자료구조로, 우선순위 큐를 구현하는 데 쓰인다.

  • 부모 노드와 자식 노드의 키 사이에 항상 대소 관계가 성립한다.
    • 최소 힙(Min Heap): 각 노드의 키가 자식 노드의 키보다 크지 않다.
    • 최대 힙(Max Heap): 각 노드의 키가 자식 노드의 키보다 작지 않다.
  • 부모와 자식 사이의 관계만 정해져 있고 형제 사이의 순서는 없는 반정렬 상태이다.
  • 이진 탐색 트리와 달리 중복된 값을 허용한다.

부모와 자식 노드 사이에 대소 관계가 성립하는 힙의 트리 구조

스택과 큐는 들어온 순서에 따라 나가는 순서가 정해지지만, 우선순위 큐는 내가 정한 우선순위에 따라 나가는 순서가 정해진다.

배열로 힙을 구현하는 방법

완전 이진 트리는 중간에 빈 자리가 없으므로 배열에 차례대로 담을 수 있다. 구현을 쉽게 하기 위해 0번 인덱스를 비워 두고 1번부터 사용하면 인덱스 관계가 다음과 같다.

노드 인덱스
왼쪽 자식 2i
오른쪽 자식 2i + 1
부모 i / 2 (몫)

0번 인덱스부터 사용하는 경우에는 왼쪽 자식이 2i + 1, 오른쪽 자식이 2i + 2가 된다. 파이썬의 heapq가 이 방식이다.

삽입과 삭제

삽입과 삭제의 시간 복잡도는 O(log N)이다. 원소를 넣고 빼는 것 자체는 O(1)이지만, 힙의 성질을 다시 맞추는 과정(heapify)이 트리의 높이만큼, 즉 O(log N) 걸리기 때문이다.

삽입

  1. 새로운 노드를 힙의 마지막 위치에 넣는다.
  2. 부모 노드와 비교해 대소 관계가 어긋나면 자리를 바꾼다. 어긋나지 않을 때까지 위로 올라가며 반복한다.

삭제

  1. 힙의 삭제 연산은 루트 노드(최대 힙이면 최댓값)를 꺼내는 것이다.
  2. 가장 마지막 노드를 루트 자리로 옮긴다.
  3. 자식 노드와 비교하며 아래로 내려가 힙의 성질을 다시 맞춘다.

힙에서는 편향이 발생하지 않는 이유

힙은 항상 완전 이진 트리 형태를 유지한다. 새 노드는 언제나 마지막 위치에 채워지고, 자식은 부모와의 대소 관계만 만족하면 될 뿐 왼쪽과 오른쪽 중 어디에 있어야 한다는 제약이 없다. 그래서 이진 탐색 트리처럼 한쪽으로 치우칠 일이 없고 높이가 항상 log N으로 유지된다.

힙 정렬의 시간 복잡도

  1. 배열을 힙으로 만든다.
  2. 루트(최댓값)를 꺼내는 일을 N번 반복한다. 한 번 꺼낼 때마다 heapify에 O(log N)이 든다.

따라서 전체 시간 복잡도는 O(N log N)이다.

파이썬 heapq

파이썬의 heapq 모듈은 리스트를 최소 힙으로 다룬다. k번째 원소가 항상 자식 원소(2k+1, 2k+2번째)보다 작거나 같도록 유지된다.

  • heapq.heappush(heap, item): heap에 item을 추가한다.
  • heapq.heappop(heap): 가장 작은 원소를 꺼내 반환한다. 비어 있으면 IndexError가 발생한다.
  • heapq.heapify(x): 리스트 x를 제자리에서 힙으로 변환한다. O(n)

최대 힙 만들기

heapq는 최소 힙만 지원한다. 최대 힙이 필요하면 부호를 뒤집은 값을 우선순위로 삼아 (-item, item) 튜플로 넣는다.

import heapq

max_heap = []
for item in [3, 1, 5]:
    heapq.heappush(max_heap, (-item, item))

print(heapq.heappop(max_heap)[1])  # 5

Reference