|DeleteMin  

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