[알고리즘] 우선순위 큐, 힙 heap

우선순위 큐는 각 원소들이 우선순위를 가지고 있고, 높은 우선순위의 원소가 낮은 우선순위의 원소보다 먼저 처리된다.

만약 우선순위가 동일하다면 먼저 들어온 원소를 처리한다.

우선순위는 힙을 통해 구현할 수 있다고 한다.

 

힙은, 완전 이진 트리로 부모 노드의 값이 항상 자식 노드보다 값이 작거나 큰 트리를 말한다.

부모 노드의 값이 항상 자식 노드보다 작은 경우를 최소힙(Min Heap)이라고 하며, 반대로 부모 노드의 값이 항상 자식 노드보다 큰 것은 최대 힙(Max Heap)이라 한다.

---

파이썬에는 Priority Queue와 heapq 내장 모듈이 있는데 오늘은 heapq에 대해 살펴보자.

 

heapq는 최소 힙 구조이고, 가장 작은 요소가 0번째에 위치한다.

또한 모든 k에 대해 heap[k] <= heap[2*k+1] 또는 heap[k] <= heap[2*k+2] 만족한다.

 

heappush()는 힙의 형태를 유지하면서(우선순위를 지정하여) item을 푸시하고,

pop()은 힙을 유지하며 우선순위가 가장 작은 원소를 pop하여 반환한다.

 

heapify()를 사용하여 리스트를 heap으로 변환할 수 있다.

 

그러면 백준과 프로그래머스의 힙 관련 문제풀이들을 살펴보자.

 

---

1. 백준 - #1927 최소 힙

https://live-for-myself.tistory.com/206

[CodingTest] 백준 #1927 최소 힙

 

2. 백준 - #11279 최대 힙

https://live-for-myself.tistory.com/205

[CodingTest] 백준 #11279 최대 힙 / 힙큐 heapq

 

3. 백준 - #11286 절댓값 힙

https://live-for-myself.tistory.com/207

[CodingTest] 백준 #11286 절댓값 힙

4. 프로그래머스 - 더 맵게

https://live-for-myself.tistory.com/18

[CodingTest] 프로그래머스 Programmers 힙 Level 2 더 맵게