[알고리즘] heap 관련 정리

Heap properties

min-heap: parent ≤ child
max-heap: parent ≥ child
for all node N, N[i]가 모든 힙 properties를 만족해야하고 완전이진트리 구조여야한다.

Heap procedures

1.Max heapify
-O(lgn)
-한쪽 서브트리만 max-heap구조를 만듬
2.Build-Max-Heap
-O(n)
-i= (n/2 -> 1) 까지 max-heapify를 수행
3.HeapSort()
-O(nlgn)
-n-1번 maxheapify와 swap을 진행하여 정렬

Max-heapify

파라메터로 들어오는 배열 A를 기준으로 왼쪽자식 Left[i]와 오른쪽 자식 right[i]를 Max-heap이라고 가정해야함
->그래야 max-heap구조가 깨지지않음

sudo code로는
if l<=heapsize and A[l]>A[i]
	largest <- l
else largest <-i
if r<=heapsize and A[r]>A[largest]
	largest <-r
if largest != i
	exchange A[i]<->A[largest]
    Max-heapify(A,largest)

결론적으로 원래 Maxheap구조가 아니면 맥스힙 구조가 유지되지 않음
시간복잡도로는 재귀로 트리 높이만큼이라고 추정할 수 있고 heap은 완전 이진트리이므로 O(lgn)으로 Guess 할 수 있다.

전체 노드개수 n max= 1+2+4+~+2^h = 2^(h+1) -1
루트노드의 왼쪽 서브트리 노드개수 L max = 1+2+4+~~+2^(h-1)=2^h -1
Lmax/nmax=2/3 이므로 maxheapify의 T(n)<=T(2n/3)+O(1)
따라서 높이가 log3/2의n이므로 높이가 곧 시간복잡도니 O(lgn)임

Build-Max-Heap

sudocode로는

Build-Max-Heap(A)
	heap-size[A]<-length[A]
    for 1<-length[A]/2
    	Max-Heapify(A,i)

#n/2부터 1까지 for문으로 리프노드 제외하고 max heapify돌리면 Max-heap 만들 수 있음

시간복잡도

저번에 구한 heap 또는 완전이진트리구조에서 높이 h에 따른 높이h 최대 노드의 개수 = n/2^(h+1)를 통하여

시간 복잡도는 O(n)으로 구할 수 있다.
사실 여기식에서 시그마돌릴때 lgn까지가 아니라 lgn에서 0까지로 해야하는데 결과는 같아서 그냥 편하게 강의자료에서 식을 잡은 것 같다.

HeapSort

알고리즘 자체는

1. build max heap을 통해 배열을 maxheap 구조로 만든다. ->O(n)
2. a[i]<->a[1] 교환한다. -> 리프노드 맨끝이 제일 큰수가됌 -> O(1)
3. heapsize를 하나 줄인다.
4. maxheapify로 다시 A[1]을 max값으로 만든다 -> O(lgn)
5. 총 n-1번 반복
   O(n) + O(lgn)*O(n) = O(nlgn)

sudocode

Heapsort(A)
	buildmaxheap(A)
    for i in range(len(A), 1, -1):
    	swap(A[0], A[i-1])
    	heap_size -= 1
    	max_heapify(A, 1)