Python에서 우선순위 큐를 구현하는 방법(코드 포함)-파이썬 튜토리얼-php.cn

Python에서 우선순위 큐를 구현하는 방법(코드 포함)

不言

풀어 주다： 2018-10-11 14:17:17

앞으로

2803명이 탐색했습니다.

이 기사는 Python이 (코드를 사용하여) 우선 순위 대기열을 구현하는 방법에 대한 것입니다. 이는 특정 참조 값을 가지고 있으므로 도움이 필요할 수 있습니다.

1. 요구 사항

주어진 우선 순위로 요소를 정렬하고 각 팝 작업에 대해 가장 높은 우선 순위를 가진 요소를 반환할 수 있는 대기열을 구현하려고 합니다

2. 해결 방법

heapq 모듈을 사용하여

코드를 구현합니다. :

import heapq

#利用heapq实现一个简答的优先级队列
class PriorityQueue:
    def __init__(self):
        self._queue=[]
        self._index=0
    def push(self,item,priority):
        heapq.heappush(self._queue,(-priority,self._index,item))
        self._index+=1
    def pop(self):
        return heapq.heappop(self._queue)[-1]

class Item:
    def __init__(self,name):
        self.name=name

    def __repr__(self):
        return 'Item({!r})'.format(self.name)

if __name__ == '__main__':
    q=PriorityQueue()
    q.push(Item('foo'),1)
    q.push(Item('bar'),5)
    q.push(Item('spam'),4)
    q.push(Item('grok'),1)

    print(q.pop())
    print(q.pop())
    #具有相同优先级的两个元素，返回的顺序同它们插入到队列时的顺序相同
    print(q.pop())
    print(q.pop())

로그인 후 복사

실행 결과:

Item('bar')
Item('spam')
Item('foo')
Item('grok')

로그인 후 복사

위 코드의 핵심은 heapq 모듈의 사용에 있습니다. heapq.heapqpush() 및 heapq.heapqpop() 함수는 각각 _queue 목록에서 요소 삽입 및 제거를 구현하고 목록의 첫 번째 요소가 가장 낮은 우선순위를 갖도록 보장합니다. heappop() 메서드는 항상 [가장 작은] 요소를 반환하므로 이것이 대기열에서 올바른 요소를 팝하는 열쇠입니다. 또한, push 및 pop 연산의 복잡도는 O(logN)(여기서 N은 힙의 요소 수를 나타냄)이므로 N 값이 크더라도 이들 연산의 효율성은 매우 높습니다.

위 코드에서 큐는 튜플(-우선순위, 인덱스, 항목)로 구성됩니다. 우선순위에 음수 값을 취하는 목적은 대기열이 요소의 우선순위가 높은 것부터 낮은 것 순으로 배열되도록 하는 것입니다.

변수 인덱스의 기능은 동일한 우선순위를 가진 요소를 적절한 순서로 배열하는 것입니다. 지속적으로 증가하는 인덱스를 유지함으로써 요소는 대기열에 나타나는 순서대로 정렬됩니다. 인덱스의 역할을 설명하려면 다음 예를 살펴보세요.

코드:

class Item:
    def __init__(self,name):
        self.name=name

    def __repr__(self):
        return 'Item({!r})'.format(self.name)

if __name__ == '__main__':
    a=(1,Item('foo'))
    b=(5,Item('bar'))
    #下面一句打印True
    print(a<b)


    c=(1,Item('grok'))
    #下面一句会报错：TypeError: '<' not supported between instances of 'Item' and 'Item'
    print(c<a)


    d=(1,0,Item('foo'))
    e=(5,1,Item('bar'))
    f=(1,2,Item('grok'))
    #下面一句打印True
    print(d<e)
    #下面一句打印True
    print(d<f)

로그인 후 복사

위 내용은 Python에서 우선순위 큐를 구현하는 방법(코드 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!