Python에서 heap 사용하기, 힙큐(heapq)

힙이 필요한 이유

원소 100만 개가 있고, 가장 작은 값 꺼내기를 100만번 반복해야 한다고 할 때, 아래와 같은 효율을 낸다.

• 리스트 순회 : O(n)
• sort() : O(n log n)
• 힙 : O(log n)

 

모든 원소를 다 정렬해 봐야하는 문제라면 힙은 의미가 없다. 힙이 필요할 때는 매번 극값(가장 크거나 작은 값) 하나만 필요할 때이다.

 

 

 

Heap 힙 이란?

힙은 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한다.

1. 완전 이진 트리 : 위에서 아래로, 왼쪽에서 오른쪽으로 빈틈없이 채워진다.
2. 힙 속성 : 모든 부모 ≤ 자식 (min heap 기준)

형제끼리는 아무 순서 관계가 없다. 힙이 보장하는 건 오직 루트 heap[0] 가 전체 최솟값이라는 것이다.

 

 

 

파이썬의 힙큐 heapq

파이썬에서는 heapq 모듈이 일반 리스트를 힙 규칙에 맞게 조작해준다.

 

힙은 왜 배열을 사용할까?

일반 트리는 각 노드가 자식 주소를 들고 있어야 하는데, 힙은 완전 이진 트리라 중간에 빈칸이 없다. 위에서부터 순서대로 번호를 매기고, 번호만 알면 부모, 자식 위치를 계산할 수 있다.

포인터 저장 공간 0, 캐시 지역성은 리스트 수준이다. 배열이라는 점에서 힙이 빠른 이유를 확인할 수 있다. 

 

 

 

메서드

import heapq

h = []
heapq.heappush(h,5)		# O(log n)
heapq.heappop(h)		# 최솟값 반환, 제거, O(log n)
h[0]					# 최솟값 조회만, O(1)

arr = [5, 3, 8, 1]
heapq.heapify(arr)		# 리스트를 제자리에서 힙으로, O(n)

heapq.heappushpop(h, x)	# push 후 pop (먼저 넣고 뺌)
heapq.heapreplace(h, x)	# pop 후 push (먼저 빼고 넣음)

heapq.nlargest(3, arr)	# 상위 3개
heapq.nsmallest(3, arr)	# 하위 3개

 

heapify 가 O(n) 인 이유 : 원소 절반은 리프라 내려갈 곳이 없고, 위로 갈수록 노드 수는 절반씩 줄어든다.

 

 

 

삽입 push 원리

[1, 3, 2, 7, 5, 4] 에 0을 넣어서 구현해보자.

1. 맨 뒤에 붙인다 → [1, 3, 2, 7, 5, 4, 0] , 인덱스 6 배정
2. 부모와 비교 → 인덱스 6의 부모는 (6-1)//2 = 2. 0 < 2 이므로 교환 → [1, 3, 0, 7, 5, 4, 2]
3. 다시 부모 → 인덱스 2의 부모는 0, 값 1. 0 < 1 이므로 교환 → [0, 3, 1, 7, 5, 4, 2]

이와같이 구현하는 것을 sift-up(상향 이동) 이라 한다. 이동 횟수는 최대 트리 높이 log n

 

교환 전:

        1
      /   \
     3     2        ← 2가 부모
    / \   / \
   7   5 4   0      ← 0이 자식 (잘못된 상태)

 

교환 후:

        1
      /   \
     3     0        ← 0이 올라옴
    / \   / \
   7   5 4   2      ← 2가 내려옴

 

 

 

삭제 pop 원리

최솟값인 루트를 꺼낸다. 루트 자리가 비었을 때, 맨 끝 원소를 루트로 가져온다. 왼쪽 자식을 올리지 않는 이유는 그 자리가 비고, 연쇄적으로 구멍이 생기면서 완전 이진트리 모양이 깨지게 된다. 지워도 모양에 영향 없는 맨 끝 원소를 루트에 놓고, 아래로 내려보낸다 (sift-down). 내려갈때는 두 자식 중 더 작은 쪽 과 비교해서 교환한다.

1. 루트를 꺼낸다 
2. 맨 끝 원소를 루트로 옮긴다
3. 루트값이 자식들보다 크면 내려보낸다. (왼쪽 자식, 오른쪽 자식 둘다 비교) 인덱스 0의 자식은 2*0+1, 2*0+2

 

임의 원소 삭제가 불가능해, lazy deletion 삭제 표시만 해두고, pop 했을 때 이미 무료한 원소면 버리고 다음 걸 꺼낸다.

 

 

부모/자식 구하는 식

층을 내려갈 때마다 노드 수가 2배라서 인덱스도 2배 근처로 벌어진다.

left   = 2*i + 1
right  = 2*i + 2
parent = (i - 1) // 2

 

 

 

자주 쓰는 패턴 

최대 힙

Python hepq는 min-heap 만 지원한다. 부호를 뒤집어 넣고 뺄 때 다시 뒤집는다.

heapq.heappush(h, -score)
top = -heapq.heappop(h)

 

 

튜플로 우선순위 지정

튜플은 앞 원소부터 순서대로 비교된다.

heapq.heappush(h, (거리, 노드))   # 거리 기준 정렬