어느 것이 밸런스 이진 탐색 트리 또는 max 요소를 추출하기위한 최대 힙인가? 균형 잡힌 <code>BST</code> 이후

Question

는 O(log(n)) 시간이 (I 모두 찾아 최대의 요소를 삭제 의미 추출하여) 최대 를 추출한다 걸릴 것이다. 한편, Max-heap은 최대 요소를 추출 할 때 시간이 O(log(n)) 일 것입니다.

그들 중 누군가가 추출 - 최대 작업에 다른 이상 가장자리를 절단했다합니까? 데이터 구조를 생각하면

Answer 1

, 당신은 시간과 공간의 계정에 자신의 복잡성을해야합니다. 여기에 공간이 동일합니다, 그래서 시간에 집중하자

균형 BST를 :

균형 BST는 시간 = O (LG 전자, n은) 모든 작업이 O (LG 전자 n)이 시간에 실행 ⇒ 유지한다.

맥스 힙 :

최대 O (1), 그 시간 복잡도는 동일하다는 의미 최대 O (엑스 N)를

삭제 찾는다.

... 최대 힙 또는 이진 트리가 잘 맞는 :

또한이 answer을 읽고, 당신은 같은 결론을 그립니다.

그러나 이미 구성된 BST의 균형은 O (n) 작업 (Balancing a BST)입니다. 그래서 내가 그렇게해야한다면, 나는 최대의 힙을 얻을 것이다. 1, 2 : 고급 사용에 대한

는

---

_{소스 Which data structure to use for accessing min/max in constant-time?을 참조하십시오.}