내 시나리오는 다음과 같습니다. 선형 시간 min이나 연산에 의존하지 않고도 A * (Python에서)를 구현하고 싶다. 나는 가장 낮은 무게의 물품을 효율적으로 얻을 수 있도록 힙이 필요하다.해당 요소의 수정을 지원하는 힙?
즉각적인 답변은 'Easy! 나는 힙합을 사용할거야! ' 그렇다면 나는 삶이 거의 그렇게 간단하지 않다는 것을 발견했다. 이 전략은 A *의 중요한 점 중 하나에 대해 차선책이라고 밝혀졌습니다. 아이들을 생각할 때 이미 힙에있는 아이들의 점수를 때때로 업데이트해야합니다.
A *의 메모리가 조금이라도 부족한 사람에게는 요소를 가져 와서 무게를 수정하고 변경 사항을 반영하도록 힙을 수정하려는 것입니다.이 모든 것이 비선형 적 시간에 반영됩니다.
제안 사항?
복잡성 때문에 이항 또는 피보나치 힙을 사용해보십시오. 파이썬에는 둘 다 구현되지만 생산 등급 라이브러리는 존재하지 않는 것처럼 보입니다. 하지만 바이너리 또는 d-ary 힙은 실제로 더 빠르게 작동합니다. heapq 페이지에는 힙에 삽입하는 항목에 대한 참조를 유지하고 유효하지 않은 것으로 표시 한 다음 새 버전을 삽입하는 방법에 대한 업데이트 방법이 나와 있습니다. 업데이트 후에 힙 속성을 유지하는 더 빠른 알고리즘이 있습니다. 빠른 업데이트에 사용할 알고리즘에 대해 http://en.wikipedia.org/wiki/D-ary_heap을 찾으십시오.하지만 배열의 맨 위에 자체 힙을 구현해야 할 수도 있습니다.
heapq 또는 Queue.PriorityQueue의 힙 기능은 매우 유용하지 않습니다. A : 블로그에 호언 장담을 쓰거나 B : 직접 구현하십시오.
힙 유형을 실제로 구현할 수없는 정확한 이유 때문에 모든 힙 메서드에서 "요소에 대한 포인터"를 입력해야하는 정확한 이유 때문에 힙 유형을 구현해야합니다.
일반적으로 항목의 구조화되지 않은 컨테이너와 포인터에 대한 힙 (heaps of Items)의 조합으로 힙을 구현합니다. Item의 힙 위치에 대한 포인터를 유지하면 즉각적인 양방향 링크가 있습니다 : a) 힙 요소가 주어진 경우 (예 : extractMin에서 반환되거나 비교 중에) : 포인터를 참조 취소하면 귀하의 항목. b) 주어진 항목 (예 : 그래프 알고리즘의 인접성 목록을 통해) : 원하는 업데이트 기능에 포인터를 전달하십시오.
물론 이것은 공간 오버 헤드 (항목 당 2 개의 추가 포인터/정수)를 유발하지만 힙 구조 조정은 매우 저렴합니다 (전체 항목을 교체하는 대신 몇 개의 포인터를 바꿔 넣음). 추가 위성 데이터를 귀하의 항목에 추가하십시오.