[자료구조론]이항히프의 설계

소개글

이항히프에 대한 이론과 설계 방향

목차

1. introduction
1.1 Overall description
1.2 Requirements
1.3 Sample Input/Output

2. Overall assignment design
2.1 flowchart

본문내용

1. introduction
1.1 Overall description
(1) Goal
본 과제에서는 동적 메모리 할당과 메모리 해제(dynamic storage allocation & deallocation)를 담당하는 메모리 관리 시스템을 시뮬레이션 한다. 이 메모리 관리 시스템은 주어진 전체 메모리 공간에서 프로세스들의 요청에 따라 일정량의 메모리 공간을 블록화 하여 할당하는 기능과 할당된 메모리 공간을 해제하는 기능, 그리고 메모리 공간의 상태를 출력하는 기능으로 구성한다.

(2) Background
(가) Binomial Heap의 정의
히프나 좌향 트리의 경우와 같이, 이항 히프도 최소와 초대의 두 가지 변형을 가지고 있다. 최소 이항 히프(min-binomial heap)는 최소 트리의 집합이고 초대 이항 히프는 최대 트리의 집합이다.
B-히프를 사용하면 삽입과 결합 연산의 실제 시간과 상환된 시간은 O(1)이 되고, 최소 삭제 연산의 상환 시간은 O(log n)이 된다. B-히프는 데이터 멤버로 degree, child, link, data를 가진 노드로 표현된다. 노드의 degree는 자식의 수를 나타내고, childs는 자식중의 하나를 가리키며, link는 형제 사이의 단순 연결 원형 리스트를 유지하는 데 사용된다. 노드의 모든 자식들은 단순 연결 원형 리스트를 구성하며 노드는 이러한 자식들 중의 하나를 지시하게 된다. 또한 B-히프를 구성하는 최소 트리들의 루트도 단순 연결 원형 리스트를 구성하기 위해 연결되어 있다. 따라서 B-히프는 최소 트리들 가운데 최소값을 갖는 루트를 가리키는 하나의 포인터에 의해 지시된다.

참고 자료

없음