[알고리즘/Python] 힙(Heap)

📌 힙 

• 힙은 우선순위 큐를 위해 만들어진 자료구조로, 완전 이진트리의 일종이다.
• 여러 값 중 최대/최소 값을 빠르게 찾아내도록 만들어진 반정렬 상태이다.
• 힙에서는 중복된 값을 허용한다.
• 최대/최소 값을 찾기 위해서 O(n)의 시간이 걸리지만, 힙을 사용하면 O(logN) 만큼 소요된다.

 

✅ 반정렬 상태 (느슨한 정렬 상태)
큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작은 이진 트리이다.

✅ 우선순위 큐
들어간 순서와 상관 없이
높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리
만약 두 원소가 같은 우선순위를 가진다면 큐에서 그들의 순서에 의해 처리

우선 순위 큐

✅ 완전 이진트리
자식 노드가 최대 2개만 채워진다. 
우선순위 큐 순서대로 채워진다. 

 

 

 

📌 파이썬 Heapq 모듈

• 파이썬에서는 heapq 모듈을 사용해서 최소 힙과 최대 힙을 구현할 수 있다.
• DEFAULT로 최소 힙을 제공한다. 

 

✅ heapq 내부 메소드

heapq 모듈의 내부 메소드들 중 주로 쓰이는 메소드는 heappush와 heappop이 있다.

모든 메소드는 힙의 불변성을 유지하며 동작한다. 

1. heapq.heappush(heap, item) : item을 heap에 추가
2. heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. 
3. heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N))
4. heapq.nlargest(n, iterable, key=None): 최소힙에서 최댓값을 구할 수 있도록 돕는다. 
   • n: 힙을 내림차순으로 정렬해 n개의 데이터를 리턴한다. 
   • iterable: heap 이름을 넣으면 된다. 
   • 기존의 힙은 변경하지 않는다. 변경된 힙은 리턴하기 때문에 반드시 = 로 받아줘야 한다. 

   

 

✅ 최소 힙

다음과 같이 최소 힙을 구현할 수 있다.

• heap 역할을 할 1) 빈 리스트를 선언해주고, 2)heappush()의 매개변수로 해당 리스트와 추가하고자 하는 값을 넣으면 리스트는 힙 정렬된 상태를 유지하며 원소들이 추가된다. 

import heapq

heap = []

# 아래 for문을 실행하고 나면 heap은 [1,2,3,5,4]로 힙 정렬이 되게 된다.
for i in range(1,6):
	heapq.heappush(heap, i)

# 작은 숫자 순서대로 1,2,3,4,5가 출력된다.
for i in range(5):
	print(heapq.heappop(heap))

• 3) 이미 존재하는 리스트를 힙으로 만들고 싶을 때는 heapq.heapify(리스트명) 을 사용하면 된다. 

 

✅ 최대 힙

heapq에서는 최대 힙을 제공하지 않는다. 따라서 다음과 같이 부호를 변경하는 방법을 사용해서 최대 힙을 구현한다. 

📢 1) 부호를 바꿔서 최소 힙에 넣어준 뒤에

📢 2) 최솟값부터 pop을 해줄 때 다시 부호를 바꿔주면 최대 힙과 동일하다.

import heapq

heap = []
values = [1,5,3,2,4]

# 1. 아래 for문을 실행시키고 나면 heap은 [-5,-4,-3,-1,-2]가 된다.
for value in values:
	heapq.heappush(heap, -value)

# 2. 아래 for문을 실행시키면 5,4,3,2,1이 출력된다. 즉, 큰 숫자부터 출력이 된다.
for i in range(5):
	print(-heapq.heappop(heap))