자료구조 & 알고리즘/트리(Tree)
[강한구] Binary Heap
오산돌구
2010. 3. 31. 22:42
Heap이란 ? 완전 이진트리를이용하고, 부모노드는 항상 자식노드보다 크거나 같음을 만족하는 자료구조이다.
각 노드는 유일한 키값을 가지며, 자료중에 가장큰값, 가장작은값을 찾을때 가장 적합하다.
Heap에는 두가지 종류가 있는데, max heap과min heap이 있다.
이름에서도 알수있듯이, max heap은 루트에 가장 큰 키값을 가진 노드가 위치하고,
min heap은 가장 작은 값을 가진 노드가 위치한것을 말한다.
max heap의 삽입, 삭제 과정을 보자.
<<<<<<<<<<<<<<<<<<<<삽입>>>>>>>>>>>>>>>>>>>>>>>>
삽입시 제일 마지막 노드에 추가후,
부모노드보다 추가된 노드의 키값이 크면, 바꾼다.(min heap은부모노드보다 작으면 바꿈)
<<<<<<<<<<<<<<<<<<<<삭제>>>>>>>>>>>>>>>>>>>>>>>>
삭제된 노드를 채우기 위해서 마지막 노드를 이동시킨후,
삽입 과정과 같이, 부모노드와 비교하면서 Heap을 재구성 한다.
구성된 Heap에서 다시 정렬을 수행한다.
검색쪽에 Heap을 쓴다고해서 공부해봄 . . .