Heapop() not invariant

Question

heapq.heappop (대기열)을 사용할 때 목록의 첫 번째 항목이 팝되지만 나머지 목록은 수정됩니다. 이 문제를 어떻게 방지 할 수 있습니까? [(1, 2 ', Z'), (1, 3, 't'

큐 : PQ ('R'이하 'O'을 함유 한 참고 튜플)

이 내 디버그 출력 (2, 6, 'f')]

대기열 이전 팝업 : [(1, 2, 'z')], (2, 4, 'r'), (1, 3 ', t')는, (2, 4, R '은'), (2, 5, 'O')가 (2, 6, 'F')]

priority, counter, node = heapq.heappop(queue) 

상품 반품 : (1, 2, 'z') 큐 이후 대기열 : ((1, 3, 't'), (2, 5, 'o'), (2, 4, 'r'), , 'f')]

카운터는 노드의 초기 추가가 대기열 [0]에 더 가깝도록해야합니다.

pop 이후의 큐는 heap [0]을 팝하는 것이 아니라 'r'을 포함하는 튜플 앞에 'o'가 포함 된 튜플을 재배치하고 놓습니다. 우선 순위는 같지만 (2), 카운터는 각각 5와 4이므로 잘못된 순서로 재정렬됩니다.

Inst heappop()은 힙 [0]을 반환하고 다른 모든 것을 대기열로 이동한다고 가정합니다. 이 재배치를 어떻게 막을 수 있습니까?

Answer 1

이것은 예상되는 정상적인 힙 동작입니다. 힙의 임의의 요소 사이에 묵시적인 순서는 없습니다. 유일한 불변량은 각 노드가 하위 노드보다 적다는 것입니다. (1,3,'t') 요소가 팝업되면 (2,4,'r')이 이전 루트의 두 자식 중 작은 수이기 때문에 새 루트로 선택됩니다. (2,5,'o')에 대한 해당 순서는 그 시점까지는 관련이 없습니다. 즉, 루트는 힙의 인덱스를 기반으로 값에 대해 말할 수있는 유일한 요소입니다.

언제나 완전히 정렬 된 순서로 목록을 원하면 모듈이 아니라 heapq 모듈이 필요합니다. 물론 성능은 훨씬 나빠질 것입니다.