파이썬의 힙에서 엿보기

StackOverflow https://stackoverflow.com/questions/1750991

  •  20-09-2019
  •  | 
  •  

문제

Heapq Libs가 만든 파이썬 힙에서 엿보기의 공식적인 방법은 무엇입니까? 지금은 가지고 있습니다

def heappeak(heap):
  smallest = heappop(heap)
  heappush(heap, smallest)
  return smallest

그것은 틀림없이 그리 좋지 않습니다. 항상 그렇게 가정 할 수 있습니다 heap[0] 힙의 상단이 그것을 사용합니까? 아니면 기본 구현이 너무 많이 가정 될까요?

도움이 되었습니까?

해결책

예,이 가정을 할 수 있습니다. 선적 서류 비치:

힙은 배열입니다 heap[k] <= heap[2*k+1] 그리고 heap[k] <= heap[2*k+2] 모든 케이, 0에서 요소 계산. 비교를 위해, 존재하지 않는 요소는 무한한 것으로 간주됩니다. 힙의 흥미로운 속성은 그 것입니다 heap[0] 항상 가장 작은 요소입니다.

(그리고 아마도 아마도 peek 기능 : 필요하지 않습니다.)

다른 팁

Python 2.4 이상을 사용하는 경우 Heapq.nsmallest ()를 사용할 수도 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top