정렬되지 않은 배열에서 이진 힙을 생성하기위한 시간 복잡도

Question

상향식 힙 구조를 사용하는 정렬되지 않은 배열에서 이진 힙을 생성하는 데 소요되는 시간이 O (n) 인 이유를 설명 할 수 있습니까?

:

은 (자신의 설명을 이해하지 못하고 아직도 내가 내부 노드에 대한 경로의 크기의 총합이 힙을 구성하는 2N-1 동안 토마스 굿 리치 책에서 찾았지만 솔루션은 지금까지 발견) 감사.

Answer 1

정상 축적 HEAP 절차는 다음과 같이 구현 h는 나무의 높이이고, 거기에 은 실행 시간 O (nh)를 만드는 O (n) 호출입니다. h = lg n을 고려하면, BUILD-HEAP 절차는 O (ng n) 시간이 걸린다 고 말할 수 있습니다.

더 엄격한 분석을 위해 대부분의 노드의 높이가 작다는 것을 알 수 있습니다. 실제로 모든 높이 h에서 유도로 쉽게 증명할 수있는 대부분의 CEIL (n/(2^h +1)) 노드가있을 수 있습니다. 그래서, BUILD-HEAP의 실행 시간을 같이 쓸 수있다 지금

lg n      lg n 
∑ n/(2^h+1)*O(h) = O(n* ∑ O(h/2^h)) 
h=0      h=0 

,

이

∞ 
∑ k*x^k = X/(1-x)^2 
k=0    
       ∞ 
Putting x=1/2, ∑h/2^h = (1/2)/(1-1/2)^2 = 2 
       h=0  

따라서, 실행 시간이되고,

이

lg n      ∞ 
O(n* ∑ O(h/2^h)) = O(n* ∑ O(h/2^h)) = O(n) 
h=0      h=0 

그래서,이주는 O (n)의 실행 시간.

N.B. 분석은 this에서 가져 왔습니다.

Answer 2

체크 아웃 위키 피 디아 :

힙을 만들기 : 힙 연속 삽입에 의해 구축 될 수있다. 이 방법은 각 삽입에 O (log n) 시간이 걸리고 n 개의 요소가 있기 때문에 O (n log n) 시간이 필요합니다. 그러나 이것이 최적의 방법은 아닙니다. 최적의 방법은 shape 속성을 고려하여 요소를 임의로 이진 트리에 배치하는 것으로 시작됩니다. 그런 다음 가장 낮은 레벨에서 시작하여 위쪽으로 이동하여 힙 특성이 복원 될 때까지 삭제 알고리즘에서와 같이 각 하위 트리의 루트를 아래로 이동하십시오. 여기

BUILD-HEAP(A) 
heap-size[A] ← length[A] 
    for i ← length[A]/2 downto 1 
    do HEAPIFY(A, i) 

HEAPIFY 절차가 O (H) 시간이 걸리고, 여기서, 정렬되지 않은 배열에서 이진 힙을 발생

http://en.wikipedia.org/wiki/Binary_heap