Relaxed min-max 힘에 대한 병합 알고리즘

• 영문명: On Merging Algorithm for Relaxed Min-Max Heaps
• 발행기관: 호서대학교 중앙도서관
• 저자명: 민용식(Yong sik Min)
• 간행물 정보: 『호서대학교 논문집』제2권, 75~90쪽, 전체 16쪽
• 주제분류: 사회과학 > 무역학
• 파일형태: PDF
• 발행일자: 1994.12.30

영문 초록

This paper presents a data structure that implements a mergeable double-ended priority queue; namely, an improved relaxed min-max-pair heap. It suggests a sequential algorithm to merge priority queues organized in two relaxed min-max heaps: kheap and nheap of sizes k and n, respectively. This new data structure eliminates the blossomed tree and the lazying method used to merge the relaxed min-max heaps in [8]. As a result, the suggested method in this paper requires the time complexity of O(log(log(n/k))*log(k)) and the space complexity of O(n+k), assuming that k≤[log(size(nheap))] are in two heaps of different sizes.

목차

Abstract

Ⅰ. Introduction

Ⅱ. Basic Definition

Ⅲ. Merging the Relaxed Min-Max Heaps

Ⅳ. The Analysis of Merging Relaxed Heaps

Ⅴ. Conclusion

References