{"id":1606,"date":"2017-07-02T21:48:43","date_gmt":"2017-07-02T12:48:43","guid":{"rendered":"http:\/\/43.203.250.216\/?p=1606"},"modified":"2025-10-01T16:26:45","modified_gmt":"2025-10-01T07:26:45","slug":"heap-tree-%eb%a7%8c%eb%93%a4%ea%b8%b0","status":"publish","type":"post","link":"https:\/\/litcoder.com\/?p=1606","title":{"rendered":"Heap tree \ub9cc\ub4e4\uae30"},"content":{"rendered":"\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>Heap tree\ub294 \uc644\uc804\uc774\uc9c4\ud2b8\ub9ac \ud615\ud0dc\ub85c \ubaa8\ub4e0 \ubd80\ubaa8 \ub178\ub4dc\uc758 \uac12\uc774 \uc790\uc2dd \ub178\ub4dc \ubcf4\ub2e4 \ud06c\uac70\ub098 (<strong>max heap<\/strong>) \ubaa8\ub4e0 \ubd80\ubaa8 \ub178\ub4dc\uc758 \uac12\uc774 \uc790\uc2dd \ub178\ub4dc \ubcf4\ub2e4 \uc791\uc740 (<strong>min heap<\/strong>) tree\ub97c \ub9d0\ud55c\ub2e4. \uc774 \uae00\uc5d0\uc11c\ub294 max heap tree\ub97c \ub9cc\ub4dc\ub294 \ubc29\ubc95\uc744 \uc54c\uc544\ubcf8\ub2e4.<\/p><\/blockquote>\n\n\n\n<p>Heap tree\ub97c \uc0dd\uc131\ud558\ub294 buildHeapTree()\uc774 \ub3d9\uc791\ud558\ub294 \uc808\ucc28\ub294 \ub2e4\uc74c\uacfc \uac19\ub2e4. N\uc740 \uc6d0\uc18c\uc758 \uac2f\uc218.<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"raw\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\ubd80\ubaa8_\ub178\ub4dc := \uc18c\uc22b\uc810_\ubc84\ub9bc(N \/ 2) - 1 \ubd80\ud130 0\uae4c\uc9c0\n\ubaa8\ub4e0 \ubd80\ubaa8_\ub178\ub4dc\ub4e4\uc5d0 \ub300\ud558\uc5ec\n\n    hepify(\ubd80\ubaa8_\ub178\ub4dc):\n        \ud070_\uc790\uc2dd := max(\uc67c\ucabd_\uc790\uc2dd, \uc624\ub978\ucabd_\uc790\uc2dd)\n        if(\ud070_\uc790\uc2dd > \ubd80\ubaa8_\ub178\ub4dc)\n            swap(\ud070_\uc790\uc2dd, \ubd80\ubaa8_\ub178\ub4dc)\n            heapify(\ud070_\uc790\uc2dd)\n<\/pre>\n\n\n\n<p>\uc7ac\uadc0\ub85c \uad6c\ud604\ub41c heapify()\uac00 \ub4f1\uc7a5\ud558\ub294\ub370, \uc774 \ud568\uc218\uac00 \ud558\ub294 \uc5ed\ud560\uc740 \uc8fc\uc5b4\uc9c4 node\ub97c \ubd80\ubaa8\ub85c \uc2dc\uc791\ud574\uc11c \ub2e8\ub9d0 node\ub85c \ub0b4\ub824\uac00\uba74\uc11c max heap \uc870\uac74\uc5d0 \ub9de\ub3c4\ub85d \ubcc0\uacbd\ud574 \uc8fc\ub294 \uc5ed\ud560\uc744 \ud55c\ub2e4. heapify()\ub294 \ud070 \uc790\uc2dd\uacfc \ubd80\ubaa8\ub97c swap() \ud558\ub294 \uacbd\uc6b0 \uc7ac\uadc0\ud558\ubbc0\ub85c \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(\ud2b8\ub9ac\ub192\uc774)\uac00 \ub41c\ub2e4.<\/p>\n\n\n\n<p>Heap tree\ub97c \uc0dd\uc131\ud558\ub294 \ubc29\ubc95\uc744 \uace0\ubbfc\ud574 \ubcf8 \uc801\uc774 \uc788\ub2e4\uba74, \ubd80\ubaa8 node\ub4e4\uc744 \uc21c\ud68c \ud560 \ub54c \uc5ed\uc21c\uc73c\ub85c \uc21c\ud68c\ud558\ub294\uac8c \uc5bc\ub9c8\ub098 \uc601\ub9ac\ud55c \ubc29\ubc95\uc778\uc9c0 \ubb34\ub98e\uc744 \ucce4\uc744 \uac83\uc774\ub2e4. \ub0b4 \uc598\uae30\ub2e4;;<\/p>\n\n\n\n<h1 class=\"wp-block-heading\">\uc608\uc81c<\/h1>\n\n\n\n<p>\uc784\uc758\uc758 \uc815\ub82c\ub418\uc9c0 \uc54a\uc740 \ubc30\uc5f4 { 2, 7, 5, 4, 1, 6, 10, 3, 9, 8}\uc744 \uc608\ub85c\ub4e4\uc5b4 \ubcf4\uc790. 10\uac1c\uc758 node\ub97c \uac00\uc9c0\ub294 tree\ub97c \ubc30\uc5f4\ub85c \uad6c\ud604 \ud560 \ub54c, \ubd80\ubaa8 node\ub4e4\uc758 index\ub294 <strong>\uc18c\uc22b\uc810_\ubc84\ub9bc(N\/2) &#8211; 1<\/strong>\ub85c \uacc4\uc0b0\ud560 \uc218 \uc788\ub2e4. \ub530\ub77c\uc11c 10\uac1c\uc758 node\ub97c \uac00\uc9c0\ub294 \uc774 tree\uc758 \ubd80\ubaa8 node\ub4e4\uc758 \uc704\uce58\ub294 [0], [1], [2], [3], [4]\uc774\ub2e4. (C\/C++\ub85c \uad6c\ud604 \ud560\ub54c\ub294 N\/2\ud55c \uac12\uc744 \uadf8\ub0e5 int\ud615 \ubcc0\uc218\uc5d0 \ub123\uc73c\uba74 \ub41c\ub2e4)<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"720\" src=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_initail.png\" alt=\"\" class=\"wp-image-1609\" srcset=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_initail.png 960w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_initail-300x225.png 300w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_initail-768x576.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure><\/div>\n\n\n\n<p>\uac01 \ubd80\ubaa8 node\ub4e4\uacfc \uc790\uc2dd node\ub4e4\uc744 subtree\ub77c\uace0 \ud558\uba74 \uc774 \uc608\uc81c\ub294 \ub2e4\uc74c\uacfc \uac19\uc774 5\uac1c\uc758 subtree\ub4e4\ub85c \uad6c\ubd84\ub420 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"720\" src=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtrees-1.png\" alt=\"\" class=\"wp-image-1619\" srcset=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtrees-1.png 960w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtrees-1-300x225.png 300w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtrees-1-768x576.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Heapify &#8211; Subtree A<\/h2>\n\n\n\n<p>\ubd80\ubaa8\uc778 4\ubc88\uc9f8 index\uc758 \uac12\uacfc \ud558\ub098 \ubc16\uc5d0 \uc5c6\ub294 \uc790\uc2dd\uc778 9\ubc88\uc9f8 index\uc758 \uac12\uc744 \ube44\uad50\ud55c\ub2e4. \uc790\uc2dd\uc758 \uac12\uc774 \ub354 \ud06c\ubbc0\ub85c \ubd80\ubaa8\uc640 swap()\ud55c\ub2e4.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"720\" src=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesA.png\" alt=\"\" class=\"wp-image-1621\" srcset=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesA.png 960w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesA-300x225.png 300w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesA-768x576.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Heapify &#8211; Subtree B<\/h2>\n\n\n\n<p>\ubd80\ubaa8\uc778 3\ubc88\uc9f8 index\uc640 \uc67c\ucabd \uc790\uc2dd\uc778 7\ubc88\uc9f8, \uc624\ub978\ucabd \uc790\uc2dd\uc778 8\ubc88\uc9f8\ub97c \ube44\uad50\ud574\uc11c \uac00\uc7a5 \ud070 \uc624\ub978\ucabd \uc790\uc2dd\uacfc \ubd80\ubaa8 node\ub97c swap()\ud55c\ub2e4.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"720\" src=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesB.png\" alt=\"\" class=\"wp-image-1622\" srcset=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesB.png 960w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesB-300x225.png 300w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesB-768x576.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Heapify &#8211; Subtree C<\/h2>\n\n\n\n<p>\uc624\ub978\ucabd \uc790\uc2dd\uc778 index 6\ubc88\uacfc \ubd80\ubaa8\uc778 index 2\ubc88\uc744 \uad50\uccb4\ud55c\ub2e4.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"720\" src=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesC.png\" alt=\"\" class=\"wp-image-1623\" srcset=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesC.png 960w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesC-300x225.png 300w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesC-768x576.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Heapify &#8211; Subtree D<\/h2>\n\n\n\n<p>1\ubc88 index\uc758 \uc67c\ucabd \uc790\uc2dd\uc774 \ub354 \ud06c\ubbc0\ub85c \ubd80\ubaa8\uc640 swap()\ud55c\ub2e4.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"720\" src=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesD.png\" alt=\"\" class=\"wp-image-1624\" srcset=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesD.png 960w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesD-300x225.png 300w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesD-768x576.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Heapify &#8211; Subtree E<\/h2>\n\n\n\n<p>2\ubc88 index\uc758 \uac12\uc774 \ub354 \ucee4\uc11c \ubd80\ubaa8\uc778 0\ubc88 index\uc640 swap()\ud558\uace0 \ubcf4\ub2c8 2\ubc88 index\ub97c \ubd80\ubaa8\ub85c \ud558\ub294 subtree\uac00 \ub354\uc774\uc0c1 max heap\uc774 \uc544\ub2c8\uac8c \ub41c\ub2e4.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"720\" src=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesE_1.png\" alt=\"\" class=\"wp-image-1625\" srcset=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesE_1.png 960w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesE_1-300x225.png 300w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesE_1-768x576.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure><\/div>\n\n\n\n<p>\uadf8\ub798\uc11c \ub2e4\uc2dc \ud55c\ubc88 heapify()\ub97c \ud638\ucd9c\ud574\uc11c max heap\uc744 \ub9cc\ub4e0\ub2e4.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"720\" src=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesE_2.png\" alt=\"\" class=\"wp-image-1626\" srcset=\"https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesE_2.png 960w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesE_2-300x225.png 300w, https:\/\/litcoder.com\/wp-content\/uploads\/2017\/05\/heaptreeEX_build_heap_subtreesE_2-768x576.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure><\/div>\n\n\n\n<h1 class=\"wp-block-heading\">Code<\/h1>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"eclipse\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"true\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/*\n  Name: buildHeapTree\n  Desc.: Makes sure all sub-trees to be max heapified.\n  Args.:\n    - arr : Pointer to array to be sorted.\n    - arrSize : Size of the array.\n*\/\nstatic void buildHeapTree(int* arr, int arrSize)\n{\n    int parentIdx = (arrSize \/ 2) - 1;\n    int arrayLastIdx = arrSize - 1;\n \n    for(; parentIdx >= 0; parentIdx--)\n    {\n        maxHeapify(arr, arrayLastIdx, parentIdx);\n    }\n}<\/pre>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"eclipse\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"true\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\/*\n  Name: swap\n  Desc.: Exchanges two elements of the array 'arr' that two given indices indicates.\n  Args.:\n    - arr: Pointer to array to be sorted.\n    - idx1, idx2 : Two indices to be swapped.\n*\/\nstatic void swap(int* arr, int idx1, int idx2)\n{\n    int t = std::move(arr[idx1]);\n    arr[idx1] = std::move(arr[idx2]);\n    arr[idx2] = std::move(t);\n}\n\n \n\/*\n  Name: maxHeapify\n  Desc.: Makes given tree and it's sub-trees to be max heap trees.\n  Args:\n    - arr : Pointer to array to be sorted.\n    - arrayLastIdx : Last index of the given array.\n    - parentIdx : Index of the parent node of the tree.\n*\/\nstatic void maxHeapify(int* arr, int arrayLastIdx, int parentIdx)\n{\n    int lcIdx = (parentIdx * 2) + 1;  \/\/ Index for left child node.\n    int rcIdx = lcIdx + 1;            \/\/ Index for right child node.\n    int biggerChildIdx = lcIdx;       \/\/ Index for child that has bigger value.\n \n    \/\/ Stop recursion if left child index exceeds last index of the array.\n    if(lcIdx > arrayLastIdx)\n        return;\n \n    \/\/ Left child would be the only one if there's no right child. \n    if(rcIdx > arrayLastIdx)\n        biggerChildIdx = lcIdx;\n    else   \/\/ Which of left\/right is bigger if both are exits?\n        biggerChildIdx = (arr[lcIdx] &lt; arr[rcIdx]) ? rcIdx : lcIdx;\n \n    \/\/ Swap and heapify if child is bigger than parent.\n    if(arr[parentIdx] &lt; arr[biggerChildIdx])\n    {\n        swap(arr, parentIdx, biggerChildIdx);\n        maxHeapify(arr, arrayLastIdx, biggerChildIdx);\n    }\n \n    return;\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Heap tree\ub294 \uc644\uc804\uc774\uc9c4\ud2b8\ub9ac \ud615\ud0dc\ub85c \ubaa8\ub4e0 \ubd80\ubaa8 \ub178\ub4dc\uc758 \uac12\uc774 \uc790\uc2dd \ub178\ub4dc \ubcf4\ub2e4 \ud06c\uac70\ub098 (max heap) \ubaa8\ub4e0 \ubd80\ubaa8 \ub178\ub4dc\uc758 \uac12\uc774 \uc790\uc2dd \ub178\ub4dc \ubcf4\ub2e4 \uc791\uc740 (min heap) tree\ub97c \ub9d0\ud55c\ub2e4. \uc774 \uae00\uc5d0\uc11c\ub294 max heap tree\ub97c \ub9cc\ub4dc\ub294 \ubc29\ubc95\uc744 \uc54c\uc544\ubcf8\ub2e4. Heap tree\ub97c \uc0dd\uc131\ud558\ub294 buildHeapTree()\uc774 \ub3d9\uc791\ud558\ub294 \uc808\ucc28\ub294 \ub2e4\uc74c\uacfc \uac19\ub2e4. N\uc740 \uc6d0\uc18c\uc758 \uac2f\uc218. \uc7ac\uadc0\ub85c \uad6c\ud604\ub41c heapify()\uac00 \ub4f1\uc7a5\ud558\ub294\ub370, \uc774 \ud568\uc218\uac00 \ud558\ub294 \uc5ed\ud560\uc740 \uc8fc\uc5b4\uc9c4 node\ub97c [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[5],"tags":[10,62,135],"class_list":["post-1606","post","type-post","status-publish","format-standard","hentry","category-programming","tag-algorithm","tag-heap","tag-tree"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/litcoder.com\/index.php?rest_route=\/wp\/v2\/posts\/1606","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/litcoder.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/litcoder.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/litcoder.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/litcoder.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1606"}],"version-history":[{"count":25,"href":"https:\/\/litcoder.com\/index.php?rest_route=\/wp\/v2\/posts\/1606\/revisions"}],"predecessor-version":[{"id":3715,"href":"https:\/\/litcoder.com\/index.php?rest_route=\/wp\/v2\/posts\/1606\/revisions\/3715"}],"wp:attachment":[{"href":"https:\/\/litcoder.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1606"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/litcoder.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1606"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/litcoder.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1606"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}