Heap을 병합시키기 위한 효율적인 알고리즘 = An efficient algorithm for merging heaps

국문 초록 (Abstract)

본 논문은 태그노드를 이용하여서 크기가 n인 nheap과 크기가 k인 kheap을 병합시켜, 병합된 heap을 형성하기 위한 새로운 알고리즘을 제시하였다. 태그노드란 헤더노드의 일종으로서, 어떤 특정한 subtree의 근 노드를 지칭하면서 헤더노드의 역활을 수행하는 노드를 말한다.
이러한 결과, 기존의 YMH알고리즘에서 제기된 문제점인 non-perfect heap에서 병합되는 경우 dummy노드의 발생이 야기되는 점을, 본 논문에서는 태그노드를 이용하여서 dummy 노드들을 제거시켜서 병합을 구현하였다. 본 논문에서 사용한 k의 크기는 n의 크기보다 적은 경우로 국한시켜서 생각하였다.

목차 (Table of Contents)

• 요약
• Ⅰ. 서론
• Ⅱ. 기본정의
• Ⅲ. 병합 알고리즘
• Ⅳ. 결론
• 참고 문헌