파이썬에서 삽입시 값으로 요소를 정렬하는 데이터 구조

Question

삽입시 값별로 요소 (id, value)를 정렬하는 큐 구조가 필요합니다. 또한, 가장 높은 값을 가진 요소를 제거 할 수 있어야합니다. 이 구조체는 스레드로부터 안전 할 필요가 없습니다. 자바에서는 PriorirtQueue에 해당합니다.

파이썬에서 어떤 구조를 사용해야합니까? 하나의 장난감 예제를 제공 할 수 있습니까?

Answer 1

heapq 모듈을 사용할 수 있습니다. 워드 프로세서

:

이 모듈 힙 큐 알고리즘도 우선 순위 큐 알고리즘이라고도 의 구현을 제공한다.

Answer 2

파이썬 (정말 heapq에 대한 스레드 안전 래퍼 인) something similar이 있습니다 대신 최대 규모의

from Queue import PriorityQueue 

q = PriorityQueue() 
q.put((-1, 'foo')) 
q.put((-3, 'bar')) 
q.put((-2, 'baz')) 

, 당신은 q.get()와 함께 가장 낮은 수를 얻을 수 있습니다 :

>>> q.get() 
(-3, 'bar') 

제외 어가 마음에 들지 않으면 방법을 재정의 할 수 있습니다.

class PositivePriorityQueue(PriorityQueue): 
    def _get(self, heappop=max): 
     return heappop(self.queue) 

Answer 3

당신이 찾고있는 것이 heapq 라이브러리에서 찾을 수 있다고 생각합니다. http://docs.python.org/2/library/heapq.html :

Heap elements can be tuples. This is useful for assigning comparison values (such as task priorities) alongside the main record being tracked: 

>>> import heapq 
>>> 
>>> h = [] 
>>> heappush(h, (5, 'write code')) 
>>> heappush(h, (7, 'release product')) 
>>> heappush(h, (1, 'write spec')) 
>>> heappush(h, (3, 'create tests')) 
>>> heappop(h) 
(1, 'write spec') 

원하는 동작입니까?

Answer 4

heapq은 우선 순위 대기열을 사용하지만 최소 힙이므로 값을 음수로 만들어야합니다. 또한 정렬은 왼쪽에서 오른쪽으로 수행되므로 id 초를 입력해야합니다.