Python의 우선순위 대기열
우선순위 대기열 큐의 각 데이터/값이 특정 우선순위를 갖는 추상 데이터 구조입니다. 예를 들어 항공사에서는 비즈니스 또는 일등석이라는 제목의 수하물이 나머지 수하물보다 먼저 도착합니다.
우선순위 큐는 다음 속성을 가진 큐의 확장입니다.
- 우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 대기열에서 제거됩니다.
- 두 요소의 우선순위가 동일한 경우 대기열의 순서에 따라 처리됩니다.
다양한 애플리케이션 컴퓨터 과학의 우선순위 대기열은 다음과 같습니다.
작업 스케줄링 알고리즘, CPU 및 디스크 스케줄링, 서로 다른 프로세스 간에 공유되는 리소스 관리 등
우선순위 대기열과 대기열의 주요 차이점:
- 대기열에서는 가장 오래된 요소가 먼저 대기열에서 제거됩니다. 우선순위 큐에서는 우선순위가 가장 높은 요소가 큐에서 제외됩니다.
- 요소가 우선순위 대기열에서 팝되면 얻은 결과는 오름차순 또는 내림차순으로 정렬됩니다. 반면, 단순 대기열에서 요소가 팝되면 결과에서 데이터의 FIFO 순서가 얻어집니다.
아래는 간단한 구현 우선순위 큐의.
파이썬
# A simple implementation of Priority Queue> # using Queue.> class> PriorityQueue(> object> ):> > def> __init__(> self> ):> > self> .queue> => []> > def> __str__(> self> ):> > return> ' '> .join([> str> (i)> for> i> in> self> .queue])> > # for checking if the queue is empty> > def> isEmpty(> self> ):> > return> len> (> self> .queue)> => => 0> > # for inserting an element in the queue> > def> insert(> self> , data):> > self> .queue.append(data)> > # for popping an element based on Priority> > def> delete(> self> ):> > try> :> > max_val> => 0> > for> i> in> range> (> len> (> self> .queue)):> > if> self> .queue[i]>> self> .queue[max_val]:> > max_val> => i> > item> => self> .queue[max_val]> > del> self> .queue[max_val]> > return> item> > except> IndexError:> > print> ()> > exit()> if> __name__> => => '__main__'> :> > myQueue> => PriorityQueue()> > myQueue.insert(> 12> )> > myQueue.insert(> 1> )> > myQueue.insert(> 14> )> > myQueue.insert(> 7> )> > print> (myQueue)> > while> not> myQueue.isEmpty():> > print> (myQueue.delete())> |
산출:
12 1 14 7 14 12 7 1
위 코드에서 삭제의 시간 복잡도는 O(n)입니다. ㅏ 더 나은 구현 사용하는 것입니다 바이너리 힙 이는 일반적으로 우선순위 큐를 구현하는 데 사용됩니다. Python은 다음을 제공합니다. 힙 도서관에서도요.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))
