알고리즘 - 우선순위 큐, 힙

목차

1. 우선순위 큐, 그리고 힙
2. 시간복잡도
3. 핵심 로직
   1. insert()
   2. pop()
4. 활용 (Python)
   1. PriorityQueue vs heapq
   2. 대표유형 풀이: [11279] 최대 힙
5. 추천 문제

 

1. 우선순위 큐, 그리고 힙

Priority Queue:

• pop() 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐

Heap:

• 데이터에서 최솟값 혹은 최댓값을 빠르게 찾기위해 고안된,
  완전이진트리(Complete Binary Tree)를 기본으로 한 자료구조
• Complete Binary Tree  
  노드를 채워갈 때, 최하단 왼쪽부터 차례대로 채워 나가는 이진트리

2. 시간복잡도

Priority Queue를 구현하는 방법은 여러가지 있겠으나, 시간복잡도를 고려하여 가장 효율적인 방식이 Heap 자료구조를 이용하는 것이다.

 

Action	Priority Queue	Array
삽입	O(logN)	O(1)
(우선순위가 가장 높은 원소) 조회	O(1)	O(N)
(우선순위가 가장 높은 원소) 제거	O(logN)	O(N)

3. 핵심 로직

최대힙 기준

3.1 insert()

https://visualgo.net/en/heap?slide=1-3

[15, 10, 8, 3, 20]

3.2 pop()

4. 활용

4.1 PriorityQueue vs heapq

• PriorityQueue

from queue import PriorityQueue

# 최소 힙으로 사용
min_heap = PriorityQueue()

min_heap.put(1)
min_heap.put(3)
min_heap.put(2)

print(min_heap.get()) # 1
print(min_heap.get()) # 2
print(min_heap.get()) # 3

# 우선순위 큐로 사용
priority_queue = PriorityQueue()
priority_queue.put([1, 'apple'])
priority_queue.put([3, 'banana'])
priority_queue.put([2, 'orange'])

print(priority_queue.get())  # [1, 'apple']
print(priority_queue.get())  # [2, 'orange']
print(priority_queue.get())  # [3, 'banana']

 

• heapq

import heapq

# 최소 힙으로 사용
min_heap = []

heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 2)

print(heapq.heappop(min_heap))  # 1
print(heapq.heappop(min_heap))  # 2
print(heapq.heappop(min_heap))  # 3

# 우선순위 큐로 사용
priority_queue = []

heapq.heappush(priority_queue, [1, 'apple'])
heapq.heappush(priority_queue, [3, 'banana'])
heapq.heappush(priority_queue, [2, 'orange'])

print(heapq.heappop(priority_queue))  # [1, 'apple']
print(heapq.heappop(priority_queue))  # [3, 'banana']
print(heapq.heappop(priority_queue))  # [2, 'orange']

파이썬 우선순위 큐 구현에서 heapq가 PriorityQueue보다 실행시간이 적게 걸려 heapq를 일반적으로 많이 사용한다.
또한, PriorityQueue와 heapq는 최소 힙만 다룰 수 있기 때문에 큰 수부터 pop 하고싶을 때는 우선순위를 음수로 만들면 된다.

4.2 대표유형 풀이: [11279] 최대 힙

• 문제 설명
  
• 정답 코드

import sys
import heapq

input = sys.stdin.readline

N = int(input())

priority_queue = []
for _ in range(N):
    value = int(input())

    if value == 0:
        max_node = heapq.heappop(priority_queue) if len(
            priority_queue) != 0 else (0, 0)
        print(max_node[1])
        continue

    node = (-1 * value, value)
    heapq.heappush(priority_queue, node)

5. 추천 문제

1927번: 최소 힙

11286번: 절대값 힙

1715번: 카드 정렬하기

2075번: N번째 큰 수

2014번: 소수의 곱 (★)

2696번: 중앙값 구하기 (★)