(구)정보과학회 논문지
Current Result Document : 4 / 5
| 한글제목(Korean Title) |
Heap을 병합시키기 위한 빠른 알고리즘 |
| 영문제목(English Title) |
A Fast Algorithm for Merging Heaps |
| 저자(Author) |
김경태
민용식
Kyung Tae Kim
Yong Sik Min
|
| 원문수록처(Citation) |
VOL 14 NO. 04 PP. 0270 ~ 0276 (1987. 11) |
한글내용
(Korean Abstract) |
본 논문은 크기가 n인 nheap과 크기가 k인 kheap을 병합하여 새로운 heap을 구성시키기 위한 알고리즘을 제시하였다.
병합하는 과정에서 먼저 병합시킬 kheap의 크기에 해당되는 nheap의 노드 p를 찾아서, nheap의 root에서 노드 p이전(p-1번째) 노드에 이르는 것들이 병합된 후에도 heap-ordered 상태를 유지시키기 위해서 kheap과 이진검색으로서 수행된다. 그리고 p를 중심으로된 pheap과 kheap을 서로 병합시켜서 그 전체결과가 O((log(n/k)-k)*log(k)+log(p))시간에 수행된다. 이때 kheap의 크기 k는 [log(size(nheap))]으로 되어 있다.
|
영문내용
(English Abstract) |
This paper suggests an algorithm which is merged kheap with size k into nheap with size n.
During the merging phase, we first find the node p, which is contained with the size k in kheap. And we perform the binary search with kheap’s nodes and nheap’s nodes which is the path from the root to p-1’s. As a result, we always hold the merged heap with heap-ordered.
This algorithm runs in O((log(n/k)-k)*log(k) log(p)) time. The size k in k-heap is restricted to [log(size(nheap))].
|
| 키워드(Keyword) |
|
| 파일첨부 |
PDF 다운로드
|
