나는 최대 힙 중간에서 특정 요소를 제거하는 것과 관련된 스카이 라인 문제를 해결하는 알고리즘을 구현하려고합니다. 내가 현재하는 방식은 maxheap.remove(index)이지만, 나는 heapify(maxheap)으로 연락을 취해야한다. 그렇지 않으면 주문이 취소된다. 나는 자바에서 당신이 treemap 같은 것을 사용할 수 있음을 알고있다. 어쨌든 파이썬에서 O (n) 시간이 걸리는 두 개의 개별 메소드를 호출하는 것보다 효율적으로 수행 할 수 있습니까?파이썬에서 힙 속성을 잃지 않고 힙에서 특정 요소를 제거하는 방법은 무엇입니까?
나는 각 요소를 무시할지 여부를 나타내는 플래그가있는 데이터 구조로 만들었을 것이다. 힙합 할 때, 플래그가 지정된 요소 인 경우 다시 팝업됩니다. 이것은 매우 쉽고, 명백하며, 힙이 내부적으로 어떻게 작동하는지 알지 못합니다. 예를 들어, 힙에 실제로 요소가있는 위치를 알 필요가 없습니다.
이 방법의 단점은 플래그가 지정된 요소가 시간이 지남에 따라 누적되는 경향이 있다는 것입니다. 때로는 필터를 걸러 내고 heapify 할 수 있습니다.
이 솔루션으로는 충분하지 않은 경우 Python에서 btree 구현을 찾아야합니다. 그것은 자바에서 익숙한 트리 맵처럼 동작합니다.
힙에서 임의의 항목을 제거하는 것은 힙에 항목이있는 위치를 알면 O (로그 n) 작업입니다. 이 알고리즘은 다음과 같습니다
는Move the last item in the heap to the position that contains the item to remove.
Decrement heap count.
If the item is smaller than its parent
bubble it up the heap
else
sift it down the heap
주요 문제는 힙 항목의 위치를 찾는 입니다. 당신이 언급했듯이, 당신이 더 많은 정보를 유지하지 않는다면 그렇게하는 것이 O (n) 연산입니다.
효율적인 솔루션은 항목 키가 들어있는 사전을 만들고 그 값이 힙에있는 해당 항목의 색인입니다. 당신은 그러나 사전을 유지해야한다 : 당신은 힙에 항목을 삽입 할 때 변경할 때마다 당신이
사전을 사용하면 힙의 항목 위치에 O (1) 액세스 권한이 있으며 O (log n)에서 제거 할 수 있습니다.
예, 구현 방법에 따라 색인 또는 포인터가있는 경우보다 효율적인 방법이 있습니다.
제거해야하는 색인 / 포인터의 번호를 가장 큰 자식으로 바꾸고 자식이없는 노드에 도달 할 때까지 반복적으로 프로세스를 반복하십시오 (가장 큰 자식 등으로 자식 바꾸기 등). 쉽게 제거 할 수 있습니다.
이 알고리즘의 복잡도는 O (log n)입니다.
당신은 힙의 어떤 구현을 참조합니까? 힙 요소에 대한 명시 적 액세스를 나타내는'remove' 연산자가 포함되어 있으면'priority change '도 포함될 수 있습니다. – MBo
@MBo Python에서 명백한 구현은 표준 라이브러리에있는 heapq이다. – btilly