2010. 8. 12. 23:40

< 힙 트리 >

*************************************************************************************

부모가 자식보다 열등 or 우등


부모가 가지고 있는 키가 자식이 가지고있는 킷값보다 커야한다.


힙의 종류


Up Heap(MAX Heap) 가장 큰 수를 아래서부터 위로


Down Heap가장 작은수를 루트로 넣고 비교해서 자리를 찾는 방법


int GetPa(int me)

{

 return (me-1)/2 // 부모 구하는 방법

}


int GetLc(int me)

{

 return 2*me+1; // 자식 구하는 방법 (Lc)

}

*************************************************************************************

< 힙의 최악의 경우 >


10

15

2

7

8

6

4

(높이)

0

1

1

2

2

2

2


20 * 0 + 21 * 22 * 2 + ... + 2h * h

 <= 2h * h + 2h * h + ... + 2h * h

  = h2 * 2h = (logn)2 * 2log2n = n*(logn)2

'COMPUTER TECH > C, C++' 카테고리의 다른 글

이진탐색트리  (0) 2010.08.12
퀵 정렬  (0) 2010.08.12
힙 트리  (0) 2010.08.12
피보나치 수열  (0) 2010.08.12
MyVector만들기  (0) 2010.08.12
최단경로 알고리즘  (0) 2010.08.09
Posted by ... XJAPAN

댓글을 달아 주세요