힙구조에 대해 설명해보세요.

① 뿌리노드를 제외한 각 내부노드는 또는 이다. (즉, 키 값은 오름차순이거나 내림차순이다.)

② 마지막 왼쪽 결합 노드들의 레벨을 제외한 다른 모든 레벨들은 완전 이진트리를 형성한다. (즉, 레벨 포화 상태 : saturated status on level)

algorithm upHeap(Position v):

while (not isRoot(v)) and key(parent(v))>key(v) do

swapItems(v.parent(v));

v<-parent(v);

algortihm downHeap(Position v):

while not (isExternal(leftChild(v)) and isExternal(rightChild(v)) do

if isExternal(rightChild(v)) then v<-leftChild(v)

else if key(leftChild(v))<=key(rightChild(v))

then v<-leftChild(v) else v<-rightChild(v);

if key(parent(v)) > key(v) then swapItems(v,parent(v))

else break;

1 2 3 4 5 6 7 8

H E A P S O R T //중간지점인 p(4번째 인덱스)에서 시작

^ ^ //그의 자식은 (왼쪽 자노드 인덱스8)T>P이기 때문에 교환

H E A T S O R P //A(3번째 인덱스)로 계속되며 A의 왼쪽 자노드는 O(6번째 인덱스)가 되며 오른쪽 자노드는

^ ^ ^ //R(7번째 인덱스값)이 되는데 R>O,R>A이므로 R,A교환

H E R T S O A P //E(인덱스 2)와 그 왼쪽 자노드T(인덱스 4),오른쪽 자노드S(인덱스 5)비교

^ ^ ^ //T>S,T>E 결국 T,E교환

H T R E S O A P //계속 E(인덱스 4)는 왼쪽 자노드P(인덱스 8)과 비교교환하는데 P>E

^ ^

H T R P S O A E //H(인덱스 1)은 그의 왼쪽 자노드T(인덱스 2)와 오른쪽 자노드R(인덱스 3)

^ ^ ^ //T>R,T>H비교 교환한다.

T H R P S O A E //계속 H를 비교 교환하게 되는데,H(인덱스 2)이므로 왼쪽 자노드P(인덱스

4),오른쪽 자노드

^ ^ ^ //S(인덱스5)에서 S>P,S>H비교 교환하게 된다.

T S R P H O A E //정렬 끝.