최대 힙에서 최소 키를 삭제하는 방법은 무엇입니까?

Question

최대 힙에서 가장 낮은 정수를 삭제하는 HEAP-DELETE-MIN (Array) 함수를 구현해야합니다. 임씨는 기능 자체에 대해 묻지 않지만 누군가가 나를 도와주기 위해 의사 코드을 제공 할 수 있습니까? 큰 도움이 될 것입니다. 배열은 함수의 끝에서 최대 힙을 유지해야합니다.

Answer 1

기본적으로 배열에 저장된 암시 적 힙의 모든 리프 노드를 검색해야합니다. 상위 노드가 최대 힙 속성이어야하고 힙이 인덱스 n/2 이상에서 저장된다는 것을 알기 때문에 힙의 리프 노드가됩니다 (알고리즘 복잡도에 영향을주지는 않지만). 그래서 기본적으로 당신이해야 할 것은 다음

1) Search the array for the minimum element 
2) Place the last-inserted heap element in the position of the minimum element (essentially this is the delete) 
3) Upheap the replaced node to restore maximum heap property and correct storage of the heap in the array 

이 최소의 요소의 검색에 대한 O (N)를 취할 것입니다, 다음 O (1)에 대한 스위치, 그리고 마지막으로 O (N 로그)에 대한 격상한다. 전체적으로 이것은 선형 시간입니다. 근본적으로 당신이 할 수있는 최선의 방법입니다.

인덱스 작업에주의해야합니다. 2 * i는 노드 i의 왼쪽 자식이고 2 * i + 1은 배열 기반 힙에서 노드 i의 오른쪽 자식입니다 (배열의 0 번째 요소는 항상 비어 있고 힙의 루트는 인덱스 1에 있습니다.)