{"id":1253,"date":"2024-04-16T14:53:25","date_gmt":"2024-04-16T05:53:25","guid":{"rendered":"https:\/\/skanto.co.kr\/?p=1253"},"modified":"2024-04-16T14:53:25","modified_gmt":"2024-04-16T05:53:25","slug":"implementing-mutable-priorityqueue","status":"publish","type":"post","link":"https:\/\/skanto.co.kr\/?p=1253","title":{"rendered":"Implementing Mutable PriorityQueue"},"content":{"rendered":"\n

\ub0b4\ube44\uac8c\uc774\uc158 \uacbd\ub85c\ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc73c\ub85c \uac00\uc7a5 \uc798 \uc54c\ub824\uc838 \uc788\uace0 \ub9ce\uc774 \uc774\uc6a9\ud558\ub294 \uc54c\uace0\ub9ac\uc998\uc774 Dijkstra \uc54c\uace0\ub9ac\uc998<\/a>\uc774\ub2e4. \uc54c\uace0\ub9ac\uc998 \uc218\ud589 \uacb0\uacfc\ub85c \ub9cc\ub4e4\uc5b4\uc9c4 \uacbd\ub85c\ub294 \ucd5c\ub2e8\uac70\ub9ac\ub97c \uc81c\uc678\ud558\uba74 \ube60\ub978\uacbd\ub85c\/\uc6b4\uc804\ud558\uae30 \ud3b8\ud55c \uacbd\ub85c\uc640 \uac19\uc774 \uc815\uc131\uc801\uc73c\ub85c \ud310\ub2e8\ud558\ub294 \ubd80\ubd84\uc774 \ub9ce\ub2e4. \uc774\uc640 \uac19\uc740 \ucc99\ub3c4\ub97c \uc81c\uc678\ud558\uba74 \uacbd\ub85c\ud0d0\uc0c9 \uc5d4\uc9c4\uc758 \ud488\uc9c8\uc744 \uce21\uc815\ud558\ub294 \uc911\uc694\ud55c \ucc99\ub3c4\ub294 \uacbd\ub85c\ud0d0\uc0c9 \uacfc\uc815\uc5d0\uc11c \uc18c\uc694\ub418\ub294 \uc2dc\uac04\uc77c \uac83\uc774\ub2e4.  Dijkstra \uc54c\uace0\ub9ac\uc998\uc744 \uc774\uc6a9\ud558\uba74 \ucd5c\uc801\uc758 \uacbd\ub85c\ub97c \ucc3e\uae34 \ud558\uc9c0\ub9cc \ud0d0\uc0c9\uc2dc\uac04\uc774\ub77c\ub294 \ube44\uc6a9\uc744 \uc9c0\ubd88\ud574\uc57c \ud55c\ub2e4. \ub0b4\ube44\uac8c\uc774\uc158 \ud488\uc9c8\uc5d0\uc11c \ud0d0\uc0c9\uc2dc\uac04\uc774\ub77c\ub294 \ube44\uc6a9\uc744 \uc904\uc774\uae30 \uc704\ud574 A*\uc640 \uac19\uc774 \ud0d0\uc0c9\uacf5\uac04(Search Space)\uc744 \uc904\uc774\ub294 Heuristic \uae30\ubc95\ub4e4\uc744 \ub9ce\uc774 \ud65c\uc6a9\ud558\uace0 \uc788\uc73c\uba70 \ucd5c\uadfc\uc5d0\ub294 \uac1c\ub150\uc744 \ubc14\uafd4 \uc804\ucc98\ub9ac(Preprocessing) \ub2e8\uacc4\ub97c \uc774\uc6a9\ud558\uc5ec \uc880 \ub354 \uad50\ud1b5\uacf5\ud559\uc801\uc73c\ub85c \uc811\uadfc\ud558\uc5ec \ud0d0\uc0c9\uc18d\ub3c4\ub97c \uac1c\uc120\ud558\ub824\ub294 \uc2dc\ub3c4\ub4e4\uc744 \ub9ce\uc774 \ud558\uace0 \uc788\ub2e4.<\/p>\n\n\n\n

\uc774 \uae00\uc5d0\uc11c\ub294 \uc774\ub7f0 \uc811\uadfc\ub3c4 \uc911\uc694\ud558\uc9c0\ub9cc Dijkstra \uc54c\uace0\ub9ac\uc998 \ub0b4\uc5d0\uc11c \ud65c\uc6a9\ub418\ub294 \uc8fc\uc694 \uc790\ub8cc\uad6c\uc870\uc778 Queue\ub97c \uac1c\uc120\ud568\uc73c\ub85c\uc368 \ud0d0\uc0c9 \uc18d\ub3c4\ub97c \uc904\uc774\ub294 \ubc29\ubc95\uc5d0\ub300\ud574 \uc774\uc57c\uae30 \ud574 \ubcf4\uace0\uc790 \ud55c\ub2e4.<\/p>\n\n\n\n

\ubcf8 \ub0b4\uc6a9\uc744 \uc774\uc5b4\uac00\uae30 \uc804\uc5d0 \uba3c\uc800 Dijkstra \uc54c\uace0\ub9ac\uc998\uc5d0\uc11c Queue\uac00 \uc65c \uc911\uc694\ud558\uace0 \ud0d0\uc0c9\uc2dc\uac04\uacfc  \uc5b4\ub5a4 \uad00\ub828\uc774 \uc788\ub294\uc9c0 \uac04\ub77d\ud558\uac8c \uc54c\uc544\ubcf4\uc790.<\/p>\n\n\n\n

Dijkstra \uc54c\uace0\ub9ac\uc998\uc5d0\uc11c Queue\uc758 \uc911\uc694\uc131<\/h2>\n\n\n\n

Dijkstra \uc54c\uace0\ub9ac\uc998\uc740 \ub3c4\ucc29\uac00\ub2a5\ud55c \ubaa8\ub4e0 \uc9c0\uc810\uc5d0 \ub300\ud574 \ucd9c\ubc1c\uc9c0\ub85c\ubd80\ud130 \ucd5c\ub2e8\uacbd\ub85c\ub97c \ub9cc\ub4e4\uc5b4 \ub0b8\ub2e4. \uc774\ub54c \uc54c\uace0\ub9ac\uc998 \ub0b4\ubd80\uc801\uc73c\ub85c \ubcf4\uba74 \ub2e4\uc74c \ub2e8\uacc4\uc5d0\uc11c \ubc29\ubb38\ud560 \ud6c4\ubcf4 \uc9c0\uc810\ub4e4\uc744 \ubaa8\ub450 \uac00\uc838\uc628 \ub2e4\uc74c \uc774\ub4e4 \uc9c0\uc810 \uc911\uc5d0 \uac00\uc7a5 \ube68\ub9ac \ub3c4\ub2ec\ud560 \uc218 \uc788\ub294 \uc9c0\uc810\ub4e4\uc744 \ud558\ub098\uc529 \uc120\ud0dd\ud574\uac00\uba70 \ucd9c\ubc1c\uc9c0\ub85c\ubd80\ud130\uc758 \uac70\ub9ac\ub97c \ube44\uad50\ud558\ub294 \uacfc\uc815\uc744 \ubc18\ubcf5\ud574 \ub098\uac04\ub2e4. \uc774\ub54c \uc911\uc694\ud55c \uac83\uc740 \uac00\uc838\uc628 \uc9c0\uc810\ub4e4 \uc911 \uac00\uc7a5 \ube68\ub9ac \ub3c4\ub2ec\ud560 \uc218 \uc788\ub294 \uc9c0\uc810\uc744 \ucc3e\uc544\ub0b4\ub294 \uac83\uc774\uba70 \ub9cc\uc57d \uc774 \uacfc\uc815\uc744 \ube44\ud6a8\uc728\uc801\uc73c\ub85c \uad6c\ud604\ud560 \uacbd\uc6b0 \uc804\uccb4 \ud0d0\uc0c9 \uc2dc\uac04\uc744 \uc7a1\uc544\uba39\uc744 \uc218 \uc788\ub2e4. \uc608\ub97c \ub4e4\uc5b4 \uc11c\uc6b8\uc5ed\uc5d0\uc11c \ucd9c\ubc1c\ud558\uc5ec \ubd80\uc0b0\uc5ed\uc5d0 \ub3c4\ucc29\ud558\ub294 \ucd5c\ub2e8\uacbd\ub85c \ud0d0\uc0c9 \uacfc\uc815\uc744 \uc0dd\uac01\ud574\ubcf4\uba74 \uc54c\uace0\ub9ac\uc998 \ub3d9\uc791\uc911\uc5d0 \uc57d 1,000\uac1c\uc5d0\uc11c 2,000\uac1c\uc758 \ud6c4\ubcf4\uc9c0\uc810\uc744 \uac00\uc838\uc624\uace0 \uc774\ub4e4 \uc911 \uac00\uc7a5 \ube68\ub9ac \ub3c4\ub2ec\ud560 \uc218 \uc788\ub294 \uc9c0\uc810\uc744 \ucc3e\uc544\uc57c \ud55c\ub2e4. \uc774 \uacfc\uc815\uc744 \uc57d 3,000,000 \ubc88\uc744 \uc218\ud589\ud574\uc57c \ud55c\ub2e4\uace0 \ud558\uba74 \uac00\uc7a5 \ube68\ub9ac \ub3c4\ub2ec\ud560 \uc218 \uc788\ub294 \ud6c4\ubcf4\uc9c0\uc810\uc744 \ucc3e\uae30 \uc704\ud574 \uc815\ub82c\ud558\ub294 \uc5f0\uc0b0\uc774 \uc54c\uace0\ub9ac\uc998 \uc18d\ub3c4\uc5d0 \uc9c0\ub300\ud55c \uc601\ud5a5\uc744 \ub07c\uce58\uac8c \ub428\uc744 \uc54c \uc218 \uc788\ub2e4. \uc774\ub97c \uc704\ud574 \uc77c\ubc18\uc801\uc73c\ub85c Dijkstra \uc54c\uace0\ub9ac\uc998 \uad6c\ud604\uccb4\ub294 \uc815\ub82c \uae30\ub2a5\uc744 \ub0b4\ud3ec\ud558\ub294 PriorityQueue<\/a>\ub77c\ub294 Queue \uc790\ub8cc\uad6c\uc870\ub85c \uc8fc\ub85c \ud65c\uc6a9\ud55c\ub2e4. \uc989, \ud6c4\ubcf4\uc9c0\uc810\uc744 Queue\uc5d0 enqueue \ud55c \ud6c4 dequeue\ub418\ub294 \ud6c4\ubcf4\uc9c0\uc810\uc740 \ub0b4\ubd80\uc801\uc73c\ub85c \uc815\ub82c\uacfc\uc815\uc744 \uac70\uccd0 \uac00\uc7a5 \ube68\ub9ac \ub3c4\ub2ec\ud560 \uc218 \uc788\ub294 \uc9c0\uc810\uc774 \ubf51\uc544\uc838 \ub098\uc624\uac8c \ub418\ub294 \uac83\uc774\ub2e4.<\/p>\n\n\n\n

PriorityQueue\ub294 \ud6c4\ubcf4\uc9c0\uc810\uc774 enqueue \ub420 \ub54c \ud6a8\uc728\uc801 \uc815\ub82c\ud558\uae30 \uc704\ud574 Priority Heap<\/a>\uc744 \uc774\uc6a9\ud55c\ub2e4. \uc989, Queue\ub0b4\uc758 \ud56d\ubaa9\ub4e4\uc5d0 \ub300\ud574 Binary Tree<\/a>\ub97c \uc774\uc6a9\ud55c Heap Sort\ub97c \uc801\uc6a9\ud55c\ub2e4. \uc774\ub97c \uc774\uc6a9\ud558\uba74 \uc77c\ubc18\uc801\uc73c\ub85c \uc758 \ud0d0\uc0c9\uc2dc\uac04\uc744 \ubcf4\uc7a5\ud560 \uc218 \uc788\uc744 \ubfd0\ub9cc \uc544\ub2c8\ub77c \ubaa8\ub4e0 \ud6c4\ubcf4\uc9c0\uc810\ub4e4\uc5d0 \ub300\ud574 \uc815\ub82c\uc744 \ud558\uc9c0 \uc54a\uace0 \uac00\uc7a5 \ube68\ub9ac \ub3c4\ub2ec\ud560 \uc218 \uc788\ub294 \uc9c0\uc810 \ud558\ub098\ub9cc \ucc3e\uc73c\uba74 \ub418\ubbc0\ub85c Dijkstra\uc54c\uace0\ub9ac\uc998\uc5d0\uc11c \ud65c\uc6a9\ud560 \uc218 \uc788\ub294 \ud6a8\uc728\uc801\uc778 \uc815\ub82c\ubc29\uc2dd\uc774\ub77c \ud560 \uc218 \uc788\ub2e4. \ud558\uc9c0\ub9cc Java\uc5d0\uc11c \uc81c\uacf5\ud558\ub294 PriorityQueue\ub294 enqueue \uacfc\uc815\uc5d0\uc11c\uc758 \uc815\ub82c\uc740 \ubcf4\uc7a5\ud558\uc9c0\ub9cc \uc774\ubbf8 Queue\ub0b4\ubd80\uc5d0 \ub4e4\uc5b4\uc788\ub358 \uc9c0\uc810\uc758 \uac12(cost)\uc774 \ube44\uad50 \uacfc\uc815\uc5d0\uc11c \ubcc0\uacbd\ub420 \uacbd\uc6b0 \uc7ac\uc815\ub82c\ud560 \uc218 \uc788\ub294 \ud6a8\uc728\uc801\uc778 \ubc29\ubc95\uc744 \uc81c\uacf5\ud558\uc9c0 \uc54a\ub294\ub2e4\ub294 \uac83\uc774 \ub9f9\uc810\uc774\ub2e4.<\/p>\n\n\n\n

\uc774 \uacbd\uc6b0 \uc815\ub82c\uc744 \uc704\ud574 \uc774\uc6a9\ud560 \uc218 \uc788\ub294 \ubc29\ubc95\uc73c\ub85c\ub294<\/p>\n\n\n\n

    \n
  1. Queue\ub0b4\uc758 \ubcc0\uacbd\ub41c \uc9c0\uc810\uc744 remove()\ud55c \ub2e4\uc74c \ub2e4\uc2dc offer() \ud558\ub294 \ubc29\ubc95<\/li>\n\n\n\n
  2. PriorityQueue \ub0b4\uc758 \uc9c0\uc810\uc774 \ubcc0\uacbd\ub418\uba74 \uae30\uc874\uc758 \uac1d\uccb4\ub97c \ubc84\ub9ac\uace0 \uc0c8\ub85c\uc6b4 PriorityQueue \uac1d\uccb4\ub97c \ub9cc\ub4dc\ub294 \ubc29\ubc95<\/li>\n<\/ol>\n\n\n\n

    \uc744 \uc0dd\uac01\ud574 \ubcfc \uc218 \uc788\ub2e4. \uc774 \ubc29\ubc95\uc744 \ud65c\uc6a9\ud558\uba74 \uc6d0\ud558\ub294 \uacb0\uacfc\ub97c \uc5bb\uc744 \uc218\ub294 \uc788\uc9c0\ub9cc \uc774\ub860\uc801\uc73c\ub85c \ubcfc \ub54c \ube44\uc6a9\uc774 \ub9ce\uc774 \ubc1c\uc0dd\ud558\ub294 \uc5f0\uc0b0\uc774\ub77c \ud560 \uc218 \uc788\ub2e4.  1\ubc88\uc758 \uacbd\uc6b0 remove \uc5f0\uc0b0\uc2dc \ub0b4\ubd80\uc801\uc73c\ub85c Binary Tree\uc758 Heap\uc744 \uc7ac\uad6c\uc131\ud558\uae30 \uc704\ud574 swap\uc5f0\uc0b0\uc774 \ub9ce\uc774 \ubc1c\uc0dd\ud558\uba70 \uc774\ud6c4 offer\uc5f0\uc0b0\uc5d0\uc11c\ub294 \uc815\ub82c\uc744 \ub2e4\uc2dc \uc218\ud589\ud574\uc57c \ud55c\ub2e4. 2\ubc88\uc758 \uacbd\uc6b0\ub294 PriorityQueue\uac1d\uccb4\ub97c \uc0c8\ub85c \ub9cc\ub4e4\uc5b4\uc57c \ud558\ubbc0\ub85c \ucef4\ud4e8\ud130 \uc785\uc7a5\uc5d0\uc11c \ubcf4\uba74 \uba54\ubaa8\ub9ac \ud655\ubcf4\ub77c\ub294 \ube44\uad50\uc801 \ube44\uc2fc \uc5f0\uc0b0\uc744 \uc218\ud589\ud574\uc57c \ud558\uba70 \uae30\uc874\uc5d0 Queue\uac00 \uac00\uc9c0\uace0 \uc788\ub358 \ubaa8\ub4e0 \uc9c0\uc810\ub4e4\uc744 \uc0c8\ub85c\uc6b4 \ubc30\uc5f4(queue)\uc5d0 \ubcf5\uc0ac\ud558\ub294 \uacfc\uc815\ub3c4 \uc218\ud589\ub418\uc5b4\uc57c \ud55c\ub2e4. \ub610\ud55c \ub0b4\ubd80\uc801\uc73c\ub85c\ub294 Heap\uc744 \ub2e4\uc2dc \uad6c\uc131\ud574\uc57c \ud558\ub294 \ubd80\ub2f4\uae4c\uc9c0 \ud3ec\ud568\ud558\uace0 \uc788\ub2e4.<\/p>\n\n\n\n

    \ub9cc\uc57d Queue\ub0b4\ubd80\uc5d0 \uc788\ub294 \ud6c4\ubcf4 \uc9c0\uc810\uc5d0\uc11c \uac12(cost)\uc774 \ubcc0\uacbd\ub420 \uacbd\uc6b0 Heap \uc758 \uc815\ub82c\ub9cc \ubcc0\uacbd\ud560 \uc218 \uc788\ub2e4\uba74 \uc55e\uc5d0\uc11c \uc5b8\uae09\ud588\ub358 \ube44\ud6a8\uc728\uc801\uc778 \ubd80\ubd84\uc774 \uc0ac\ub77c\uc9c0\uac8c \ub418\ubbc0\ub85c \ud0d0\uc0c9\uc18d\ub3c4\uac00 \uac1c\uc120\ub420 \uc218 \uc788\ub2e4\ub294 \uacb0\ub860\uc5d0 \uc774\ub97c \uc218 \uc788\ub2e4. \uc54c\uace0\ub9ac\uc998 \uad6c\ud604\uc2dc \uac1c\ubc1c\uc790\ub4e4\uc774 \uc774\ub7f0 \ubb38\uc81c\uc810\uc744 \uc778\uc9c0\ud588\uc5c8\ub2e4\uba74 \ud574\uacb0\uc744 \uc704\ud55c \ub2e4\uc591\ud55c \uc2dc\ub3c4\ub4e4\uc774 \uc788\uc5c8\uc744\ud14c\uace0 \uc774\uc640 \uad00\ub828\ub41c \uc608\uc81c\ub4e4\uc774 \uc778\ud130\ub137\uc5d0 \uc788\uc744 \ubc95 \ud55c\ub370 \uc544\ubb34\ub9ac \ucc3e\uc544\ubd10\ub3c4 \ucc3e\uc744 \uc218\uac00 \uc5c6\ub2e4. \ud558\uc9c0\ub9cc \uc2e4\ub9c8\ub9ac\ub97c \uc81c\uacf5\ud558\ub294 \ub17c\ubb38<\/a>\uacfc PriorityQueue.Java \uc18c\uc2a4\ucf54\ub4dc<\/a>, \uc720\uc6a9\ud55c \uc778\ud130\ub137 \uc790\ub8cc<\/a>\ub97c \ubc14\ud0d5\uc73c\ub85c Mutable PriorityQueue(\uac00\uce6d)\uc744 \uc124\uacc4\ud560 \uc218 \uc788\uc5c8\uace0 \uadf8 \uad6c\ud604\uacfc\uc815\uc744 \uae30\ub85d\uc73c\ub85c \ub0a8\uaca8\ubcf8\ub2e4.<\/p>\n\n\n\n

    Heapsort overview<\/a><\/h2>\n\n\n\n

    Java\uc5d0\uc11c \uc81c\uacf5\ub418\ub294 PriorityQueue.java\ub294 \ub0b4\ubd80\uc801\uc73c\ub85c Heapsort\ub97c \ud65c\uc6a9\ud558\uba70  Complete Binary-Tree(\uc644\uc804\uc774\uc9c4\ud2b8\ub9ac)\ub97c \uae30\ubc18\uc73c\ub85c \ub3d9\uc791\ud558\ubbc0\ub85c \uba3c\uc800 Complete Binary-Tree\uc758 \ud2b9\uc131\uc744 \uc774\ud574\ud560 \ud544\uc694\uac00 \uc788\ub2e4.<\/p>\n\n\n\n

    \"\"\/<\/figure>\n\n\n\n

    Complete Binary-Tree\ub294 \uc774\uc9c4 \ud2b8\ub9ac\uc5d0\uc11c \uc544\ub798 \ub450 \uac00\uc9c0 \uc870\uac74\uc744 \ub354 \ub9cc\uc871\ud574\uc57c \ud55c\ub2e4.<\/p>\n\n\n\n

      \n
    1. \ub9c8\uc9c0\ub9c9 \ub808\ubca8(leaf)\uc744 \uc81c\uc678\ud55c \ubaa8\ub4e0 \ub178\ub4dc\uac00 \ucc44\uc6cc\uc838 \uc788\ub2e4.<\/li>\n\n\n\n
    2. \ubaa8\ub4e0 \ub178\ub4dc\ub4e4\uc740 \uc67c\ucabd\ubd80\ud130 \ucc44\uc6cc\uc9c4\ub2e4.<\/li>\n<\/ol>\n\n\n\n

      \uc774\ub7f0 Complete Binary-Tree\uc758 \ud2b9\uc131\uc744  \ubc30\uc5f4\ub85c \ud45c\ud604\ud558\uba74 \uc544\ub798 \uadf8\ub9bc\uacfc \uac19\uc774 \ub8e8\ud2b8 \ub178\ub4dc\ub294 1\ubc88\uc9f8 Index\uc5d0 \uc800\uc7a5\ub418\uba70 \ubd80\ubaa8\ub178\ub4dc\ubcf4\ub2e4 \ud070 \uac12\uc744 \uac00\uc9c0\ub294 \uc790\uc2dd\ub178\ub4dc\ub4e4\uc740 \uc67c\ucabd\ubd80\ud130 \uc21c\uc11c\ub300\ub85c \uc800\uc7a5\uc774 \uac00\ub2a5\ud558\ub2e4.(0-based Index\uc77c \uacbd\uc6b0\ub294 Root\uac00 0\ubc88\uc9f8 \uc784) \uc774\uc640 \uac19\uc774 \ubc30\uc5f4\uc744 \uc774\uc6a9\ud558\uba74 \ud2b9\uc815 Index\uc5d0 \uc9c1\uc811 \uc811\uadfc\ud560 \uc218 \uc788\uc73c\ubbc0\ub85c \ud6a8\uc728\uc801\uc778 \ucc98\ub9ac\uac00 \uac00\ub2a5\ud574 \uc9c4\ub2e4.<\/p>\n\n\n\n

      \"\"\/<\/figure>\n\n\n\n

      \uc704 \uadf8\ub9bc\uc5d0\uc11c \ud2b9\uc9d5\uc73c\ub85c\ub294<\/p>\n\n\n\n

        \n
      1. \uc124\uba85 \uc6a9\uc774\ud568\uc744 \uc704\ud574 \uc704 \uadf8\ub9bc\uc758 \uc2dc\uc791 Index(root)\ub294 1 \ubd80\ud130 \uc2dc\uc791\ud55c\ub2e4. (\uc2e4\uc81c \uad6c\ud604\uc740 0-based index\ub85c \uad6c\ud604)<\/li>\n\n\n\n
      2. \uac01 \ub178\ub4dc\uc640 \ub300\uc751\ub418\ub294 \ubc30\uc5f4\uc758 Index\ub294 \uc720\uc9c0\ub41c\ub2e4.<\/li>\n<\/ol>\n\n\n\n

        \uc774\ub7f0 \ud2b9\uc9d5\uc744 \uc774\uc6a9\ud558\uba74 \ub2e4\uc74c\uc744 \uc720\ucd94\ud560 \uc218 \uc788\ub2e4. [ ] \uc548\uc740 0-based index\ub85c \ud560 \uacbd\uc6b0, i: index<\/p>\n\n\n\n

          \n
        1. \uc67c\ucabd \uc790\uc2dd \ub178\ub4dc Index = Index \u00d7 2 [iLeftChild(i) = 2\u22c5i + 1<\/em>]<\/li>\n\n\n\n
        2. \uc624\ub978\ucabd \uc790\uc2dd \ub178\ub4dc Index =\u00a0Index \u00d7 2 + 1 [iRightChild(i) = 2\u22c5i + 2<\/em>]<\/li>\n\n\n\n
        3. \ubd80\ubaa8 \ub178\ub4dc Index = floor(Index \/ 2) [iParent(i) = floor((i\u22121) \/ 2<\/em>)]<\/li>\n\n\n\n
        4. \ub0b4\ubd80 \ub178\ub4dc(leaf\uac00 \uc544\ub2cc \ub178\ub4dc)\uc758 Index \ubc94\uc704\ub294 \uc804\uccb4 \ub178\ub4dc \uac1c\uc218\uc758 1\/2 \ubbf8\ub9cc(0-based index\uc77c \uacbd\uc6b0)<\/li>\n<\/ol>\n\n\n\n

          \uc774\uc640 \uac19\uc740 Complete Binary-Tree\uc758 \ud2b9\uc9d5\uc640 \uc131\uc9c8\uc744 \uc774\uc6a9\ud558\uc5ec Heap\uc5d0 \ucd94\uac00(offer)\uc640 \uc0ad\uc81c(poll) \uc5f0\uc0b0\uc744 \uc124\uba85\ud558\uba74 \uc544\ub798\uc640 \uac19\ub2e4.<\/p>\n\n\n\n

          offer() operation<\/h2>\n\n\n\n

          offer()\uc5f0\uc0b0\uc740 Queue \ucd94\uac00\ud558\ub294 enqueue \ub3d9\uc791\uc73c\ub85c Heap\uc5d0 \ub178\ub4dc\ub97c \ucd94\uac00(offer)\ud558\ub294 \uacfc\uc815\uc740 \uc544\ub798\uc758 \uadf8\ub9bc\uc73c\ub85c \uc124\uba85\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n

          \"\"\/<\/figure>\n\n\n\n

          \ubc30\uc5f4\uc758 \ub9c8\uc9c0\ub9c9 \ubd80\ubd84\uc5d0 \ub178\ub4dc\ub97c \ub123\uace0 \ubd80\ubaa8\ub178\ub4dc\ub97c \ucc3e\uc544\uac00\uba74\uc11c \ubd80\ubaa8 \ub178\ub4dc\uac00 \uc0bd\uc785 \ub178\ub4dc\ubcf4\ub2e4 \uc791\uc744 \ub54c \uae4c\uc9c0 \uc694\uc18c\ub97c \uad50\ud658\ud574\uac00\uba74\uc11c \uc62c\ub77c\uac04\ub2e4. \uc704\uc640 \uac19\uc740 \uacfc\uc815\uc744 \ud754\ud788 \uc704\ub85c \uc62c\ub77c\uac00\uba74\uc11c \uc120\ubcc4\ud55c\ub2e4\uace0 \ud558\uc5ec siftUp (\uc0c1\ud5a5 \uc120\ubcc4) \uc774\ub77c\uace0 \ubd80\ub978\ub2e4. \uc989, \uac12\uc744 \ucd94\uac00 \ud560 \ub54c\ub294 size + 1 \uc778\ub371\uc2a4\uc5d0 \uc0c8\ub85c\uc6b4 \uac12\uc744 \ucd94\uac00\ud558\uace0 siftUp \uacfc\uc815\uc744 \uac70\uccd0 ‘\uc7ac\ubc30\uce58’\ub97c \ud55c\ub2e4\uace0 \uc0dd\uac01\ud558\uba74 \ub41c\ub2e4. \uc5ec\uae30\uc11c \uc8fc\ubaa9\ud560 \ubd80\ubd84\uc740 Heap\uc5d0 \uc0c8\ub85c\uc6b4 \ub178\ub4dc\uac00 \ucd94\uac00\ub420 \ub54c \ud56d\uc0c1 Root\ub294 \ucd5c\uc18c\uac12\uc73c\ub85c \uc720\uc9c0\ub41c\ub2e4\ub294 \uac83\uc774\ub2e4.<\/p>\n\n\n\n

          poll() operation<\/h2>\n\n\n\n

          poll() \uc5f0\uc0b0\uc740 Queue\uc5d0\uc11c Head\ub97c \ucd94\ucd9c\ud558\ub294 dequeue \uc5f0\uc0b0\uc73c\ub85c Heap\uc5d0\uc11c Root\ub178\ub4dc\ub97c \ucd94\ucd9c\ud558\ub294 \ub3d9\uc791\uc774\ub2e4. dequeue \uc774\ud6c4\uc758 \ub0b4\ubd80 \ub3d9\uc791\uc740 \uacf5\ubc31\uc774 \ub41c Head \ub178\ub4dc\ub97c \uc55e\uc560\uc11c \uc124\uba85\ud55c offer() \uc5f0\uc0b0\uacfc \ubc18\ub300\uc758 \uacfc\uc815\uc73c\ub85c \ucc44\uc6cc\ub098\uac00\uba74 \ub41c\ub2e4. \uc989, \ub9c8\uc9c0\ub9c9\uc5d0 \uc704\uce58\ud55c \ub178\ub4dc\ub97c \ube44\uc5b4\uc788\ub294 Root \ub178\ub4dc\ub85c \uac00\uc838\uc628 \ub2e4\uc74c \uc790\uc2dd\ub178\ub4dc\uac00 \uc7ac\ubc30\uce58\ud558\ub824\ub294 \ub178\ub4dc\ubcf4\ub2e4 \ud06c\uac70\ub098 \uc790\uc2dd\ub178\ub4dc\uac00 \uc5c6\uc744 \ub54c\uae4c\uc9c0 \uc704\uce58\ub97c \uc7ac\ubc30\uce58 \ud574\ub098\uac00\uba74 \ub41c\ub2e4. \uc5ec\uae30\uc11c \uc790\uc2dd\ub178\ub4dc\uac00 \uc5c6\uc744 \ub54c\uae4c\uc9c0 \uc218\ud589\ud55c\ub2e4\ub294 \uac83\uc740 \uc55e\uc560\uc11c Complete Binary-Tree\uc5d0\uc11c \uc720\ucd94\ud55c \uac83\ucc98\ub7fc \uc804\uccb4 \ub178\ub4dc \uac1c\uc218\uc758 1\/2 \ubbf8\ub9cc\uae4c\uc9c0 \ud655\uc778\ud574 \ub098\uac00\uba74 \ub41c\ub2e4. \uc774 \ub0b4\uc6a9\uc744 \uadf8\ub9bc\uc73c\ub85c \ud45c\ud604\ud558\uba74 \uc544\ub798\uc640 \uac19\ub2e4.<\/p>\n\n\n\n

          \"\"\/<\/figure>\n\n\n\n

          \uc5ec\uae30\uc11c \uc8fc\ubaa9\ud560 \uc810\uc740 \uc67c\ucabd \uc790\uc2dd \ub178\ub4dc\uc640 \uc624\ub978\ucabd \uc790\uc2dd \ub178\ub4dc \uc911 ‘\uc791\uc740 \uac12\uc744 \uac00\uc9c4 \ub178\ub4dc’\uc640 \uc7ac\ubc30\uce58\ub97c \ud574\uc57c \ud55c\ub2e4\ub294 \uac83\uc774\ub2e4.  \ub9cc\uc57d \ubc18\ub300\ub85c \ub41c\ub2e4\uba74 \uc704 \uadf8\ub9bc\uc758 \uccab\ubc88\uc9f8 \ube44\uad50\/\uad50\ud658 \ub2e8\uacc4\uc5d0\uc11c 35\uac00 Root\ub178\ub4dc\uc5d0 \ubc30\uce58\ub418\uc5b4\ubc84\ub9ac\uba70, \uc774\ub294 \uc67c\ucabd \uc790\uc2dd\ub178\ub4dc\uc778 10\ubcf4\ub2e4 \ud070 \uac12\uc744 \uac00\uc9c0\uac8c \ub418\uc5b4 \ucd5c\uc18cHeap\uc744 \ub9cc\uc871\ud558\uc9c0 \ubabb\ud558\uac8c \ub41c\ub2e4. \uc774\ub807\uac8c \uc544\ub798\ub85c \ub0b4\ub824\uac00\uba74\uc11c \uc7ac\ubc30\uce58\ud558\ub294 \uacfc\uc815\uc744 siftDown (\ud558\ud5a5 \uc120\ubcc4)\uc774\ub77c\uace0 \ud55c\ub2e4.<\/p>\n\n\n\n

          mutate() operation<\/h2>\n\n\n\n

          mutate\uc5f0\uc0b0\ub294 PriorityQueue.java\uac00 \uc81c\uacf5\ud558\uc9c0 \uc54a\ub294 \uba54\uc18c\ub4dc\ub85c Queue \ub0b4\ubd80\uc5d0 \uc788\ub294 \ub178\ub4dc\uc758 \uc0c1\ud0dc\uac00 \ubcc0\uacbd\ub420 \uacbd\uc6b0 offer()\uc5f0\uc0b0\uacfc poll()\uc5f0\uc0b0\uc744 \uac19\uc774 \ud65c\uc6a9\ud558\uba74 \uac04\ub2e8\ud558\uac8c \uad6c\ud604\ud560 \uc218 \uc788\ub2e4. \uc989, \uc0c1\ud0dc(\uac12, Cost)\uac00 \ubcc0\uacbd\ub41c \ub178\ub4dc\uac00 \ubd80\ubaa8\ub178\ub4dc\ubcf4\ub2e4 \uac12\uc774 \uc791\ub2e4\uba74 offer()\uc5d0\uc11c \ud588\ub358 shiftUp\uc5f0\uc0b0\uc744 \uc218\ud589\ud558\uace0, \uc790\uc2dd\ub178\ub4dc\ubcf4\ub2e4 \uac12\uc774 \ud06c\ub2e4\uba74  poll()\uc5d0\uc11c \ud588\ub358 shiftDown \uc5f0\uc0b0\uc744 \uc218\ud589\ud558\uba74 \ub41c\ub2e4. \uc774 \uacfc\uc815\uc744 \uac04\ub2e8\ud558\uac8c \ucf54\ub4dc\ub85c \uc124\uba85\ud558\uba74 \uc544\ub798\uc640 \uac19\ub2e4.<\/p>\n\n\n\n

          MutablePriorityQueue.java<\/strong><\/p>\n\n\n\n

          \n...\n \npublic boolean mutate(E e) {\n    final int i = indexOf(e);\n    if (i == -1) return false;\n    int child = (i << 1) + 1; \/\/ assume left child is least\n    int parent = (i - 1) >>> 1;\n    Object[] es = queue;\n    if (i < (size >>> 1) && ((Comparable<? super E>) e).compareTo((E) es[child]) > 0) {\n        siftDown(i, e, es, size);  \/\/ the priority of the element is greater than the priority of child element\n    } else if (i > 0 && ((Comparable<? super E>) e).compareTo((E) es[parent]) < 0) {\n        siftUp(i, e, es);\n    }\n    return true;\n}\n \n...<\/code><\/pre>\n\n\n\n
          Java API\ub85c \uc81c\uacf5\ub418\ub294 PriorityQueue.java\ub97c \ud655\uc7a5\ud574\uc11c mutate\uae30\ub2a5\uc744 \ucd94\uac00\ud558\uba74 \ub418\uaca0\uc9c0\ub9cc siftUp, siftDown\uacfc \uac19\uc774 \ud575\uc2ec \uba54\uc18c\ub4dc\ub4e4\uc758 visibility\uac00 private\uc73c\ub85c \uc124\uc815\ub418\uc5b4 \uc788\uc5b4 \ud074\ub798\uc2a4 \uc678\ubd80\uc5d0\uc11c\ub294 \uc811\uadfc\uc774 \ubd88\uac00\ub2a5\ud558\ub2e4. \ub530\ub77c\uc11c \uc0c8\ub85c\uc6b4 MutablePriorityQueue\ub85c \uad6c\ud604\ud560 \uc218 \ubc16\uc5d0 \uc5c6\uc73c\uba70 siftUp, siftDown \uba54\uc18c\ub4dc\ub294 \uae30\uc874\uc758 \uba54\uc18c\ub4dc\uc640 \ub3d9\uc77c\ud558\ub2e4\uace0 \ubcf4\uba74 \ub41c\ub2e4.<\/p>\n\n\n\n
          MutablePriorityQueue\uc5d0 \ucd94\uac00\ub41c \uc720\uc6a9\ud55c Method<\/h2>\n\n\n\n
          find() Method<\/h3>\n\n\n\n
          \uc55e\uc5d0\uc11c \uc124\uba85\ud55c mutate()\uba54\uc18c\ub4dc \ubfd0\ub9cc \uc544\ub2c8\ub77c \uc54c\uace0\ub9ac\uc998 \ub3d9\uc791\uc2dc PriorityQueue\uc5d0 \ub4e4\uc5b4 \uc788\ub294 \uc9c0\uc810\ub4e4 \uc911 \ud2b9\uc815 \uc9c0\uc810\uc744 \ucc3e\uc544\ub0b4\ub294 \uae30\ub2a5\uc744 \ub9ce\uc774 \ud65c\uc6a9\ud55c\ub2e4. \uc774\ub97c \uc704\ud574 Queue \ub0b4\ubd80\uc758 \ubaa8\ub4e0 \uc9c0\uc810\uc744 \ubc30\uc5f4\ub85c \ubcc0\ud658\ud55c \ub2e4\uc74c \ucc3e\uc544\ub0b4\ub294 \ubc29\ubc95 \ub610\ub294 Stream\uc744 \ud65c\uc6a9\ud558\uc5ec \ucc3e\ub294 \ubc29\ubc95\uc744 \uc774\uc6a9\ud55c\ub2e4. \uc774 \uacbd\uc6b0 \uac1c\ubc1c\ud574\uc57c \ud558\ub294 \ucf54\ub4dc\uac00 \uae38\uc5b4\uc9c0\uac70\ub098 \ub0b4\ubd80\uc801\uc73c\ub85c \ubc30\uc5f4\uc744 \ubcf5\uc0ac\ud574\uc57c\ud558\ub294 \ubd80\ub2f4\uc744 \uc548\uace0 \uc788\ub2e4. \ubc30\uc5f4 \ubcf5\uc0ac \uc5c6\uc774 \uadf8\ub9ac\uace0 \uac04\uacb0\ud55c \ucf54\ub4dc\ub97c \uc791\uc131\ud560 \uc218 \uc788\ub3c4\ub85d Queue \ub0b4\ubd80\uc758 \ubc30\uc5f4\uc5d0 \uc9c1\uc811 \uc811\uadfc\ud558\uc5ec  \uac80\uc0c9\uc774 \uac00\ub2a5\ud558\ub3c4\ub85d find() \uba54\uc18c\ub4dc\ub97c \ucd94\uac00\ud558\uc600\ub2e4.<\/p>\n\n\n\n
          \n...\n\/**\n * Refer to the find method of MutableQueue interface\n *\/\npublic Optional<E> find(Predicate<? super E> predicate) {\n    E e = null;\n    for (int i = 0; i < size; i++) {\n        if (predicate.test((E) queue[i])) {\n            e = (E) queue[i];\n            break;\n        }\n    }\n    return Optional.ofNullable(e);\n}\n...<\/code><\/pre>\n\n\n\n
          \uc774\ub97c \uc774\uc6a9\ud560 \uacbd\uc6b0 Dijkstra\uc54c\uace0\ub9ac\uc998 \uad6c\ud604\uc2dc Queue\ub0b4\uc5d0 \ud2b9\uc815 \ubc29\ubb38\uc9c0\uc810\uc744 \ucc3e\ub294 \ucf54\ub4dc\ub294 \uc544\ub798\uc640 \uac19\uc774 \uac04\ub7b5\ud558\uac8c \uc791\uc131\ud560 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n
          ...\nfinal MutableQueue<Visit> unsettled = new MutablePriorityQueue<>();\n...\nVisit adjacent = unsettled.find(v -> v.has(link.to())).orElseGet(() -> new Visit(link.to()));\n...<\/code><\/pre>\n\n\n\n
          pick() Method<\/h3>\n\n\n\n
          \ub610\ud55c Queue \ub0b4\ubd80\uc758 \ubc30\uc5f4\uc744 \uac80\uc0c9\ud558\uc9c0 \uc54a\uace0 Map\uc744 \uc774\uc6a9\ud558\uc5ec \ubc14\ub85c \uc811\uadfc\ud560 \uc218 \uc788\ub3c4\ub85d pick() \uba54\uc18c\ub4dc\ub3c4 \ucd94\uac00\ud558\uc600\ub2e4. pick() \uba54\uc18c\ub4dc\ub294 Node\ub97c \ud30c\ub77c\ubbf8\ud130\ub85c \ubc1b\uc544 Map\uc11c \ubc14\ub85c \ucc3e\uae30 \ub54c\ubb38\uc5d0 find()\ubcf4\ub2e4 \ub354 \uac04\uacb0\ud558\uac8c \uc0ac\uc6a9\ud560 \uc218 \uc788\uc73c\uba70 \ub354 \ube60\ub978 \uc131\ub2a5\uc744 \ubcf4\uc7a5\ud55c\ub2e4. \uc544\ub798\ub294 pick()\uba54\uc18c\ub4dc\ub97c \ud65c\uc6a9\ud558\ub294 \ucf54\ub4dc\ub97c \ubcf4\uc5ec \uc900\ub2e4.<\/p>\n\n\n\n
          ...\nVisit adjacent = unsettled.pick(link.to()).orElseGet(() -> new Visit(link.to()));\n...<\/code><\/pre>\n\n\n\n
          Dijkstra \uc54c\uace0\ub9ac\uc998 \uc801\uc6a9\uc2dc \uc131\ub2a5 \ud14c\uc2a4\ud2b8<\/h2>\n\n\n\n
          \ud14c\uc2a4\ud2b8 \uc2dc\ub098\ub9ac\uc624<\/h3>\n\n\n\n
          \ub3d9\uc77c\ud55c \ucd9c\ubc1c\uc9c0 \ubaa9\uc801\uc9c0(\uc11c\uc6b8\uc5ed -> \uac15\ub989\uc5ed) \uae30\ubc18\uc73c\ub85c PriorityQueue\ub97c \uc544\ub798\uc758 \uc2dc\ub098\ub9ac\uc624\ub85c \uc801\uc6a9\ud558\uc5ec \ucd1d 5\ud68c \uc5f0\uc18d \ud14c\uc2a4\ud2b8<\/p>\n\n\n\n
            \n
          1. Visit\uc758 Cost \ubcc0\uacbd\uc2dc PriorityQueue \ub0b4\uc758 \uc6b0\uc120\uc21c\uc704\ub97c \uc7ac\uc870\uc815 \ud558\ub3c4\ub85d MutablePriorityQueue \uc801\uc6a9<\/li>\n\n\n\n
          2. Visit\uc758 Cost \ubcc0\uacbd\uc2dc PriorityQueue\uc5d0\uc11c \ud574\ub2f9 visit\uc744 \uc0ad\uc81c\ud55c \ud6c4 \uc7ac \uc0bd\uc785(offer)<\/li>\n\n\n\n
          3. Visit\uc758 Cost \ubcc0\uacbd\uc2dc PriorityQueue \uac1d\uccb4\ub97c \uc0c8\ub85c \uc0dd\uc131<\/li>\n<\/ol>\n\n\n\n
            \ud14c\uc2a4\ud2b8 \ud658\uacbd<\/h3>\n\n\n\n