우선순위 큐 구현 (PriorityQueue, Heap)

오늘은 우선순위 큐 구현에 대해 알아보겠습니다!

 

# 우선순위 큐란?

일반적인 큐(queue) 구조는 선입 선출인 FIFO(First In, First Out) 방식으로 작동합니다! 

https://hipposdata.tistory.com/11

스택(Stack), 큐(Queue), 덱(Deque)

하지만 높은 우선순위(제일 큰 값, 작은 값 등)을 기준으로 자료를 꺼낼때, 매번 모든 자료의 우선순위를 계산해야하는데욥 

이를 쉽게 해결할 수 있는 데이터 구조가 우선순위 큐입니다! 

우선순위 큐 구조에서는 자료를 꺼낼 때, 우선순위가 높은 요소(제일 큰 값, 작은 값 등)가 먼저 처리됩니다! 

 

# Python 구현

Python을 이용하여 구현시 두가지 방법이 존재합니다!

1. PriorityQueue

2. heapq

 

 

1. PriorityQueue

from queue import PriorityQueue

que = PriorityQueue() # 생성

print(type(que)) # <class 'queue.PriorityQueue'>

#함수

# 원소 추가 - 원소 하나씩 추가 가능

que.put(1)

que.put(3)

que.put(5,7) # 동작X

# 꺼내기

print(que.get()) # 1

print(que.get()) # 3

print(que.get()) # 5

print(que.get()) # 5

# 큐 사이즈 확인

print(que.qsize()) # 0

# 비었는지 확인

print(que.empty()) # True

 

2. heapq

힙(Heap) 데이터 구조 이용

힙 구조에서 가장 작은 값은 항상 루트 노드에 위치하므로,

우선순위 큐에서 가장 작은 값을 선택할 때는 루트 노드가 꺼내지는 식으로 동작합니다!

import heapq

lst = [] # 빈리스트

# 함수

# 원소 추가 - 원소 하나씩 추가 가능

heapq.heappush(lst,1) # 넣을 리스트, 넣을 값 - 원소 하나씩

heapq.heappush(lst,3)

heapq.heappush(lst,5)

print(lst) # [1, 3, 5]

# 꺼내기 - 작은 값부터 꺼내짐

heapq.heappop(lst) # 1 꺼내짐 / print(heapq.heappop(lst)) 출력시 1 반환

print(lst) #[3, 5] 꺼내지고 남은 리스트

lst = [6,5,4,3,2,1,0]

heapq.heapify(lst) # 최소 힙(Min Heap) 구조로 변환

print(lst) # [0, 2, 1, 3, 5, 6, 4]

 

요런 구조로 반환됩니다!

        0
       /  \
     2    1
    /  \   /  \
  3   5 6   4

 

 

 

2-1 heapq 최댓값부터 꺼내기

원래 우선순위 큐는 최솟값 순서대로 꺼내지는데욥 최댓값 순서대로 꺼내지도록 우선순위 기준을 변경할 수 있습니다

변경 과정 

리스트 값 음수 변환 -> 리스트를 힙구조로 변환 -> 출력

import heapq

lst = [] # 빈리스트

# 함수

# 원소 추가 - 원소 하나씩 추가 가능

heapq.heappush(lst,1) # 넣을 리스트, 넣을 값 - 원소 하나씩

heapq.heappush(lst,3)

heapq.heappush(lst,5)

lst = list(map(lambda x: x * -1, lst)) # 음수로 변경 ( 최대 힙(max heap)구조로 변경되니 주의)

print(lst) # [-1, -3, -5]

heapq.heapify(lst) # 힙 구조로 변환: 최대 힙(max heap)구조 -> 최소 힙(min heap)구조

print(lst) # [-5, -3, -1]

# 꺼내기 - 작은 값부터 꺼내짐

print(-heapq.heappop(lst)) # - 붙여서 5출력 -5 꺼내짐

print(lst) #[-3, -5] 꺼내지고 남은 리스트

 

# PriorityQueue, heapq 차이점

 

PriorityQueue -> 객체 자체가 우선순위 큐 형태
heapq   -> 리스트 객체를 대상으로 우선순위 큐 구현 함수 제공 

 

# 관련문제

백준 1927: 최소 힙

https://www.acmicpc.net/problem/1927

 

백준 11279: 최대 힙

https://www.acmicpc.net/problem/11279

 

백준 11286 : 절댓값 힙

https://www.acmicpc.net/problem/11286