파이썬 우선순위 큐 (Priority Queues)

 

 

 

 

우선순위 큐(Priority Queues)

• 큐가 FIFO(선입선출) 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져 나가는 방식
• 같은 우선순위를 가지고 있을 경우엔, 먼저 들어온 원소가 먼저 나간다.
• 즉, 우선순위 큐는 내부적으로 데이터를 정렬된 상태로 보관하는 메커니즘이 존재한다.
• 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하며, 이 중에서 heap 자료구조 (heapq 모듈)를 통해 구현하는 것이 가장 효율적
• 우선순위 큐의 구현 방식(2가지 방법)
  • 1. Enqueue할 때 우선순위 순서를 유지하며 enqueue
  • 2. Dequeue할 때 우선순위가 높은 것을 선택하여 dequeue
  • 2번은 deque할 때마다 모든 원소를 다 탐색해야 하므로 1번이 더 적절하다.
• 시간 복잡도
  • 우선순위 큐의 삽입/삭제 : O(log n)
• 우선순위 큐의 사용
  • queue 내장 모듈에서 PriorityQueue를 임포트해서 사용
  • from queue import PriorityQueue
  • 우선순위 큐의 원소 추가: put()
  • # 우선순위 큐의 원소 추가: put()

    que.put(4)

    que.put(1)

    que.put(7)
  • 단순 오름차순이 아닌 다른 기준으로 원소가 정렬되기 원한다면, (우선순위, 값)의 튜플의 형태로 데이터를 추가하고 제거하면 된다.
  • que.put((3, 'Apple'))

    que.put((1, 'Banana'))

    que.put((2, 'Cherry'))

    
    

    print(que.get()[1])  # Banana

    print(que.get()[1])  # Cherry

    print(que.get()[1])  # Apple
  • 우선순위 큐의 원소 삭제: get()
  • # 우선순위 큐의 원소 삭제: get()

    print(que.get()) # 1

    print(que.get()) # 4

    print(que.get()) # 7
  • 우선순위 큐의 크기 확인: qsize()
  • print(que.qsize())
  • 우선순위 큐가 비었는지 확인: empty()
  • print(que.empty()) # true/false
  •  우선순위 큐가 가득 찼는지 확인: full()
  • 우선순위 que 생성시 설정한 maxsize와 일치할 경우 True 반환, 그렇지 않으면 False 반환
  • print(que.full()) # true/false

 

 

 

---

참고

 

 

https://www.daleseo.com/python-priority-queue/

https://cocobi.tistory.com/204