[PYTHON] 어떻게 파이썬의 heapq에서 감소 키 기능을 구현할 수 있습니까?

어떻게 파이썬의 heapq에서 감소 키 기능을 구현할 수 있습니까?

O (log n)에서 감소 키 기능을 실현하는 것이 가능하다는 것을 알고 있지만 어떻게 알 수 있습니까?

해결법

1. ==============================

   1."감소 키"를 효과적으로 구현하려면 "이 요소를 감소시키고 힙 조건이 복원 될 때까지이 요소를 하위 요소로 스왑하십시오."기능에 액세스해야합니다. heapq.py에서 이것은 _siftdown이라고 불립니다 (그리고 INcrementing과 비슷한 _siftup). 따라서 좋은 소식은 함수가 있다는 것입니다 ... 나쁜 소식은 이름이 밑줄로 시작하여 "내부 구현 세부 정보"로 간주되며 응용 프로그램 코드 (다음 릴리스의 표준 라이브러리는 이러한 "내부"를 사용하여 주변 환경을 변경하고 코드를 깨뜨릴 수 있습니다.

   "감소 키"를 효과적으로 구현하려면 "이 요소를 감소시키고 힙 조건이 복원 될 때까지이 요소를 하위 요소로 스왑하십시오."기능에 액세스해야합니다. heapq.py에서 이것은 _siftdown이라고 불립니다 (그리고 INcrementing과 비슷한 _siftup). 따라서 좋은 소식은 함수가 있다는 것입니다 ... 나쁜 소식은 이름이 밑줄로 시작하여 "내부 구현 세부 정보"로 간주되며 응용 프로그램 코드 (다음 릴리스의 표준 라이브러리는 이러한 "내부"를 사용하여 주변 환경을 변경하고 코드를 깨뜨릴 수 있습니다.

   경고 선행을 무시할지 여부를 결정하는 것은 당신에게 달려 있습니다. O (로그 N) 선별 대신 O (N) heapify를 사용하거나 선별 기본 요소를 공용 부분으로 공개하도록 heapq의 기능 일부 또는 전부를 다시 구현하십시오. 인터페이스의 ". heapq의 데이터 구조는 문서화되어 공개 (목록 만)되어 있기 때문에 최선의 선택은 아마 부분적으로 다시 구현하는 것일 것입니다 - heapq.py의 sifting 함수를 응용 프로그램 코드로 복사하십시오.

2. ==============================

   2.heapq 문서에는이를 수행하는 방법에 대한 항목이 있습니다.

   heapq 문서에는이를 수행하는 방법에 대한 항목이 있습니다.

   그러나, 나는 정확히 이것을 수행하는 힙 패키지를 작성했다 (heapq 주위의 래퍼이다). 따라서 pip 또는 easy_install을 사용하면 다음과 같은 작업을 수행 할 수 있습니다.

   pip install heap
   

   그런 다음 코드 작성

   from heap.heap import heap
   
   h = heap()
   
   h['hello'] = 4 # Insert item with priority 4.
   
   h['hello'] = 2 # Update priority/decrease-key has same syntax as insert. 
   

   그것은 꽤 새롭다. 그래서 버그로 가득 할지도 모른다.

3. ==============================

   3.Decrease-key는 많은 알고리즘 (Dijkstra 's Algorithm, A *, OPTICS)에서 필수적인 연산이며, 파이썬의 기본 우선 순위 큐가 왜 지원하지 않는지 궁금합니다.

   Decrease-key는 많은 알고리즘 (Dijkstra 's Algorithm, A *, OPTICS)에서 필수적인 연산이며, 파이썬의 기본 우선 순위 큐가 왜 지원하지 않는지 궁금합니다.

   불행히도 math4tots 패키지를 다운로드 할 수 없었습니다.

   그러나 Daniel Stutzbach가이 구현을 찾을 수있었습니다. 파이썬 3.5에서 완벽하게 작동했습니다.

   hd = heapdict()
   hd[obj1] = priority
   hd[obj1] = lower_priority
   # ...
   obj = hd.pop()
   

4. ==============================

   4.우선 순위 큐로 힙 (heap)을 사용한다고 가정 해 봅시다. 여기에는 문자열로 표현되는 많은 작업이 있으며 각 작업에는 키가 있습니다. 구체적으로 말하자면, task_list = [[7, "do laundry"], [3, "clean room"], [6, "calls parents"]] 여기서 task_list의 각 태스크는 우선 순위와 설명이있는 목록입니다. heapq.heapify (task_list)를 실행하면 배열이 힙 불변성을 유지하게됩니다. 그러나 "do laundry"의 우선 순위를 1로 변경하려는 경우 힙을 통한 선형 스캔없이 힙에 "세탁을 수행"하는 위치를 알 수 없습니다 (따라서 로그 시간에 reduce_key를 수행 할 수 없음) . 참고 reduce_key (heap, i, new_key)는 힙에서 변경할 값의 인덱스를 알아야합니다.

   우선 순위 큐로 힙 (heap)을 사용한다고 가정 해 봅시다. 여기에는 문자열로 표현되는 많은 작업이 있으며 각 작업에는 키가 있습니다. 구체적으로 말하자면, task_list = [[7, "do laundry"], [3, "clean room"], [6, "calls parents"]] 여기서 task_list의 각 태스크는 우선 순위와 설명이있는 목록입니다. heapq.heapify (task_list)를 실행하면 배열이 힙 불변성을 유지하게됩니다. 그러나 "do laundry"의 우선 순위를 1로 변경하려는 경우 힙을 통한 선형 스캔없이 힙에 "세탁을 수행"하는 위치를 알 수 없습니다 (따라서 로그 시간에 reduce_key를 수행 할 수 없음) . 참고 reduce_key (heap, i, new_key)는 힙에서 변경할 값의 인덱스를 알아야합니다.

   각 하위 목록에 대한 참조를 유지 관리하고 실제로 키를 변경하더라도 여전히 로그 시간에이를 수행 할 수 없습니다. 목록은 변경 가능한 객체에 대한 참조 일 뿐이므로 작업의 원래 순서를 기억하는 것과 같은 작업을 시도 할 수 있습니다. (이 경우 "do laundry"이 원래 task_list의 0 번째 작업이었습니다) :

   task_list = [[7, "do laundry"], [3, "clean room"], [6, "call parents"]]
   task_list_heap = task_list[:] # make a non-deep copy
   heapq.heapify(task_list_heap)
   # at this point:
   # task_list = [[7, 'do laundry'], [3, 'clean room'], [6, 'call parents']]
   # task_list_heap = [3, 'clean room'], [7, 'do laundry'], [6, 'call parents']]
   # Change key of first item of task_list (which was "do laundry") from 7 to 1.
   task_list[0][0] = 1
   # Now:
   # task_list = [[1, 'do laundry'], [3, 'clean room'], [6, 'call parents']]
   # task_list_heap = [3, 'clean room'], [1, 'do laundry'], [6, 'call parents']]
   # task_list_heap violates heap invariant at the moment
   

   그러나 heapq._siftdown (task_list_heap, 1)을 호출하여 로그 시간에 heap invariant를 유지해야합니다 (heapq.heapify는 선형 시간 임).하지만 불행히도 task_list_heap에서 "do laundry"인덱스를 알지 못합니다 이 경우 heap_index는 1입니다.

   그래서 우리는 힙을 구현할 필요가 있습니다. 각 객체의 heap_index를 추적합니다. 예를 들어, 힙에 대한리스트와 각 객체를 힙 /리스트의 인덱스에 매핑하는 딕트 (힙 위치가 스왑 될 때마다 업데이트되어 각 스왑에 일정한 요소를 추가 함)를 가질 수 있습니다. 당신은 heapq.py를 읽고 절차가 간단하므로 스스로 구현할 수 있습니다. 그러나 다른 사람들은 이미 이런 종류의 HeapDict를 구현했습니다.

from https://stackoverflow.com/questions/1465662/how-can-i-implement-decrease-key-functionality-in-pythons-heapq by cc-by-sa and MIT license