- ÀÌÁø Å¥´Â ÀÌÁø ÆQ(Binomial
heap)ÀÇ ÁýÇÕ(Forest)ÀÌ´Ù.
- ÇϳªÀÇ Æ®¸®·Î ±¸¼ºµÇÁö
¾Ê°í ÀÌÇ× Æ®¸®¶ó°í ¹°¸®´Â
¿©·¯°³ÀÇ Æ®¸®µé Áï, Æ÷¸®½ºÆ®·Î
±¸¼º
- BK´Â
- ·çÆ® ¹Ø¿¡ B0, B1,
.... Bk-1À» ÀÚ¼Õ(child)À¸·Î
°¡Áü
- K = Àڽijëµå(Child)ÀÇ
¼ö = ³ôÀÌ(height)ÀÌ´Ù.
- Àüü ³ëµåÀÇ ¼ö´Â
2k
- ÀÌÁø Å¥¿¡¼ ¿¬»êÀº ÃÖ¾ÇÀÇ
°æ¿ì O(logN) , »ðÀÔÀº O(1)ÀÌ´Ù.
- »ðÀÔÀº B0
³ëµå¸¦ ¸¸µé¾î ¸ÓÁö ¼öÇà,
¸ÓÁö´Â Bi °¡
¾øÀ¸¸é Áß´ÜÇÑ´Ù. ¾øÀ» È®·üÀÌ
1/2 À̹ǷΠÆò±Õ 2¹ø¸¸¿¡
»ðÀÔ ¿Ï·á. O(1)
- »èÁ¦(DeleteMin)Àº O(logN)ÀÇ
¼öÇà½Ã°£ÀÌ °É¸°´Ù.
|
|