파이썬에는 최소 힙 데이터 구조가 내장되어 있습니까?

Question

파이썬은 2.7.3에서 최소 힙 데이터 구조가 내장되어 있습니까?

코드를 가져오고 싶지 않습니다.

내가 원하는

myheap = minheap(key=lambda x: x[1]) 
myheap.add(obj) 
o = myheap.pop() 

같은이 가능합니까?

Answer 1

파이썬은 다운로드 할 필요는 없지만, 여전히 수입에 가지고있는, heapq와 함께 제공됩니다.

파이썬은 import 문을 사용하지 않고 사용할 수있는 데이터 구조가 거의 없습니다. 귀하의 언어가 모든 표준 라이브러리를 모든 프로젝트의 메모리와 네임 스페이스에로드하게하고 싶습니까? 아무도 아직 언급되지 것대로 가 key=를 지원하지 않습니다,하지만 -

Answer 2

모두가 말한다처럼, heapq이 그것입니다! 따라서 key=이 지원되는 곳이면 어디서나 내부적으로 사용되는 좋은 오래된 DSU (decorate-sort-undecorate) 관용구로 넘어갈 필요가 있습니다 (heapq에 아예 없습니다. nlargest 및 nsmallest 제외). 나머지 모듈).

그래서 당신은 당신의 자신의 클래스의 예를 들면 키의 추가와 함께, heapq 기능을 래핑 할 수 있습니다

import heapq 

class MyHeap(object): 
    def __init__(self, key, data=()) 
     self.key = key 
     self.heap = [(self.key(d), d) for d in data] 
     heapq.heapify(self.heap) 

    def push(self, item): 
     decorated = self.key(item), item 
     heapq.heappush(self.heap, decorated) 

    def pop(self): 
     decorated = heapq.heappop(self.heap) 
     return decorated[1] 

    def pushpop(self, item): 
     decorated = self.key(item), item 
     dd = heapq.heappushpop(self.heap, decorated) 
     return dd[1] 

    def replace(self, item): 
     decorated = self.key(item), item 
     dd = heapq.heapreplace(self.heap, decorated) 
     return dd[1] 

    def __len__(self): 
     return len(self.heap) 

이 pushpop와 replace의 차이에 대한 https://docs.python.org/2/library/heapq.html을 참조하십시오 (다른 보조 기능에 의해 공급 표준 라이브러리 모듈 heapq).