본문 바로가기

자료구조 & 알고리즘/트리(Tree)

[강한구] Binary Heap

Heap이란 ? 완전 이진트리를이용하고, 부모노드는 항상 자식노드보다 크거나 같음을 만족하는 자료구조이다.
             
각 노드는 유일한 키값을 가지며, 자료중에 가장큰값, 가장작은값을 찾을때 가장 적합하다.

Heap
에는 두가지 종류가 있는데, max heapmin heap이 있다.
이름에서도 알수있듯이, max heap은 루트에 가장 큰 키값을 가진 노드가 위치하고,
min heap
은 가장 작은 값을 가진 노드가 위치한것을 말한다.

max heap
의 삽입, 삭제 과정을 보자.

<<<<<<<<<<<<<<<<<<<<
삽입>>>>>>>>>>>>>>>>>>>>>>>>
삽입시 제일 마지막 노드에 추가후,
부모노드보다 추가된 노드의 키값이 크면, 바꾼다.(min heap은부모노드보다 작으면 바꿈)

 



<<<<<<<<<<<<<<<<<<<<
삭제>>>>>>>>>>>>>>>>>>>>>>>>

삭제된 노드를 채우기 위해서 마지막 노드를 이동시킨후,

삽입 과정과 같이, 부모노드와 비교하면서 Heap을 재구성 한다.

구성된 Heap에서 다시 정렬을 수행한다.

 

 

 

 

검색쪽에 Heap을 쓴다고해서 공부해봄 . . .

http://www.codesos.com/book/algori/sort_algo5.htm

'자료구조 & 알고리즘 > 트리(Tree)' 카테고리의 다른 글

[박혜웅] digital tree  (0) 2010.03.28
[박혜웅] 트리 (tree)  (0) 2010.03.28
[박혜웅] B Tree (balanced tree)  (0) 2010.03.27
[강한구] 이진트리  (0) 2009.07.13
[강한구] 트리 기초개념  (0) 2009.04.01