변형된 Minmaxheap 메인터넌스 알고리즘

국문 초록 (Abstract)

본 논문은 ATKINSON[1]이 제안한 Double-ended priority queue(MinMaxHeap)를 확장하여 modified minmaxheap(MMM-Heap)라는 자료 구조와 MMM-Heap에 대한 유지·관리를 할 수 있는 알고리즘들을 제안한다. MMM-Heap 자료 구조는 배열을 중위수(Median)중심으로 왼쪽에는 중위수보다 작은 원소들로 MaxMinHeap을 구성하고, 오른쪽에는 중위수보다 큰 원소들로 MinMaxHeap을 구성한다. MMM-Heap자료 구조를 사용하면 최대값, 최소값, 중위값을 갖는 노드를 0(1)에 검색할 수 있을 뿐만 아니라, 최대값, 최소값, 중위값 제거를 0(log n)에 할 수 있고, 임의 노드 삽입을 0(log n), 임의노드 제거를 0(n)에 할 수 있다.

목차 (Table of Contents)

• 제Ⅰ장. 서론 1
• 제Ⅱ장. MMM-Heap 알고리즘 3
• 2-1. MMM-Heap 생성 알고리즘 3
• 2-2. MMM-Heap 삽입 알고리즘 9
• 2-3. MMM-Heap 검색 알고리즘 15
• 2-4. MMM-Heap 삭제 알고리즘 19
• 2-5. MMM-Heap에서 중위수를 찾는 알고리즘 22
• 제Ⅲ장. 결론 26
• 참고문헌 27