상수삽입전이시간을가지는양단우선순위큐 217 DOI: 10.3745/KIPSTA.2009.16-A.3.217 상수삽입전이시간을가지는양단우선순위큐 정해재 요 약 우선순위큐는스케줄링, 정렬, 유전자검색과같은우선순위에따른검색, 최단거리계산과같은응용에사용될수있다. 본논문에서제안하는배열을이용한양단우선순위큐자료구조는삽입과삭제연산에각각 O(1) 전이시간과 O(logn) 시간이걸린다. 본저자가알고있는한, 지금까지의배열을이용한양단우선순위큐알고리즘은삽입과삭제에모두 O(logn) 시간이걸린다. 키워드 : 자료구조, 양단우선순위큐, 힙, 전이시간복잡도 A Double-Ended Priority Queue with O(1) Insertion Amortized Time Haejae Jung ABSTRACT Priority queues can be used in applications such as scheduling, sorting, retrival based on a priority like gene searching, shortest paths computation. This paper proposes a data structure using array representation for double-ended priority queue in which insertion and deletion takes O(1) amortized time and O(logn) time, respectively. To the author's knowledge, all the published array-based data structures for double ended priority queue support O(logn) time insertion and deletion operations. Keywords : Data Structure, Double-Ended Priority Queue, Heap, Amortized Time Complexity 1. 서론 1) 양단우선순위큐 (double-ended priority queue) 는어떤데이터집합 S에서특정우선순위에따른최소값과최대값을빨리찾고자고안된동적자료구조로서, 다음의세가지연산을기본으로지원하며, 이자료구조는운영체제스케줄링, 사건시뮬레이션, 유전자검색과같은우선순위에따른검색, 또는정렬과같은응용에이용될수있다. insert(e, S): 집합 S에새로운임의의데이터 e를추가. delmax(s): 집합 S로부터우선순위가가장높은데이터를삭제. delmin(s): 집합 S로부터우선순위가가장낮은데이터를삭제. 우선순위큐는부모-자식관계를나타내기위해포인터를사용하거나일차원배열인덱스를사용하여구현할수있다. 포인터를사용하는경우부모노드와자식노드를포 이논문은 2006 년도안동대학교특성화추진지원사업에의하여연구되었음. 종신회원 : 안동대학교정보통신공학과교수논문접수 : 2009 년 1 월 22 일수정일 :1 차 2009 년 4 월 21 일심사완료 : 2009 년 4 월 30 일 인터로연결하여부모-자식관계를나타내고, 배열을사용하는경우인덱스값에관한간단한수식을사용하여부모- 자식관계를묵시적으로나타낸다. 배열을이용한단일우선순위큐 (single-ended priority queue) 로는 O(logn) 삽입및삭제시간을가진전통적인힙, 상수삽입전이시간 (amortized time) 과 O(logn) 삭제시간복잡도를가지는묵시이항 (binomial) 큐, 및 M-힙의배열버전인 MA-힙등이있다 [1-4]. MA-힙은최대 O(logn) 개의내부힙으로구성되며, 삽입은 O(1) 전이시간복잡도 (amortized time complexity) 를가지고, 삭제는 O(logn) 시간복잡도를가진다 [1]. MA-힙은묵시이항큐보다자료구조가훨씬단순하여구현하기가상당히용이하다. 본논문에서관심이있는배열을이용한양단우선순위큐에는최대-최소힙 (min-max heap), 딥 (deap), d-딥 (d-deap), 대칭최대-최소힙 (symmetric min-max heap), 구간힙 (interval heap) 등이있으며, 이들은모두 O(logn) 삽입및삭제시간복잡도를가진다 [5-8]. 이중구간힙의구조는전통적인힙과같은완전이진트리 (complete binary tree) 형태를가지지만, 제일마지막노드를제외한각노드에는구간의좌단값과우단값을나타내는두개의값 <lval, rval> 을유지
218 정보처리학회논문지 A 제 16-A 권제 3 호 (2009.6) 하고, lval <= rval의관계를가진다. 삽입, 삭제연산을통하여부모노드의구간은자식노드의구간을항상포함하도록유지한다 [5, 6]. 본논문에서는상수삽입전이시간과 O(logn) 최대값 / 최소값삭제시간을가지는배열을이용한양단우선순위큐 MI-힙을제안하며, 제안된자료구조는 MA-힙의자료구조의특성과구간힙의특성을기반으로하여고안된구조이다. 본저자가알고있는한, 지금까지의배열을이용한모든양단우선순위큐에대한모든자료구조는 O(logn) 삽입과 O(logn) 최대값 / 최소값삭제시간복잡도를가진다. 2. MI-힙자료구조 MI-힙은최대 n 개의데이터를저장하기위해 개의노드를가지는포화이진트리 (full binary tree) 로표현되며, 최대 O(logn) 개의내부힙으로구성된다 [3]. 데이터를가지고있는내부힙의각루트노드는연결리스트를통하여연결된다. ( 그림 1) 은노드 2와노드 6에루트를가진두개의내부힙으로구성된 MI-힙의예를나타내며, 각내부힙의루트노드는연결리스트의노드에의해참조되고연결리스트의각노드는 lastp로부터접근될수있다. MI- 힙에서는삽입과삭제연산을하기위해서두개의변수 lastleaf와 lastp를유지한다. lastleaf는데이터를가진노드중가장오른쪽리프노드를나타내고, lastp는가장오른쪽연결리스트노드를참조하여마지막내부힙즉가장오른쪽내부힙의루트노드를접근할수있도록하고있다. MI-힙에서의는각노드에좌단값 (lval) 과우단값 (rval) 의두값 <lval, rval> 을저장하여구간을나타내는데, 그두값의관계는 lval <= rval 이다. MI-힙에서의부모노드의구간은항상자식노드의구간을포함하는관계를가진다. 예를들면, ( 그림 1) 에서노드 4와 5의구간은노드 2의구간에포함된다. ( 그림 3) MI-힙에서의연산 lastp를통하여연결된연결리스트의각노드는 ( 그림 3) 과같은구조를가진다. nextp는연결리스트의다음노드를가리키고, rootnode는내부힙의루트노드인덱스값을저장하며, height는 rootnode에의해참조되는내부힘의높이를나타낸다. ( 그림 1) 에서의연결리스트노드에있는값은 height 값이다. MI-힙에서의실질적인데이터삽입과삭제는 MI-힙에서의가장오른쪽에있는마지막내부힙의루트노드에서이루어지며, 그노드의 rval은실제저장되는어떠한값보다도크게정의된값 (( 그림 1) 에서 로표시 ) 이저장될수있다. ( 그림 3) 은연결리스트를생략한 MI-힙의구조를나타내고있다. 삽입연산시마지막내부힙루트노드의 rval이 인경우, 새데이터로 값을대체한다. 그렇지않은경우마지막두내부힙의높이를비교한다. 높이가같은경우, ( 그림 3) 의 (a) 와같이마지막두내부힙의루트노드의부모노드 h에새로운데이터와 값를삽입하고, 노드 h를새로운마지막내부힙의루트로만든다. 높이가같지않을경우, ( 그림 3) 의 (b) 와같이하나의노드로된새로운내부힙 h에새데이터와 값을삽입하고, 노드 h를마지막내부힙의루트노드로만든다. 삭제의경우실제데이터의삭제는마지막내부힙의루트노드에서일어난다. 즉, 먼저각내부힙의루트노드를조사하여최대또는최소값을찾고, 그값을마지막내부힙의 rval (rval이 이면 lval) 로대체한다. 물론기술한삽입또는대체후힙조정 (heapify) 이적절히이루어진다. 3. MI- 힙연산 3.1 초기화 MA- 힙에서는 n 개의데이터저장을위해크기가 인배열 A[M] 를할당하여, 포화이진트리가되도록한다. 참조변 ( 그림 1) MI-힙의예 nextp height rootnode ( 그림 2) 연결리스트노드구조 void initialize( nummax ) // nummax : max. number of elements MinLeaf = 2 log2(nummax) ; // leftmost leaf node MaxLeaf = 2* MinLeaf - 1; // rightmost leaf node // allocate array A[] and // initialize lastleaf and lastp. A = new Node [MaxLeaf + 1]; // array of nodes lastleaf = MinLeaf - 1; ListNode lastp = null; // reference of right most linked list node ( 그림 4) MI- 힙초기화
상수삽입전이시간을가지는양단우선순위큐 219 수 lastp 는 NULL 로초기화되고, 변수 lastleaf 는 MI-힙의제일왼쪽리프노드인덱스보다 1 적은값으로초기화한다. 3.2 힙조정 MI-힙에새로운데이터가삽입되면더이상 MI-힙의성질을만족하지못하게되므로힙조정을통하여 MI-힙성질을만족하도록만든다. MI-힙에서는새로운데이터가어떤내부힙의루트노드의좌단값또는우단값으로삽입될수있으며, 힙조정은하향식으로이루어진다. 새로운데이터가우단값으로상입될경우, 우단값으로만형성되는최대힙를따라하향식으로조정이이루어지는데, 그알고리즘은 ( 그림 5) 에나타나있다. 좌단값으로만구성되는최소힙을따라하향식으로힙조정을하는 heapify_lheap( ) 도이와유사하게작성할수있다. 함수 heapify_rheap() 의인수 k는새로운우단값을가지고있는노드인덱스를나타낸다. 함수 cmp_swap() 는특정 노드의좌단값과우단값을비교하여좌단값이우단값보다크면서로교환해주는함수이다. heapify_rheap() 함수에서노드 k의두자식노드의우단값중큰값을가지는노드를 max로두고, 노드 max가부모노드 k의우단값보다크면두우단값을서로교환한다. 이러한과정은부모노드의우단값이자식노드의우단값중큰값보다크면 while 반복문을빠져나와힙조정을종료한다. // k : root node to start to heapify void heapify_rheap( k ) cmp_swap( A[k].lval, A[k].rval ); left = 2*k; // left child of k while( left < MaxLeaf ) // 자식이있는동안 max = left; if( A[max].rval < A[left+1].rval ) max = left + 1; // right child of k. if( A[k].rval > A[max].rval ) break; swap( A[k].rval, A[max].rval ); cmp_swap( A[max].lval, A[max].rval ); k = max; left = 2*k; ( 그림 5) 우단힙조정알고리즘 3.3 삽입 ( 그림 6) 은 MI-힙삽입알고리즘을보여주고있다. 인수로전달된 thedata 를삽입하기위해마지막내부힙의루트노드가한개의데이터만가지고있는지알아본다. 이경우인수로전달된데이터로 rval인 INF( ) 값을대체하고 heapify_rheap() 함수를호출하여힙조정을한다. 마지막두내부힙의높이가같은경우에는마지막내부힙 루트노드의부모노드에인수 thedata와 INF 값을각각 lval 과 rval로저장하고, heapify_lheap() 을호출하여힙조정을한다. 마지막리스트노드의왼쪽노드는삭제하고, 마지막리스트노드의 rootnode와 height 필드를수정한다. 마지막두내부힙의높이가다른경우, lastleaf를 1 증가하여새로운내부힙을생성하고, 이노드의 lval과 rval 필드에 thedata와 INF 값을각각삽입한다. 이경우새로운리스트노드를하나생성하여마지막리스트노드로만들고, 이노드의 rootnode와 height 값은 lastleaf와 1이된다. ( 그림 7) 과 ( 그림 8) 은 ( 그림 1) 에데이터 45와 35를연속으로삽입한후의 MI-힙을보여주고있다. ( 그림 7) 은 45로 INF값을대체한후힙조정한결과이고, ( 그림 8) 은 35를새로운내부힙루트노드 14에삽입한결과이다. bool insert( Element thedata ) // check if the rval of the last root is infinite value. if( lastp!= NULL && A[lastp.rootnode].rval == INF ) lastroot = lastp.rootnode; A[lastroot].rval = thedata; heapify_rheap( lastroot ); return TRUE; // Now, heap is empty, or the last root node has two values. h1 = -1; h2 = -2; if( lastp ) if( lastp.rootnode == 1 ) return FALSE; // MI-힙 is full. h1 = lastp.height; // 마지막내부힙높이 sp = lastp.nextp; // 두번째리스트노드 if( sp ) h2 = sp.height; // 마지막왼쪽내부힙높이 if( h1 == h2 ) parnode = lastp.rootnode / 2; A[parnode].lval = thedata; A[parnode].rval = INF; heapify_lheap( parnode ); lastp.rootnode = parnode; lastp.height++; lastp.nextp = sp.nextp; delete sp; // 두번째리스트노드삭제 else lastleaf++; A[lastLeaf].lval = thedata; A[lastLeaf].rval = INF; np = new ListNode; np.rootnode = lastleaf; np.height = 1; np.nextp = lastp; lastp = np; return TRUE; ( 그림 6) 삽입알고리즘 ( 그림 7) ( 그림 1) 에 45 를삽입한후
220 정보처리학회논문지 A 제 16-A 권제 3 호 (2009.6) ( 그림 8) ( 그림 7) 에 35 를삽입한후 [ 정리 1] n 개의데이터를가지고있는 MI-힙에서, 삽입연산은 O(1) 전이시간복잡도를가진다. ( 증명 ) 리스트노드의삽입및삭제와변수 lastleaf의증가는상수시간걸리고, m개의노드를가진내부힙의힙조정은트리높이인 O(logm) 시간이걸린다. 삽입전이시간복잡도를구하기위해, 일련의삽입연산이이루어진다고하자. 일련의삽입중, 두개의내부힙으로구성된 MI-힙에새로운데이터를삽입할경우하나의내부힙만으로구성된 MI-힙이되는데, 이때최대비용이소요된다. 삽입시의힙조정은항상이웃하는두내부힙의부모노드에서시작하여리프노드쪽으로이루어지므로, 그부모노드의높이만큼의시간이걸린다. 따라서, 하나의내부힙으로구성된 MI-힙의높이가 h라할때, 일련의삽입총 비용을계산하면 가된다. 즉, 트리레벨 i 에는 개의노드가있고, 각노드에대한 2개의데이터삽입비용은 가된다. 따라서총비용을계산하면, 이되므로, 각데이터삽입에대한전이시간복잡도는 이된다. int find_maxnode( void ) maxnode = lastp.rootnode; leftchild = 2 * maxnode; if( maxnode.rval == INF && leftchild <= MaxLeaf ) rightchild = leftchild +1; maxnode = leftchild; if( A[leftchild].rval < A[rightchild].rval ) maxnode = rightchild; maxval = A[maxnode].rval; if( A[maxnode].rval == INF ) maxval = A[maxnode].lval; tmp = lastp.nextp; while( tmp ) if( A[tmp.rootnode].rval > maxval ) maxnode = tmp.rootnode; maxval = A[maxnode].rval; tmp = tmp.nextp; return maxnode; // node index with maxval ( 그림 9) 최대값을가진노드찾기함수 Element delmax( ) if( lastp == NULL ) return -1; // MI-힙 is empty. maxnode = find_maxnode( ); // find the node with max. element retdata = A[maxnode].rval; if( A[maxnode].rval == INF ) // maxnode == lastroot : leaf node retdata = A[maxnode].lval; lastleaf--; tmp = lastp; lastp = lastp.nextp; delete tmp; lastroot = lastp.rootnode; if( A[lastroot].rval == INF ) // lastroot has children, maxnode!= lastroot A[maxnode].rval = A[lastroot].lval; heapify_rheap( maxnode ); if( 2*lastroot < MaxLeaf ) split_heap( ); else lastleaf--; tmp = lastp; lastp = lastp.nextp; delete tmp; 3.4 최대값삭제최대값은내부힙들중어떤한내부힙의루트노드또는마지막내부힙의루트노드의자식노드에있을수있다. ( 그림 9) 에서보는바와같이마지막내부힙의 rval이 INF 값을가지고있는경우그자식노드의값도조사하여최대값을가진노드및값을각각 maxnode 및 maxval로둔다. 마지막내부힙을제외한내부힙에대해서는루트노드의 rval만비교하면되며, while 문을통하여최대값을가진 maxnode를찾게된다. MI-힙에서의최대값삭제는최대값을가지고있는내부힙을찾은후, 그최대값을마지막내부힙의루트노드값으로대체하고, 대체된내부힙에대해힙조정을함으로써이루어진다. ( 그림 10) 의최대값삭제알고리즘은우선 find_maxnode() 함수를호출하여최대값을가진노드 maxnode를찾는다. // Now, there is no INF value in MI-heap. if( lastroot!= maxnode ) A[maxnode].rval = A[lastroot].rval; heapify_rheap( maxnode ); A[lastroot].rval = INF; ( 그림 10) 최대값삭제알고리즘 maxnode의 rval이 INF이면 maxnode는단하나의리프노드만을가진마지막내부힙이므로마지막내부힙을삭제하고최대값을리턴한다. 그렇지않고마지막내부힙루트노드의 rval이 INF이면, 그노드의 lval을 maxnode의 rval로대체한후힙조정을한다. 힙조정후, 마지막내부힙루트노드가
상수삽입전이시간을가지는양단우선순위큐 221 자식을가지고있으면 split_heap( ) 함수를호출하여마지 4. 결론 막내부힙의루트노드의오른쪽자식을마지막내부힙루 트노드로만들고, 자식이없으면마지막내부힙을제거한 본고에서제안한 MI-힙은배열을이용하여묵시적으로 다. 위의경우가아니면, 마지막내부힙의 rval을 maxnode 부모-자식관계를표현하는양단우선순위큐자료구조이다. 의 rval로복사한후 maxnode 로부터하향식으로힙조정을 배열을이용한기존의양단우선순위큐알고리즘은삽입 한다. 마지막내부힙루트노드인 lastroot의 rval에는 INF 과삭제를하는데모두 O(logn) 시간이걸렸지만, 본논문에 값을삽인한후, 최대값을리턴한다. 서제안한 MI-힙에서는삽입과최대값 / 최소값삭제연산에 ( 그림 11) 의 split_heap( ) 함수는마지막내부힙의루트 각각상수전이시간과 O(logn) 시간복잡도를가진다. 노드에더이상데이터가없을경우그자식들을루트로하 는두개의내부힙으로분리하는함수이다. 이때, 마지막 참고문헌 두내부힙의높이는 1 감소한다. ( 그림 12) 는기술한알고리즘에따라 ( 그림 8) 로부터최 [1] 정해재, 배열표현을이용한 M-힙에서의삽입 / 삭제알고리 대값 90을삭제한결과를보여주고있다. 즘, 정보처리학회논문지, 13-A(3), pp.261-266, Jun., 2006. [2] D. Mehta, and S. Sahni(ed.), Handbook of Data Structures [ 정리 2] n 개의데이터를가지고있는 MI-힙에서, 최대 and Applications, Chapman & Hall/CRC, New York, 2005. 값삭제연산은 O(logn) 시간복잡도를가진다. [3] S. Bansal, S. Sreekanth, and P. Gupta, M-heap: A Modified heap data structures, International Journal of Foundations ( 증명 ) 힙조정알고리즘 heapify_rheap( ) 은힙의높이만 of Computer Science, 14(3), pp.491-502, 2003. 큼의시간이걸리므로 O(logn) 시간이걸리고, MI-힙에최대 [4] S. Carlsson, J. Munro, and P. Poblete, An implicit binomial O(logn) 개의내부힙이존재할수있으므로최대값을가진 queue with constant insertion time, Proceedings of the 1st 노드를찾는함수 find_maxnode( ) 또한 O(logn) 시간이걸 Scandinavian Workshop on Algorithm Theory, Lecture 린다. 그외의삭제알고리즘에서사용하는함수 split_heap( ) Notes in Computer Science, 318, pp.1-13, July, 1988. 과문장은상수시간이걸린다. 따라서최대값삭제알고리 [5] J. van Leeuwen and D. Wood, Interval heaps, The Computer 즘은 O(logn) 시간복잡도를가진다. Journal, 36(3), 209-216, 1993. O(logn) 시간복잡도를가지는최소값삭제알고리즘도 [6] Y. Ding and M. Weiss, On the Complexity of Building an 최대값삭제알고리즘과유사하며, 구체적인알고리즘은 [ 부 Interval Heap, Information Processing Letters, 50, 143-144, 록 ] 의 ( 그림 13) 와 ( 그림 14) 에나타나있다. 1994. [7] H. Jung, The d-deap*: A fast and simple cache-aligned d-ary deap, Information Processing Letters, 93(2), pp.63-67, void split_heap( void ) // 마지막내부힙루트가자식을가지고있음. Jan., 2005. [8] E. Horowitz, S. Sahni, and D. Mehta, Fundamentals of Data sp = new ListNode; sp.nextp = lastp.nextp; lastp.nextp = sp; Structures in C++, W. H. Freeman, San Francisco, 1995. leftchild = 2 * lastp.rootnode; lastp.rootnode = leftchild+1; lastp.height--; sp.rootnode = leftchild; sp.height = lastp.height; ( 부록 ) 최소값삭제알고리즘 ( 그림 11) 마지막내부힙의분할 int find_minnode( void ) minroot = lastp.rootnode; tmp = lastp.nextp; while( tmp ) if( A[tmp.rootnode].lval < A[minroot].lval ) minroot = tmp.rootroot; tmp = tmp.nextp; return minroot; // node index with minval ( 그림 12) ( 그림 8) 로부터최대값삭제후 MI- 힙 ( 그림 13) 최소값을가진노드찾기함수
222 정보처리학회논문지 A 제 16-A 권제 3 호 (2009.6) Element delmin( ) if( lastp == NULL ) return -1; // MI-힙 is empty. minroot = find_minnode( ); // find the node with min. element retdata = A[minroot].lval; lastroot = lastp.rootnode; A[minroot].lval = A[lastroot].lval; heapify_lheap( minroot ); if( A[lastroot].rval!= INF ) A[lastroot].lval = A[lastroot].rval; heapify_lheap( lastroot ); A[lastroot].rval = INF; // A[lastroot].rval is INF. leftchild = 2 * lastroot; if( leftchild > MaxLeaf ) // lastroot is a leaf node. lastleaf--; tmp = lastp; lastp = lastp.nextp; delete tmp; else // lastroot has children split_heap( ); 정해재 e-mail : hjjung@andong.ac.kr 1984년경북대학교전자계산학과 ( 학사 ) 1987년서울대학교컴퓨터공학과 ( 공학석사 ) 2000년플로리다대학교 (UF) 컴퓨터정보학과 ( 공학박사 ) 1988년~1995년한국전자통신연구원선임연구원 2001년~2002년 Numerical Technologies Inc. Staff Engineer 2003년~2005년성신여자대학교컴퓨터정보학부교수 2005년~현재안동대학교정보통신공학과교수관심분야 : 알고리즘, 계산기하, 웹데이터베이스, 웹보안 ( 그림 14) 최소값삭제알고리즘