추출 - 분 런타임은 무엇이며 그 이유는 무엇입니까?

Question

힙에서 추출 - 분이 O (lg n) 걸리는 이유는 무엇입니까?

Answer 1

가 참조 :

• 첫째, 마지막 수준의 마지막 요소와 힙의 루트를 대체 : https://en.wikipedia.org/wiki/Binary_heap#Extract 몇 즉

  , 세 단계를 수행하십시오. 그것은 O (1)에 대해 수행됩니다.

• 둘째, 새 루트를 자식 (여전히 O (1))과 비교하십시오. 모든 것이 정상이면, 끝났어!
• 이제 까다 롭습니다. 새로운 루트가 더 큰 경우 (우리는 당신이 그것의 아이들 중 하나보다 위에 최소를 가지고 있다고 생각합니다), 그들을 바꾸십시오! 이제 (아마도) 당신은 아이의 하위 트리에서 똑같은 문제가 있습니다. 하위 트리 안의 2 ~ 3 단계를 반복하십시오! 이 아닌은 한 레벨 아래로 내려갈 때마다 트리의 레벨 수보다 더 많은 횟수를 반복해야합니다. 균형 이진 트리에는 O (Ng N) 레벨이 있습니다. 참고 : 루트가 둘 다 자식보다 크면 작은 루트로 바꿉니다.