Á¤º¸Ã³¸®ÇÐȸ ³í¹®Áö ÄÄÇ»ÅÍ ¹× Åë½Å½Ã½ºÅÛ
Current Result Document : 4 / 4
ÇѱÛÁ¦¸ñ(Korean Title) |
IMI-Èü: »ó¼ö »ðÀÔ ÀüÀÌ ½Ã°£ º¹Àâµµ¸¦ °¡Áø ¹¬½Ã ¾ç´Ü ¿ì¼±¼øÀ§ Å¥ |
¿µ¹®Á¦¸ñ(English Title) |
IMI-Heap: An Implicit Double-Ended Priority Queue with Constant Insertion Amortized Time Complexity |
ÀúÀÚ(Author) |
Á¤ÇØÀç
Haejae Jung
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 08 NO. 02 PP. 0029 ~ 0034 (2019. 02) |
Çѱ۳»¿ë (Korean Abstract) |
¿ì¼±¼øÀ§ Å¥Àº ±Ùº»ÀûÀÎ ÀÚ·á ±¸Á¶ ÁßÀÇ ÇϳªÀÌ¸ç ¿À·§µ¿¾È ¸¹Àº ¿¬±¸°¡ ÀÌ·ç¾î¿© ¿Ô´Ù. º» ³í¹®¿¡¼´Â IMI-ÈüÀ̶ó°í ÇÏ´Â ¹¬½Ã ¾ç´Ü ¿ì¼±¼øÀ§ Å¥¸¦ Á¦¾ÈÇÑ´Ù. Á¦¾ÈµÈ IMI-Èü¿¡¼´Â »ðÀÔ¿¡ O(1) ÀüÀ̽ð£ÀÌ °É¸®°í ÃÖ¼Ò°ª°ú ÃÖ´ë°ª »èÁ¦ ¿¬»ê¿¡ °¢°¢ O(logn) ½Ã°£ÀÌ °É¸°´Ù. ±âÁ¸¿¡ ¹ßÇ¥µÈ ¹¬½Ã ¾ç´Ü ¿ì¼±¼øÀ§ Å¥´Â »ðÀÔ°ú ÃÖ¼Ò/ÃÖ´ë°ª »èÁ¦¿¡ ¸ðµÎ O(logn) ½Ã°£ÀÌ °É¸®´Â °ÍÀ¸·Î º» ÀúÀÚ´Â ¾Ë°í ÀÖ´Ù. µû¶ó¼ Á¦¾ÈµÈ IMI-ÈüÀº »ðÀÔ ½Ã°£ º¹Àâµµ¿¡ ÀÖ¾î¼ ±âÁ¸ÀÇ Èüº¸´Ù ¿ì¼öÇÏ´Ù.
|
¿µ¹®³»¿ë (English Abstract) |
Priority queues, one of the fundamental data structures, have been studied for a long time by computer scientists. This paper proposes an implicit double-ended priority queue, called IMI-heap, in which insert operation takes constant amortized time and each of removal operation of the minimum key or the maximum key takes O(logn) time. To the author¡¯s knowledge, all implicit double-ended priority queues that have been published, perform insert, removeMin and removeMax operations in O(logn) time each. So, the proposed IMI-heap is superior than the published heaps in terms of insertion time complexity.The abstract should concisely state what was done, how it was done, principal results, and their significance.
|
Å°¿öµå(Keyword) |
¾ç´Ü ¿ì¼±¼øÀ§ Å¥
¹¬½Ã Èü
ÀüÀÌ ½Ã°£ º¹Àâµµ
ÀÚ·á ±¸Á¶
Double-Ended Priority Queue
Implicit Heap
Amortized Time Complexity
Data Structures
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|