Á¤º¸Ã³¸®ÇÐȸ ³í¹®Áö ÄÄÇ»ÅÍ ¹× Åë½Å½Ã½ºÅÛ
Current Result Document : 3 / 4
ÇѱÛÁ¦¸ñ(Korean Title) |
¹¬½Ã ´Ù¿ø AM-Èü |
¿µ¹®Á¦¸ñ(English Title) |
Implicit D-Ary AM-Heap |
ÀúÀÚ(Author) |
Á¤ÇØÀç
Haejae Jung
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 07 NO. 12 PP. 0289 ~ 0294 (2018. 12) |
Çѱ۳»¿ë (Korean Abstract) |
º» ³í¹®¿¡¼´Â AM-ÈüÀÇ ´Ù¿ø ¹öÀüÀÎ AM(d)-ÈüÀ̶ó°í ÇÏ´Â ¹¬½Ã ´Ù¿ø ¿ì¼±¼øÀ§ Å¥¸¦ Á¦¾ÈÇϸç, Á¦¾ÈµÈ AM(d)-Èü¿¡¼´Â »ðÀÔ¿¡ O(1)ÀüÀ̽ð£ÀÌ °É¸®°í »èÁ¦ ¿¬»ê¿¡ O(logn) ½Ã°£ÀÌ °É¸°´Ù. ½ÇÇè °á°ú¿¡ µû¸£¸é, ÀüüÀûÀ¸·Î d°¡ 4 ¶Ç´Â 8ÀÏ ¶§ °¡Àå ¿ì¼öÇÑ ¼º´ÉÀ» ³ªÅ¸³»¾ú´Ù. ±âÁ¸ÀÇ ÈÄÀ§Èü°ú ºñ±³Çϸé AM(d)-ÈüÀÌ ¾à 1.5~1.8¹è ºü¸¥ °ÍÀ¸·Î ³ªÅ¸³µ´Ù.
|
¿µ¹®³»¿ë (English Abstract) |
This paper proposes an implicit d-ary priority queue, called AM(d)-heap that is a generalized version of AM-heap, in which insert operation takes constant amortized time and remove operation takes O(logn) time. According to our experimental results, the best performance was shown when d is 4 or 8. Also, AM(d)-heap is about 1.5¢¦1.8 times faster than the postorder heap.
|
Å°¿öµå(Keyword) |
¿ì¼±¼øÀ§ Å¥
¹¬½Ã Èü
ÀüÀÌ ½Ã°£ º¹Àâµµ
ÀÚ·á ±¸Á¶
Priority Queue
Implicit Heap
Amortized Time Complexity
Data Structures
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|