[Python]우선순위 큐, heapq

MEIN_FIGUR·2021년 8월 27일
2

Python_정리

목록 보기
8/8

우선순위 큐 (Priority Queue)


✔우선순위 큐란?

큐나 스택과 비슷한 자료형이지만, 각 원소들은 우선순위를 가지고 있다. 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 같은 우선순위를 가진다면, 먼저 들어온 원소를 처리한다.

우선순위 큐는 힙(heap)이라는 자료 구조를 통해 구현할 수 있다.

우선순위 큐는 최소한 두 가지 연산이 지원되어야 한다.

  • 하나의 원소를 우선순위를 지정하여 추가하는 함수(push)
  • 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 반환하는 함수(pop)

힙(Heap)이란?

완전 이진 트리(Complete Binary Tree)로, 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap), 작아야(Min Heap) 한다. 힙은 우선순위 큐를 구현하거나, 힙 정렬을 하는 데 사용된다. 루트 노드에 있는 값이 최대값, 혹은 최소값이며, 자식 노드들의 값의 위치는 기본적인 조건만 맞추면 된다.


Max Heap, Min Heap

https://chanhuiseok.github.io/posts/ds-4/ 사진 참조


✔우선순위 큐의 Push

  • 맨 끝 위치에 값을 저장
  • 부모 노드와 비교하며, 조건을 만족하는 지 확인
    • 만족하지 않는다면, 서로 위치를 변경

https://chanhuiseok.github.io/posts/ds-4/ 사진 참조


✔우선순위 큐의 Pop

  • 가장 우선순위가 높은 값을 삭제
  • 맨 끝의 노드를 비어있는 루트 노드로 끌어옴
  • 루트 노드의 자식 노드들과 값을 비교, 위치 변경
    • 위치를 만족할 때까지 자식 노드와 위치를 변경하며 올바른 위치까지 이동

https://chanhuiseok.github.io/posts/ds-4/ 사진 참조



📌파이썬에서의 우선순위 큐

파이썬에서는 우선순위 큐의 활용을 위해, 모듈을 제공하고 있다.


PriorityQueue

from queue import PriorityQueue

q = PriorityQueue() 
q1 = PriorityQueue(maxsize=10) # maxsize를 활용하면 크기 제한 가능

put

  • .put(item)
q.put(3) # 원소를 넣는 과정
q.put(4)
q.put(1)

q1.put((1, 'apple')) # (우선순위, 값)의 형태로 저장할 수도 있음

get

  • .get()
# 원소 삭제 및 반환
q.get() # 1
q1.get()[1] # (우선순위, 값)의 형태에서 값 반환



Heapq

자세한 내용은 https://docs.python.org/ko/3/library/heapq.html 참조

  • 최소 힙(Min Heap)의 구조
  • 모든 k에 대해 heap[k] <= heap[2*k+1] 또는 heap[k] <= heap[2*k+2] 만족
  • 가장 작은 요소가 heap[0]에 위치
  • 힙을 만들기 위해서는, 초기화된 리스트 []를 사용하거나, heapify를 통해 값이 들어있는 리스트를 힙으로 변환 가능
import heapq

hq = []

push

  • heapq.heappush(heap, item)
  • 힙의 형태를 유지하면서 item을 push
heapq.heappush(hq, 4)
heapq.heappush(hq, 1)
heapq.heappush(hq, 3)
heapq.heappush(hq, 7)

pop

  • heapq.heappop(heap)
  • 힙의 형태를 유지하면서 가장 작은 항목을 pop, 반환
  • 비어있으면 IndexError 발생
  • 반환하지 않고 접근하고 싶다면, heap[0] 활용
heapq.heappop(hq) # 1

heapify

  • heapify(x)
  • 리스트 x를 선형 시간으로 제자리에서 heap으로 변환
x = [4, 3, 1, 2, 5, 6]
print(x) # [4, 3, 1, 2, 5, 6]
heapq.heapify(x)
print(x) # [1, 2, 4, 3, 5, 6]
profile
Growing Developer

0개의 댓글