{"id":624,"date":"2022-07-24T02:25:24","date_gmt":"2023-05-03T06:06:51","guid":{"rendered":"https:\/\/www.silicloud.com\/ja\/blog\/index.php\/2023\/11\/30\/%e6%9c%80%e5%b0%8f%e3%83%92%e3%83%bc%e3%83%97%e3%81%ae%e4%ba%8c%e5%88%86%e6%9c%a8\/"},"modified":"2025-08-01T01:09:55","modified_gmt":"2025-07-31T16:09:55","slug":"%e6%9c%80%e5%b0%8f%e3%83%92%e3%83%bc%e3%83%97%e3%81%ae%e4%ba%8c%e5%88%86%e6%9c%a8","status":"publish","type":"post","link":"https:\/\/www.silicloud.com\/ja\/blog\/%e6%9c%80%e5%b0%8f%e3%83%92%e3%83%bc%e3%83%97%e3%81%ae%e4%ba%8c%e5%88%86%e6%9c%a8\/","title":{"rendered":"\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728"},"content":{"rendered":"

\u6700\u5c0f\u30d2\u30fc\u30d7\u4e8c\u5206\u6728\u3068\u306f\u3001\u6839\u30ce\u30fc\u30c9\u304c\u6728\u5185\u3067\u6700\u5c0f\u306e\u30ad\u30fc\u3092\u6301\u3064\u4e8c\u5206\u6728\u3067\u3042\u308b\u3002<\/p>\n

\u4e0a\u8a18\u306e\u5b9a\u7fa9\u306f\u3001\u6728\u306e\u3059\u3079\u3066\u306e\u30b5\u30d6\u30c4\u30ea\u30fc\u306b\u5f53\u3066\u306f\u307e\u308a\u307e\u3059\u3002\u3053\u308c\u3092\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u7279\u6027\u3068\u547c\u3073\u307e\u3059\u3002<\/p>\n

\u6700\u5f8c\u306e2\u3064\u306e\u5c64\u4ee5\u5916\u306e\u307b\u307c\u3059\u3079\u3066\u306e\u30ce\u30fc\u30c9\u306f\u30012\u3064\u306e\u5b50\u30ce\u30fc\u30c9\u3092\u6301\u3063\u3066\u3044\u308b\u5fc5\u8981\u304c\u3042\u308a\u307e\u3059\u3002\u3064\u307e\u308a\u3001\u6700\u5f8c\u306e2\u3064\u306e\u5c64\u3092\u9664\u3044\u3066\u3001\u307b\u307c\u5b8c\u5168\u306a\u4e8c\u5206\u6728\u3067\u3059\u3002<\/p>\n

\u4ee5\u4e0b\u306e\u6728\u306f\u3001\u4e0a\u8a18\u306e2\u3064\u306e\u7279\u6027\u304c\u6e80\u305f\u3055\u308c\u3066\u3044\u308b\u306e\u3067\u3001\u6700\u5c0f\u30d2\u30fc\u30d7\u4e8c\u5206\u6728\u306e\u4f8b\u3067\u3059\u3002<\/p>\n

\"Min<\/div>\n

\u300c\u6700\u5c0f\u30d2\u30fc\u30d7\u6728\u300d\u306e\u6982\u8981\u3092\u8aac\u660e\u3057\u305f\u306e\u3067\u3001\u305d\u306e\u8868\u73fe\u65b9\u6cd5\u3092\u898b\u3066\u307f\u307e\u3057\u3087\u3046\u3002<\/p>\n

\n

\u30df\u30f3\u30d2\u30fc\u30d7\u30c4\u30ea\u30fc\u306e\u8868\u73fe<\/h2>\n

\u30df\u30f3\u30d2\u30fc\u30d7\u4e8c\u5206\u6728\u306f\u3001\u4e00\u822c\u7684\u306b\u306f\u4ee5\u4e0b\u306e\u5f62\u5f0f\u306b\u5f93\u3063\u3066\u30a4\u30f3\u30c7\u30c3\u30af\u30b9\u5316\u3055\u308c\u305f\u914d\u5217\u3068\u3057\u3066\u8868\u3055\u308c\u307e\u3059\u3002<\/p>\n

\n
\n\n\n\n\n\n\n\n\n
<\/th>\n<\/th>\n<\/tr>\n<\/thead>\n
Current Node<\/td>\narr[i]<\/code><\/td>\n<\/tr>\n
Parent Node<\/td>\narr[(i-1)\/2]<\/code><\/td>\n<\/tr>\n
Left Child<\/td>\narr[(2*i) + 1]<\/code><\/td>\n<\/tr>\n
Right Child<\/td>\narr[(2*i )+ 2]<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n

\u5168\u4f53\u306e\u6728\u306e\u6839\u306farr[0]\u306b\u3042\u308a\u307e\u3059\u3002<\/p>\n

\u4e0b\u306e\u56f3\u306b\u793a\u3055\u308c\u3066\u3044\u308b\u3088\u3046\u306b\u3001\u79c1\u305f\u3061\u306f\u30a4\u30f3\u30c7\u30c3\u30af\u30b9\u3092\u4f7f\u7528\u3057\u307e\u3059\u3002\u3053\u306e\u30d1\u30bf\u30fc\u30f3\u306f\u975e\u5e38\u306b\u308f\u304b\u308a\u3084\u3059\u304f\u3001\u4e0a\u8a18\u306e\u8868\u3068\u4e00\u81f4\u3059\u308b\u3067\u3057\u3087\u3046\u3002<\/p>\n

\"Min<\/div>\n

\u3053\u306e\u30a4\u30f3\u30c7\u30c3\u30af\u30b9\u4ed8\u3051\u306f\u3001\u30d0\u30a4\u30ca\u30ea\u30c4\u30ea\u30fc\u306e\u30ec\u30d9\u30eb\u9806\u30c8\u30e9\u30d0\u30fc\u30b5\u30eb\u306b\u5f93\u3044\u307e\u3059\u306e\u3067\u3001\u30d0\u30a4\u30ca\u30ea\u30d2\u30fc\u30d7\u914d\u5217\u306f\u30ec\u30d9\u30eb\u9806\u30c8\u30e9\u30d0\u30fc\u30b5\u30eb\u3092\u4f7f\u7528\u3057\u305f\u30d0\u30a4\u30ca\u30ea\u30c4\u30ea\u30fc\u3067\u3059\u3002<\/p>\n

\"Min<\/div>\n

\u4e0a\u306e\u56f3\u306f\u3001\u6700\u5c0f\u30d2\u30fc\u30d7\u30c4\u30ea\u30fc\u306e\u914d\u5217\u8868\u73fe\u3092\u793a\u3057\u3066\u3044\u307e\u3059\u3002<\/p>\n

\u4eca\u306e\u6982\u5ff5\u3092\u30ab\u30d0\u30fc\u3057\u305f\u306e\u3067\u3001\u6b21\u306fC\u3067\u306e\u5b9f\u88c5\u306b\u79fb\u308a\u307e\u3057\u3087\u3046\u3002<\/p>\n

\n

\u30df\u30cb\u30d2\u30fc\u30d7\u6728\u306e\u5b9f\u88c5<\/h2>\n

\u914d\u5217\u8868\u73fe\u3092\u4f7f\u7528\u3057\u3066\u6728\u3092\u69cb\u7bc9\u3057\u307e\u3059\u3002\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u69cb\u9020\u3092\u66f8\u304d\u59cb\u3081\u307e\u3057\u3087\u3046\u3002 (Hairetsu hy\u014dgen o shiy\u014d shite ki o k\u014dchiku shimasu. Saish\u014d h\u012bpu no k\u014dz\u014d o kakishidemashou.)<\/p>\n

typedef<\/span> struct<\/span> MinHeap<\/span> MinHeap;<\/span>\r\nstruct<\/span> MinHeap<\/span> {<\/span>\r\n    int<\/span>*<\/span> arr;<\/span>\r\n    \/\/ Current Size of the Heap<\/span>\r\n    int<\/span> size;<\/span>\r\n    \/\/ Maximum capacity of the heap<\/span>\r\n    int<\/span> capacity;<\/span>\r\n}<\/span>;<\/span>\r\n<\/code><\/pre>\n
\u79c1\u305f\u3061\u306f\u8981\u7d20\u306e\u914d\u5217\u3068\u30b5\u30a4\u30ba\u3092\u6301\u3061\u307e\u3059\u3002\u8981\u7d20\u304c\u633f\u5165\u307e\u305f\u306f\u524a\u9664\u3055\u308c\u308b\u3068\u30b5\u30a4\u30ba\u304c\u66f4\u65b0\u3055\u308c\u307e\u3059\u3002<\/p>\n
\u914d\u5217\u306b\u306f\u3001\u6700\u5927\u30b5\u30a4\u30ba\u3092\u793a\u3059\u5bb9\u91cf\u3082\u3042\u308a\u307e\u3059\u3002<\/p>\n
\u30df\u30cb\u30d2\u30fc\u30d7\u6728\u3092\u8868\u3059\u305f\u3081\u306b\u3001\u89aa\u3084\u5b50\u4f9b\u3092\u898b\u3064\u3051\u308b\u3068\u3044\u3063\u305f\u3044\u304f\u3064\u304b\u306e\u95a2\u6570\u3092\u66f8\u304f\u5fc5\u8981\u304c\u3042\u308a\u307e\u3059\u3002<\/p>\n
int<\/span> parent<\/span>(<\/span>int<\/span> i)<\/span> {<\/span>\r\n    \/\/ Get the index of the parent<\/span>\r\n    return<\/span> (<\/span>i -<\/span> 1<\/span>)<\/span> \/<\/span> 2<\/span>;<\/span>\r\n}<\/span>\r\n\r\nint<\/span> left_child<\/span>(<\/span>int<\/span> i)<\/span> {<\/span>\r\n    return<\/span> (<\/span>2<\/span>*<\/span>i +<\/span> 1<\/span>)<\/span>;<\/span>\r\n}<\/span>\r\n\r\nint<\/span> right_child<\/span>(<\/span>int<\/span> i)<\/span> {<\/span>\r\n    return<\/span> (<\/span>2<\/span>*<\/span>i +<\/span> 2<\/span>)<\/span>;<\/span>\r\n}<\/span>\r\n\r\nint<\/span> get_min<\/span>(<\/span>MinHeap*<\/span> heap)<\/span> {<\/span>\r\n    \/\/ Return the root node element,<\/span>\r\n    \/\/ since that's the minimum, by the min-heap<\/span>\r\n    \/\/ property<\/span>\r\n    return<\/span> heap-><\/span>arr[<\/span>0<\/span>]<\/span>;<\/span>\r\n}<\/span>\r\n<\/code><\/pre>\n
\u30d2\u30fc\u30d7\u3092\u521d\u671f\u5316\u304a\u3088\u3073\u89e3\u653e\u3059\u308b\u95a2\u6570\u3092\u4f5c\u6210\u3057\u307e\u3059\u3002<\/p>\n
MinHeap*<\/span> init_minheap<\/span>(<\/span>int<\/span> capacity)<\/span> {<\/span>\r\n    MinHeap*<\/span> minheap =<\/span> (<\/span>MinHeap*<\/span>)<\/span> calloc<\/span> (<\/span>1<\/span>,<\/span> sizeof<\/span>(<\/span>MinHeap)<\/span>)<\/span>;<\/span>\r\n    minheap-><\/span>arr =<\/span> (<\/span>int<\/span>*<\/span>)<\/span> calloc<\/span> (<\/span>capacity,<\/span> sizeof<\/span>(<\/span>int<\/span>)<\/span>)<\/span>;<\/span>\r\n    minheap-><\/span>capacity =<\/span> capacity;<\/span>\r\n    minheap-><\/span>size =<\/span> 0<\/span>;<\/span>\r\n    return<\/span> minheap;<\/span>\r\n}<\/span>\r\n\r\nvoid<\/span> free_minheap<\/span>(<\/span>MinHeap*<\/span> heap)<\/span> {<\/span>\r\n    if<\/span> (<\/span>!<\/span>heap)<\/span>\r\n        return<\/span>;<\/span>\r\n    free<\/span>(<\/span>heap-><\/span>arr)<\/span>;<\/span>\r\n    free<\/span>(<\/span>heap)<\/span>;<\/span>\r\n}<\/span>\r\n<\/code><\/pre>\n
\u305d\u308c\u304c\u30ab\u30d0\u30fc\u3055\u308c\u305f\u306e\u3067\u3001\u3067\u306f\u3001\u6b21\u306b\u8981\u7d20\u3092\u633f\u5165\u3059\u308b\u65b9\u6cd5\u306b\u79fb\u308a\u307e\u3057\u3087\u3046\uff01<\/p>\n
Min Heap \u306b\u633f\u5165\u3059\u308b\u3002<\/h2>\n
\u633f\u5165\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u30b7\u30f3\u30d7\u30eb\u3067\u3059\u3002\u3053\u308c\u306f\u8981\u7d20\u3092\u6728\u306b\u633f\u5165\u3057\u307e\u3059\u3002<\/p>\n
\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u89e3\u8aac\u3092\u5206\u304b\u308a\u3084\u3059\u304f\u8ff0\u3079\u308b\u3002<\/p>\n
    \n
  • First, always insert at the bottom of the tree. The initial position of the inserted element is at the last level.<\/li>\n
  • We will now need to update the position of this element so that the min-heap property is satisfied.<\/li>\n
  • Since the root node of every sub-tree must be the minimum, check the sub-tree of its immediate parent.<\/li>\n
  • If the parent is greater than this inserted element, we need to update its position by swapping it.<\/li>\n
  • But we are not yet done, since the min-heap property may be violated of the updated node\u2019s sub-tree!<\/li>\n
  • We need to keep swapping until we reach the root node, after which we are done.<\/li>\n<\/ul>\n
    \u3053\u306e\u624b\u9806\u3092\u7406\u89e3\u3059\u308b\u305f\u3081\u306b\u3001\u4f8b\u3092\u6319\u3052\u307e\u3057\u3087\u3046\u3002 (Kono shorui wo rikai suru tameni, rei wo agemashou.)<\/p>\n
    \u4e0b\u8a18\u306e\u6728\u3092\u8003\u3048\u3066\u307f\u3066\u304f\u3060\u3055\u3044\u3002\u8981\u7d20\u306f\u305f\u30601\u3064\u3060\u3051\u3067\u3059\u3002<\/p>\n
    \"Min<\/div>\n
    \u30a8\u30ec\u30e1\u30f3\u30c840\u3092\u633f\u5165\u3057\u307e\u3057\u3087\u3046\u3002\u30a8\u30ec\u30e1\u30f3\u30c8\u304c1\u3064\u3060\u3051\u306a\u306e\u3067\u3001\u4e00\u756a\u4e0b\u306b\u633f\u5165\u3055\u308c\u3001\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u6027\u8cea\u304c\u6e80\u305f\u3055\u308c\u3066\u3044\u308b\u3053\u3068\u304c\u308f\u304b\u308a\u307e\u3059\u3002\u306a\u305c\u306a\u308910\u306f40\u3088\u308a\u3082\u5c0f\u3055\u3044\u304b\u3089\u3067\u3059\u3002\u3060\u304b\u3089\u4ea4\u63db\u3059\u308b\u5fc5\u8981\u306f\u3042\u308a\u307e\u305b\u3093\u3002<\/p>\n
    \"Min<\/div>\n
    \u6b21\u306b\u300150\u3092\u633f\u5165\u3057\u307e\u3059\u3002\u540c\u69d8\u306e\u624b\u7d9a\u304d\u304c\u7d9a\u304d\u307e\u3059\u3002<\/p>\n
    \"Min<\/div>\n
    \u6b21\u306b\u30015\u3092\u633f\u5165\u3057\u307e\u3059\u3002\u3053\u308c\u3067\u3001\u307e\u305a\u306f\u30c4\u30ea\u30fc\u306e\u4e00\u756a\u4e0b\u306b\u3001\u30a4\u30f3\u30c7\u30c3\u30af\u30b93\u306b\u633f\u5165\u3057\u307e\u3059\u3002<\/p>\n
    \"Min<\/div>\n
    \u90e8\u5206\u67281-3\u306b\u304a\u3044\u3066\u3001\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u6761\u4ef6\u304c\u7834\u3089\u308c\u3066\u3044\u308b\u305f\u3081\u3001\u5168\u4f53\u306e\u6728\u3067\u3082\u540c\u69d8\u3067\u3059\u3002\u3057\u305f\u304c\u3063\u3066\u3001\u30eb\u30fc\u30c8\u306b\u5230\u9054\u3059\u308b\u307e\u3067\u89aa\u3068\u4ea4\u63db\u3057\u7d9a\u3051\u308b\u5fc5\u8981\u304c\u3042\u308a\u307e\u3059\u3002<\/p>\n
    \"Swap<\/div>\n
    \u3060\u304b\u3089\u3001\u518d\u30730\u756a\u30ce\u30fc\u30c9\u3092\u6839\u3068\u3059\u308b\u90e8\u5206\u6728\u3067\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u6027\u8cea\u304c\u7834\u3089\u308c\u3066\u3044\u308b\u305f\u3081\u3001\u3082\u30461\u3064\u306e\u30b9\u30ef\u30c3\u30d7\u304c\u5fc5\u8981\u3067\u3059\u3002<\/p>\n
    \"Min<\/div>\n
    \u308f\u304b\u308a\u307e\u3057\u305f\u3002\u30a4\u30e1\u30fc\u30b8\u304c\u3067\u304d\u305f\u306e\u3067\u3001\u305d\u308c\u3092\u66f8\u304d\u307e\u3057\u3087\u3046\uff01(Wakarimashita. Im\u0113ji ga dekita node, sore o kakimashou!)<\/p>\n
    MinHeap*<\/span> insert_minheap<\/span>(<\/span>MinHeap*<\/span> heap,<\/span> int<\/span> element)<\/span> {<\/span>\r\n    \/\/ Inserts an element to the min heap<\/span>\r\n    \/\/ We first add it to the bottom (last level)<\/span>\r\n    \/\/ of the tree, and keep swapping with it's parent<\/span>\r\n    \/\/ if it is lesser than it. We keep doing that until<\/span>\r\n    \/\/ we reach the root node. So, we will have inserted the<\/span>\r\n    \/\/ element in it's proper position to preserve the min heap property<\/span>\r\n    if<\/span> (<\/span>heap-><\/span>size ==<\/span> heap-><\/span>capacity)<\/span> {<\/span>\r\n        fprintf<\/span>(<\/span>stderr<\/span>,<\/span> \"Cannot insert %d. Heap is already full!\\n\"<\/span>,<\/span> element)<\/span>;<\/span>\r\n        return<\/span> heap;<\/span>\r\n    }<\/span>\r\n    \/\/ We can add it. Increase the size and add it to the end<\/span>\r\n    heap-><\/span>size++<\/span>;<\/span>\r\n    heap-><\/span>arr[<\/span>heap-><\/span>size -<\/span> 1<\/span>]<\/span> =<\/span> element;<\/span>\r\n\r\n    \/\/ Keep swapping until we reach the root<\/span>\r\n    int<\/span> curr =<\/span> heap-><\/span>size -<\/span> 1<\/span>;<\/span>\r\n    \/\/ As long as you aren't in the root node, and while the <\/span>\r\n    \/\/ parent of the last element is greater than it<\/span>\r\n    while<\/span> (<\/span>curr ><\/span> 0<\/span> &&<\/span> heap-><\/span>arr[<\/span>parent<\/span>(<\/span>curr)<\/span>]<\/span> ><\/span> heap-><\/span>arr[<\/span>curr]<\/span>)<\/span> {<\/span>\r\n        \/\/ Swap<\/span>\r\n        int<\/span> temp =<\/span> heap-><\/span>arr[<\/span>parent<\/span>(<\/span>curr)<\/span>]<\/span>;<\/span>\r\n        heap-><\/span>arr[<\/span>parent<\/span>(<\/span>curr)<\/span>]<\/span> =<\/span> heap-><\/span>arr[<\/span>curr]<\/span>;<\/span>\r\n        heap-><\/span>arr[<\/span>curr]<\/span> =<\/span> temp;<\/span>\r\n        \/\/ Update the current index of element<\/span>\r\n        curr =<\/span> parent<\/span>(<\/span>curr)<\/span>;<\/span>\r\n    }<\/span>\r\n    return<\/span> heap;<\/span> \r\n}<\/span>\r\n<\/code><\/pre>\n
    \u4eca\u3001\u524a\u9664\u30e1\u30bd\u30c3\u30c9\u3092\u5b9f\u88c5\u3057\u307e\u3059\u3002<\/p>\n
    \u30df\u30f3\u30d2\u30fc\u30d7\u304b\u3089\u524a\u9664\u3057\u3066\u304f\u3060\u3055\u3044\u3002<\/h2>\n
    \u79c1\u305f\u3061\u306f\u3001\u30a4\u30f3\u30c7\u30c3\u30af\u30b9\u306e\u3069\u306e\u8981\u7d20\u3092\u524a\u9664\u3059\u308b\u304b\u3092\u898b\u308b\u524d\u306b\u3001\u6700\u5c0f\u30d2\u30fc\u30d7\u306f\u6839\u3068\u975e\u5e38\u306b\u5bc6\u63a5\u306b\u95a2\u9023\u3057\u3066\u3044\u308b\u305f\u3081\u3001\u307e\u305a\u6839\u3092\u524a\u9664\u3059\u308b\u3053\u3068\u3092\u8003\u3048\u307e\u3059\u3002<\/p>\n
    \u6700\u5c0f\u306e\u8981\u7d20\uff08\u3064\u307e\u308a\u6839\uff09\u3092\u524a\u9664\u3059\u308b\u305f\u3081\u306b\u3001\u4ee5\u4e0b\u306e\u624b\u9806\u3092\u884c\u3044\u307e\u3059\u3002<\/p>\n
      \n
    • Update the root as the last element of the array (tree)<\/li>\n
    • We will now remove the last element at the bottom. This is similar to swapping and deleting at the end! Only because we don\u2019t care about the root value anymore, we simply update it instead.<\/li>\n
    • The problem again is that we need to maintain the min-heap property.<\/li>\n
    • So we must ensure that the whole tree maintains this property. We will use a function called heapify() to do this for us.<\/li>\n<\/ul>\n
      \u3067\u3059\u304b\u3089\u3001\u79c1\u305f\u3061\u306f\u30d2\u30fc\u30d7\u5316\uff08heapify()\uff09\u30e1\u30bd\u30c3\u30c9\u3092\u884c\u3063\u305f\u5f8c\u306b\u3001\u524a\u9664\u65b9\u6cd5\u304c\u5b8c\u4e86\u3059\u308b\u3053\u3068\u3092\u77e5\u3063\u3066\u3044\u307e\u3059\u3002<\/p>\n
      MinHeap*<\/span> delete_minimum<\/span>(<\/span>MinHeap*<\/span> heap)<\/span> {<\/span>\r\n    \/\/ Deletes the minimum element, at the root<\/span>\r\n    if<\/span> (<\/span>!<\/span>heap ||<\/span> heap-><\/span>size ==<\/span> 0<\/span>)<\/span>\r\n        return<\/span> heap;<\/span>\r\n\r\n    int<\/span> size =<\/span> heap-><\/span>size;<\/span>\r\n    int<\/span> last_element =<\/span> heap-><\/span>arr[<\/span>size-<\/span>1<\/span>]<\/span>;<\/span>\r\n    \r\n    \/\/ Update root value with the last element<\/span>\r\n    heap-><\/span>arr[<\/span>0<\/span>]<\/span> =<\/span> last_element;<\/span>\r\n\r\n    \/\/ Now remove the last element, by decreasing the size<\/span>\r\n    heap-><\/span>size--<\/span>;<\/span>\r\n    size--<\/span>;<\/span>\r\n\r\n    \/\/ We need to call heapify(), to maintain the min-heap<\/span>\r\n    \/\/ property<\/span>\r\n    heap =<\/span> heapify<\/span>(<\/span>heap,<\/span> 0<\/span>)<\/span>;<\/span>\r\n    return<\/span> heap;<\/span>\r\n}<\/span>\r\n<\/code><\/pre>\n
      \u30d2\u30fc\u30d7\u6574\u7406\uff08heapify\uff09\u624b\u7d9a\u304d<\/h3>\n
      \u3053\u306e\u6a5f\u80fd\u306f\u8981\u7d20\u306e\u30a4\u30f3\u30c7\u30c3\u30af\u30b9index\u3092\u53d7\u3051\u53d6\u308a\u3001\u5373\u6642\u306e\u30b5\u30d6\u30c4\u30ea\u30fc\u306e\u6700\u5c0f\u306e\u8981\u7d20\u3068\u5165\u308c\u66ff\u3048\u3066\u3001\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u7279\u6027\u3092\u7dad\u6301\u3057\u307e\u3059\u3002<\/p>\n
      \u5f97\u3089\u308c\u308b\u6728\u306f\u3001\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u6027\u8cea\u3092\u6e80\u305f\u3057\u307e\u3059\u3002 (Erareru ki wa, saish\u014d-h\u012bpu no seishitsu o mitashimasu.)<\/p>\n
      \u3053\u306e\u5834\u5408\u3001\u90e8\u5206\u6728\u306e\u6700\u5c0f\u8981\u7d20\u3092\u898b\u3064\u3051\u3066\u3001\u73fe\u5728\u306e\u8981\u7d20\u3068\u4ea4\u63db\u3059\u308b\u3053\u3068\u304c\u5fc5\u8981\u3067\u3059\u3002<\/p>\n
      \u3053\u308c\u304b\u3089\u306f\u3001\u6728\u5168\u4f53\u304c\u3053\u308c\u3092\u6e80\u305f\u3057\u3066\u3044\u308b\u3053\u3068\u3092\u78ba\u8a8d\u3059\u308b\u5fc5\u8981\u304c\u3042\u308a\u307e\u3059\u3002\u305d\u306e\u305f\u3081\u306b\u306f\u3001\u6700\u3082\u5c0f\u3055\u306a\u8981\u7d20\u306b\u5bfe\u3057\u3066\u624b\u9806\u3092\u518d\u5e30\u7684\u306b\u547c\u3073\u51fa\u3057\u3001\u6700\u7d42\u7684\u306b\u306f\u30eb\u30fc\u30c8\u307e\u3067\u5230\u9054\u3059\u308b\u5fc5\u8981\u304c\u3042\u308a\u307e\u3059\u3002<\/p>\n
      MinHeap*<\/span> heapify<\/span>(<\/span>MinHeap*<\/span> heap,<\/span> int<\/span> index)<\/span> {<\/span>\r\n    \/\/ Rearranges the heap as to maintain<\/span>\r\n    \/\/ the min-heap property<\/span>\r\n    if<\/span> (<\/span>heap-><\/span>size <=<\/span> 1<\/span>)<\/span>\r\n        return<\/span> heap;<\/span>\r\n    \r\n    int<\/span> left =<\/span> left_child<\/span>(<\/span>index)<\/span>;<\/span> \r\n    int<\/span> right =<\/span> right_child<\/span>(<\/span>index)<\/span>;<\/span> \r\n\r\n    \/\/ Variable to get the smallest element of the subtree<\/span>\r\n    \/\/ of an element an index<\/span>\r\n    int<\/span> smallest =<\/span> index;<\/span> \r\n    \r\n    \/\/ If the left child is smaller than this element, it is<\/span>\r\n    \/\/ the smallest<\/span>\r\n    if<\/span> (<\/span>left <<\/span> heap-><\/span>size &&<\/span> heap-><\/span>arr[<\/span>left]<\/span> <<\/span> heap-><\/span>arr[<\/span>index]<\/span>)<\/span> \r\n        smallest =<\/span> left;<\/span> \r\n    \r\n    \/\/ Similarly for the right, but we are updating the smallest element<\/span>\r\n    \/\/ so that it will definitely give the least element of the subtree<\/span>\r\n    if<\/span> (<\/span>right <<\/span> heap-><\/span>size &&<\/span> heap-><\/span>arr[<\/span>right]<\/span> <<\/span> heap-><\/span>arr[<\/span>smallest]<\/span>)<\/span> \r\n        smallest =<\/span> right;<\/span> \r\n\r\n    \/\/ Now if the current element is not the smallest,<\/span>\r\n    \/\/ swap with the current element. The min heap property<\/span>\r\n    \/\/ is now satisfied for this subtree. We now need to<\/span>\r\n    \/\/ recursively keep doing this until we reach the root node,<\/span>\r\n    \/\/ the point at which there will be no change!<\/span>\r\n    if<\/span> (<\/span>smallest !=<\/span> index)<\/span> \r\n    {<\/span> \r\n        int<\/span> temp =<\/span> heap-><\/span>arr[<\/span>index]<\/span>;<\/span>\r\n        heap-><\/span>arr[<\/span>index]<\/span> =<\/span> heap-><\/span>arr[<\/span>smallest]<\/span>;<\/span>\r\n        heap-><\/span>arr[<\/span>smallest]<\/span> =<\/span> temp;<\/span>\r\n        heap =<\/span> heapify<\/span>(<\/span>heap,<\/span> smallest)<\/span>;<\/span> \r\n    }<\/span>\r\n\r\n    return<\/span> heap;<\/span>\r\n}<\/span>\r\n<\/code><\/pre>\n
      \u4eca\u3001delete_minimum()\u95a2\u6570\u3092\u62e1\u5f35\u3057\u3066\u3001\u4efb\u610f\u306e\u8981\u7d20\u3092\u524a\u9664\u3067\u304d\u308b\u3088\u3046\u306b\u3059\u308b\u3053\u3068\u304c\u3067\u304d\u307e\u3059\u3002<\/p>\n
      \u4efb\u610f\u306e\u8981\u7d20\u3092\u524a\u9664\u3059\u308b<\/h2>\n
      \u73fe\u5728\u306e\u6700\u5c0f\u5024\u3088\u308a\u5c0f\u3055\u304f\u306a\u308b\u3088\u3046\u3001\u5e0c\u671b\u3059\u308b\u8981\u7d20\u3092\u6700\u5c0f\u53ef\u80fd\u5024\u306b\u8a2d\u5b9a\u3059\u308b\u3060\u3051\u3067\u6e08\u307f\u307e\u3059\u3002\u305d\u308c\u306f get_min() – 1 \u3068\u306a\u308a\u307e\u3059\u3002<\/p>\n
      \u4eca\u304b\u3089\u3001\u65b0\u3057\u3044\u6839\u304c\u3053\u306e\u8981\u7d20\u306b\u306a\u308b\u3088\u3046\u306b\u3001\u4f4d\u7f6e\u3092\u66f4\u65b0\u3059\u308b\u307e\u3067\u3001\u5165\u308c\u66ff\u3048\u3092\u7d9a\u3051\u307e\u3059\u3002<\/p>\n
      \u4eca\u3001\u79c1\u305f\u3061\u306f\u53e4\u3044delete_minimum()\u95a2\u6570\u306b\u623b\u3063\u3066\u304d\u307e\u3057\u305f\uff01\u65b0\u3057\u3044\u6839\u3092\u7c21\u5358\u306b\u524a\u9664\u3059\u308b\u3053\u3068\u304c\u3067\u304d\u307e\u3059\uff01<\/p>\n
      \u3053\u308c\u306b\u3088\u308a\u3001\u79c1\u305f\u3061\u306e\u5168\u4f53\u306e\u524a\u9664\u624b\u9806\u306f\u6b21\u306e\u3088\u3046\u306b\u306a\u308a\u307e\u3059\u3002<\/p>\n
      MinHeap*<\/span> delete_element<\/span>(<\/span>MinHeap*<\/span> heap,<\/span> int<\/span> index)<\/span> {<\/span>\r\n    \/\/ Deletes an element, indexed by index<\/span>\r\n    \/\/ Ensure that it's lesser than the current root<\/span>\r\n    heap-><\/span>arr[<\/span>index]<\/span> =<\/span> get_min<\/span>(<\/span>heap)<\/span> -<\/span> 1<\/span>;<\/span>\r\n    \r\n    \/\/ Now keep swapping, until we update the tree<\/span>\r\n    int<\/span> curr =<\/span> index;<\/span>\r\n    while<\/span> (<\/span>curr ><\/span> 0<\/span> &&<\/span> heap-><\/span>arr[<\/span>parent<\/span>(<\/span>curr)<\/span>]<\/span> ><\/span> heap-><\/span>arr[<\/span>curr]<\/span>)<\/span> {<\/span>\r\n        int<\/span> temp =<\/span> heap-><\/span>arr[<\/span>parent<\/span>(<\/span>curr)<\/span>]<\/span>;<\/span>\r\n        heap-><\/span>arr[<\/span>parent<\/span>(<\/span>curr)<\/span>]<\/span> =<\/span> heap-><\/span>arr[<\/span>curr]<\/span>;<\/span>\r\n        heap-><\/span>arr[<\/span>curr]<\/span> =<\/span> temp;<\/span>\r\n        curr =<\/span> parent<\/span>(<\/span>curr)<\/span>;<\/span>\r\n    }<\/span>\r\n\r\n    \/\/ Now simply delete the minimum element<\/span>\r\n    heap =<\/span> delete_minimum<\/span>(<\/span>heap)<\/span>;<\/span>\r\n    return<\/span> heap;<\/span>\r\n}<\/span>\r\n<\/code><\/pre>\n
      \u3075\u3045\uff01\u3084\u3063\u3068\u7d42\u308f\u308a\u307e\u3057\u305f\u3002\u4eca\u304b\u3089\u3001\u3053\u308c\u307e\u3067\u306e\u30b3\u30fc\u30c9\u3068print()\u95a2\u6570\u3092\u4f7f\u3063\u3066\u3001\u30c4\u30ea\u30fc\u3092\u8996\u899a\u5316\u3057\u307e\u3059\u3002<\/p>\n
      \n
      \u5b8c\u5168\u306a\u30b3\u30fc\u30c9<\/h2>\n
      #<\/span>include<\/span> <stdio.h><\/span><\/span>\r\n#<\/span>include<\/span> <stdlib.h><\/span><\/span>\r\n\r\ntypedef<\/span> struct<\/span> MinHeap<\/span> MinHeap;<\/span>\r\nstruct<\/span> MinHeap<\/span> {<\/span>\r\n    int<\/span>*<\/span> arr;<\/span>\r\n    \/\/ Current Size of the Heap<\/span>\r\n    int<\/span> size;<\/span>\r\n    \/\/ Maximum capacity of the heap<\/span>\r\n    int<\/span> capacity;<\/span>\r\n}<\/span>;<\/span>\r\n\r\nint<\/span> parent<\/span>(<\/span>int<\/span> i)<\/span> {<\/span>\r\n    \/\/ Get the index of the parent<\/span>\r\n    return<\/span> (<\/span>i -<\/span> 1<\/span>)<\/span> \/<\/span> 2<\/span>;<\/span>\r\n}<\/span>\r\n\r\nint<\/span> left_child<\/span>(<\/span>int<\/span> i)<\/span> {<\/span>\r\n    return<\/span> (<\/span>2<\/span>*<\/span>i +<\/span> 1<\/span>)<\/span>;<\/span>\r\n}<\/span>\r\n\r\nint<\/span> right_child<\/span>(<\/span>int<\/span> i)<\/span> {<\/span>\r\n    return<\/span> (<\/span>2<\/span>*<\/span>i +<\/span> 2<\/span>)<\/span>;<\/span>\r\n}<\/span>\r\n\r\nint<\/span> get_min<\/span>(<\/span>MinHeap*<\/span> heap)<\/span> {<\/span>\r\n    \/\/ Return the root node element,<\/span>\r\n    \/\/ since that's the minimum<\/span>\r\n    return<\/span> heap-><\/span>arr[<\/span>0<\/span>]<\/span>;<\/span>\r\n}<\/span>\r\n\r\nMinHeap*<\/span> init_minheap<\/span>(<\/span>int<\/span> capacity)<\/span> {<\/span>\r\n    MinHeap*<\/span> minheap =<\/span> (<\/span>MinHeap*<\/span>)<\/span> calloc<\/span> (<\/span>1<\/span>,<\/span> sizeof<\/span>(<\/span>MinHeap)<\/span>)<\/span>;<\/span>\r\n    minheap-><\/span>arr =<\/span> (<\/span>int<\/span>*<\/span>)<\/span> calloc<\/span> (<\/span>capacity,<\/span> sizeof<\/span>(<\/span>int<\/span>)<\/span>)<\/span>;<\/span>\r\n    minheap-><\/span>capacity =<\/span> capacity;<\/span>\r\n    minheap-><\/span>size =<\/span> 0<\/span>;<\/span>\r\n    return<\/span> minheap;<\/span>\r\n}<\/span>\r\n\r\nMinHeap*<\/span> insert_minheap<\/span>(<\/span>MinHeap*<\/span> heap,<\/span> int<\/span> element)<\/span> {<\/span>\r\n    \/\/ Inserts an element to the min heap<\/span>\r\n    \/\/ We first add it to the bottom (last level)<\/span>\r\n    \/\/ of the tree, and keep swapping with it's parent<\/span>\r\n    \/\/ if it is lesser than it. We keep doing that until<\/span>\r\n    \/\/ we reach the root node. So, we will have inserted the<\/span>\r\n    \/\/ element in it's proper position to preserve the min heap property<\/span>\r\n    if<\/span> (<\/span>heap-><\/span>size ==<\/span> heap-><\/span>capacity)<\/span> {<\/span>\r\n        fprintf<\/span>(<\/span>stderr<\/span>,<\/span> \"Cannot insert %d. Heap is already full!\\n\"<\/span>,<\/span> element)<\/span>;<\/span>\r\n        return<\/span> heap;<\/span>\r\n    }<\/span>\r\n    \/\/ We can add it. Increase the size and add it to the end<\/span>\r\n    heap-><\/span>size++<\/span>;<\/span>\r\n    heap-><\/span>arr[<\/span>heap-><\/span>size -<\/span> 1<\/span>]<\/span> =<\/span> element;<\/span>\r\n\r\n    \/\/ Keep swapping until we reach the root<\/span>\r\n    int<\/span> curr =<\/span> heap-><\/span>size -<\/span> 1<\/span>;<\/span>\r\n    \/\/ As long as you aren't in the root node, and while the <\/span>\r\n    \/\/ parent of the last element is greater than it<\/span>\r\n    while<\/span> (<\/span>curr ><\/span> 0<\/span> &&<\/span> heap-><\/span>arr[<\/span>parent<\/span>(<\/span>curr)<\/span>]<\/span> ><\/span> heap-><\/span>arr[<\/span>curr]<\/span>)<\/span> {<\/span>\r\n        \/\/ Swap<\/span>\r\n        int<\/span> temp =<\/span> heap-><\/span>arr[<\/span>parent<\/span>(<\/span>curr)<\/span>]<\/span>;<\/span>\r\n        heap-><\/span>arr[<\/span>parent<\/span>(<\/span>curr)<\/span>]<\/span> =<\/span> heap-><\/span>arr[<\/span>curr]<\/span>;<\/span>\r\n        heap-><\/span>arr[<\/span>curr]<\/span> =<\/span> temp;<\/span>\r\n        \/\/ Update the current index of element<\/span>\r\n        curr =<\/span> parent<\/span>(<\/span>curr)<\/span>;<\/span>\r\n    }<\/span>\r\n    return<\/span> heap;<\/span> \r\n}<\/span>\r\n\r\nMinHeap*<\/span> heapify<\/span>(<\/span>MinHeap*<\/span> heap,<\/span> int<\/span> index)<\/span> {<\/span>\r\n    \/\/ Rearranges the heap as to maintain<\/span>\r\n    \/\/ the min-heap property<\/span>\r\n    if<\/span> (<\/span>heap-><\/span>size <=<\/span> 1<\/span>)<\/span>\r\n        return<\/span> heap;<\/span>\r\n    \r\n    int<\/span> left =<\/span> left_child<\/span>(<\/span>index)<\/span>;<\/span> \r\n    int<\/span> right =<\/span> right_child<\/span>(<\/span>index)<\/span>;<\/span> \r\n\r\n    \/\/ Variable to get the smallest element of the subtree<\/span>\r\n    \/\/ of an element an index<\/span>\r\n    int<\/span> smallest =<\/span> index;<\/span> \r\n    \r\n    \/\/ If the left child is smaller than this element, it is<\/span>\r\n    \/\/ the smallest<\/span>\r\n    if<\/span> (<\/span>left <<\/span> heap-><\/span>size &&<\/span> heap-><\/span>arr[<\/span>left]<\/span> <<\/span> heap-><\/span>arr[<\/span>index]<\/span>)<\/span> \r\n        smallest =<\/span> left;<\/span> \r\n    \r\n    \/\/ Similarly for the right, but we are updating the smallest element<\/span>\r\n    \/\/ so that it will definitely give the least element of the subtree<\/span>\r\n    if<\/span> (<\/span>right <<\/span> heap-><\/span>size &&<\/span> heap-><\/span>arr[<\/span>right]<\/span> <<\/span> heap-><\/span>arr[<\/span>smallest]<\/span>)<\/span> \r\n        smallest =<\/span> right;<\/span> \r\n\r\n    \/\/ Now if the current element is not the smallest,<\/span>\r\n    \/\/ swap with the current element. The min heap property<\/span>\r\n    \/\/ is now satisfied for this subtree. We now need to<\/span>\r\n    \/\/ recursively keep doing this until we reach the root node,<\/span>\r\n    \/\/ the point at which there will be no change!<\/span>\r\n    if<\/span> (<\/span>smallest !=<\/span> index)<\/span> \r\n    {<\/span> \r\n        int<\/span> temp =<\/span> heap-><\/span>arr[<\/span>index]<\/span>;<\/span>\r\n        heap-><\/span>arr[<\/span>index]<\/span> =<\/span> heap-><\/span>arr[<\/span>smallest]<\/span>;<\/span>\r\n        heap-><\/span>arr[<\/span>smallest]<\/span> =<\/span> temp;<\/span>\r\n        heap =<\/span> heapify<\/span>(<\/span>heap,<\/span> smallest)<\/span>;<\/span> \r\n    }<\/span>\r\n\r\n    return<\/span> heap;<\/span>\r\n}<\/span>\r\n\r\nMinHeap*<\/span> delete_minimum<\/span>(<\/span>MinHeap*<\/span> heap)<\/span> {<\/span>\r\n    \/\/ Deletes the minimum element, at the root<\/span>\r\n    if<\/span> (<\/span>!<\/span>heap ||<\/span> heap-><\/span>size ==<\/span> 0<\/span>)<\/span>\r\n        return<\/span> heap;<\/span>\r\n\r\n    int<\/span> size =<\/span> heap-><\/span>size;<\/span>\r\n    int<\/span> last_element =<\/span> heap-><\/span>arr[<\/span>size-<\/span>1<\/span>]<\/span>;<\/span>\r\n    \r\n    \/\/ Update root value with the last element<\/span>\r\n    heap-><\/span>arr[<\/span>0<\/span>]<\/span> =<\/span> last_element;<\/span>\r\n\r\n    \/\/ Now remove the last element, by decreasing the size<\/span>\r\n    heap-><\/span>size--<\/span>;<\/span>\r\n    size--<\/span>;<\/span>\r\n\r\n    \/\/ We need to call heapify(), to maintain the min-heap<\/span>\r\n    \/\/ property<\/span>\r\n    heap =<\/span> heapify<\/span>(<\/span>heap,<\/span> 0<\/span>)<\/span>;<\/span>\r\n    return<\/span> heap;<\/span>\r\n}<\/span>\r\n\r\nMinHeap*<\/span> delete_element<\/span>(<\/span>MinHeap*<\/span> heap,<\/span> int<\/span> index)<\/span> {<\/span>\r\n    \/\/ Deletes an element, indexed by index<\/span>\r\n    \/\/ Ensure that it's lesser than the current root<\/span>\r\n    heap-><\/span>arr[<\/span>index]<\/span> =<\/span> get_min<\/span>(<\/span>heap)<\/span> -<\/span> 1<\/span>;<\/span>\r\n    \r\n    \/\/ Now keep swapping, until we update the tree<\/span>\r\n    int<\/span> curr =<\/span> index;<\/span>\r\n    while<\/span> (<\/span>curr ><\/span> 0<\/span> &&<\/span> heap-><\/span>arr[<\/span>parent<\/span>(<\/span>curr)<\/span>]<\/span> ><\/span> heap-><\/span>arr[<\/span>curr]<\/span>)<\/span> {<\/span>\r\n        int<\/span> temp =<\/span> heap-><\/span>arr[<\/span>parent<\/span>(<\/span>curr)<\/span>]<\/span>;<\/span>\r\n        heap-><\/span>arr[<\/span>parent<\/span>(<\/span>curr)<\/span>]<\/span> =<\/span> heap-><\/span>arr[<\/span>curr]<\/span>;<\/span>\r\n        heap-><\/span>arr[<\/span>curr]<\/span> =<\/span> temp;<\/span>\r\n        curr =<\/span> parent<\/span>(<\/span>curr)<\/span>;<\/span>\r\n    }<\/span>\r\n\r\n    \/\/ Now simply delete the minimum element<\/span>\r\n    heap =<\/span> delete_minimum<\/span>(<\/span>heap)<\/span>;<\/span>\r\n    return<\/span> heap;<\/span>\r\n}<\/span>\r\n\r\nvoid<\/span> print_heap<\/span>(<\/span>MinHeap*<\/span> heap)<\/span> {<\/span>\r\n    \/\/ Simply print the array. This is an<\/span>\r\n    \/\/ inorder traversal of the tree<\/span>\r\n    printf<\/span>(<\/span>\"Min Heap:\\n\"<\/span>)<\/span>;<\/span>\r\n    for<\/span> (<\/span>int<\/span> i=<\/span>0<\/span>;<\/span> i<<\/span>heap-><\/span>size;<\/span> i++<\/span>)<\/span> {<\/span>\r\n        printf<\/span>(<\/span>\"%d -> \"<\/span>,<\/span> heap-><\/span>arr[<\/span>i]<\/span>)<\/span>;<\/span>\r\n    }<\/span>\r\n    printf<\/span>(<\/span>\"\\n\"<\/span>)<\/span>;<\/span>\r\n}<\/span>\r\n\r\nvoid<\/span> free_minheap<\/span>(<\/span>MinHeap*<\/span> heap)<\/span> {<\/span>\r\n    if<\/span> (<\/span>!<\/span>heap)<\/span>\r\n        return<\/span>;<\/span>\r\n    free<\/span>(<\/span>heap-><\/span>arr)<\/span>;<\/span>\r\n    free<\/span>(<\/span>heap)<\/span>;<\/span>\r\n}<\/span>\r\n\r\nint<\/span> main<\/span>(<\/span>)<\/span> {<\/span>\r\n    \/\/ Capacity of 10 elements<\/span>\r\n    MinHeap*<\/span> heap =<\/span> init_minheap<\/span>(<\/span>10<\/span>)<\/span>;<\/span>\r\n\r\n    insert_minheap<\/span>(<\/span>heap,<\/span> 40<\/span>)<\/span>;<\/span>\r\n    insert_minheap<\/span>(<\/span>heap,<\/span> 50<\/span>)<\/span>;<\/span>\r\n    insert_minheap<\/span>(<\/span>heap,<\/span> 5<\/span>)<\/span>;<\/span>\r\n    print_heap<\/span>(<\/span>heap)<\/span>;<\/span>\r\n    \r\n    \/\/ Delete the heap->arr[1] (50)<\/span>\r\n    delete_element<\/span>(<\/span>heap,<\/span> 1<\/span>)<\/span>;<\/span>\r\n\r\n    print_heap<\/span>(<\/span>heap)<\/span>;<\/span>\r\n    free_minheap<\/span>(<\/span>heap)<\/span>;<\/span>\r\n    return<\/span> 0<\/span>;<\/span>\r\n}<\/span>\r\n<\/code><\/pre>\n
      \u51fa\u529b<\/p>\n
      Min Heap:<\/span>\r\n5<\/span> -><\/span> 50<\/span> -><\/span> 40<\/span> -><\/span> \r\nMin Heap:<\/span>\r\n5<\/span> -><\/span> 40<\/span> -><\/span> \r\n<\/code><\/pre>\n
      \n
      \u5b9f\u88c5\u306e\u6642\u9593\u8a08\u7b97\u91cf<\/h2>\n
      \u4e0a\u8a18\u306e\u624b\u7d9a\u304d\u306e\u6642\u9593\u306e\u8907\u96d1\u3055\u306f\u4ee5\u4e0b\u306e\u901a\u308a\u3067\u3059\u3002<\/p>\n
      \n
      \n\n\n\n\n\n\n\n\n\n\n
      <\/th>\n<\/th>\n<\/tr>\n<\/thead>\n
      Function<\/strong><\/td>\nTime Complexity<\/strong><\/td>\n<\/tr>\n
      get_min()<\/code><\/td>\nO(1)<\/strong><\/td>\n<\/tr>\n
      insert_minheap()<\/code><\/td>\nO(logN)<\/strong><\/td>\n<\/tr>\n
      delete_minimum()<\/code><\/td>\nSame as insert – O(logN)<\/strong><\/td>\n<\/tr>\n
      heapify()<\/code><\/td>\nO(logN)<\/strong><\/td>\n<\/tr>\n
      delete_element()<\/code><\/td>\nO(logN)<\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n
      \n
      \u30b3\u30fc\u30c9\u3092\u30c0\u30a6\u30f3\u30ed\u30fc\u30c9\u3057\u3066\u304f\u3060\u3055\u3044\u3002<\/h2>\n
      \u79c1\u304c\u30a2\u30c3\u30d7\u30ed\u30fc\u30c9\u3057\u305fGithub Gist\u304b\u3089\u5b8c\u5168\u306a\u30b3\u30fc\u30c9\u3092\u30c0\u30a6\u30f3\u30ed\u30fc\u30c9\u3059\u308b\u3053\u3068\u304c\u3067\u304d\u307e\u3059\u3002\u4f55\u304b\u8cea\u554f\u304c\u3042\u308a\u307e\u3057\u305f\u3089\u3001\u4ee5\u4e0b\u306e\u30b3\u30e1\u30f3\u30c8\u30bb\u30af\u30b7\u30e7\u30f3\u3067\u304a\u5c0b\u306d\u304f\u3060\u3055\u3044\uff01<\/p>\n
      \n
      \u7d50\u8ad6<\/h2>\n
      \u3053\u306e\u8a18\u4e8b\u3067\u306f\u3001Min Heap\u30d0\u30a4\u30ca\u30ea\u30c4\u30ea\u30fc\u3092\u3069\u306e\u3088\u3046\u306b\u8868\u73fe\u3067\u304d\u308b\u304b\u3092\u5b66\u3073\u3001C\u3067\u306e\u5b9f\u88c5\u3082\u898b\u3066\u3044\u304d\u307e\u3057\u305f\u3002<\/p>\n
      \u53c2\u8003\u6587\u732e<\/h2>\n
        \n
      • An illustration of Heaps, from Cormen<\/li>\n
      • Wikipedia article on Binary Heaps<\/li>\n<\/ul>\n
        \n","protected":false},"excerpt":{"rendered":"
        \u6700\u5c0f\u30d2\u30fc\u30d7\u4e8c\u5206\u6728\u3068\u306f\u3001\u6839\u30ce\u30fc\u30c9\u304c\u6728\u5185\u3067\u6700\u5c0f\u306e\u30ad\u30fc\u3092\u6301\u3064\u4e8c\u5206\u6728\u3067\u3042\u308b\u3002 \u4e0a\u8a18\u306e\u5b9a\u7fa9\u306f\u3001\u6728\u306e\u3059\u3079\u3066\u306e\u30b5\u30d6\u30c4\u30ea\u30fc\u306b\u5f53\u3066\u306f\u307e\u308a\u307e\u3059\u3002\u3053\u308c\u3092\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u7279\u6027\u3068\u547c\u3073\u307e\u3059\u3002 \u6700\u5f8c\u306e2\u3064\u306e\u5c64\u4ee5\u5916\u306e\u307b\u307c\u3059\u3079\u3066\u306e\u30ce\u30fc\u30c9\u306f\u30012\u3064\u306e\u5b50\u30ce\u30fc\u30c9\u3092\u6301 […]<\/p>\n","protected":false},"author":7,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[26,61],"class_list":["post-624","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-26","tag-61"],"yoast_head":"\n\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728 - Blog - Silicon Cloud<\/title>\n<meta name=\"description\" content=\"\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728\u3092\u5206\u304b\u308a\u3084\u3059\u304f\u89e3\u8aac\u3002\u5b9f\u8df5\u7684\u306a\u4f8b\u3068\u30b3\u30fc\u30c9\u3001\u6ce8\u610f\u70b9\u3092\u542b\u3081\u3066\u521d\u5fc3\u8005\u306b\u3082\u7406\u89e3\u3067\u304d\u308b\u3088\u3046\u8aac\u660e\u3057\u307e\u3059\u3002\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.silicloud.com\/ja\/blog\/\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728\/\" \/>\n<meta property=\"og:locale\" content=\"ja_JP\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728\" \/>\n<meta property=\"og:description\" content=\"\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728\u3092\u5206\u304b\u308a\u3084\u3059\u304f\u89e3\u8aac\u3002\u5b9f\u8df5\u7684\u306a\u4f8b\u3068\u30b3\u30fc\u30c9\u3001\u6ce8\u610f\u70b9\u3092\u542b\u3081\u3066\u521d\u5fc3\u8005\u306b\u3082\u7406\u89e3\u3067\u304d\u308b\u3088\u3046\u8aac\u660e\u3057\u307e\u3059\u3002\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.silicloud.com\/ja\/blog\/\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728\/\" \/>\n<meta property=\"og:site_name\" content=\"Blog - Silicon Cloud\" \/>\n<meta property=\"article:published_time\" content=\"2023-05-03T06:06:51+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2025-07-31T16:09:55+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/cdn.silicloud.com\/blog-img\/blog\/img\/656494d0daa94e2bdf7bf291\/4-0.png\" \/>\n<meta name=\"author\" content=\"\u7d50\u8863, \u6625\u82b1\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u57f7\u7b46\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"\u7d50\u8863, \u6625\u82b1\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u63a8\u5b9a\u8aad\u307f\u53d6\u308a\u6642\u9593\" \/>\n\t<meta name=\"twitter:data2\" content=\"29\u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.silicloud.com\/ja\/blog\/%e6%9c%80%e5%b0%8f%e3%83%92%e3%83%bc%e3%83%97%e3%81%ae%e4%ba%8c%e5%88%86%e6%9c%a8\/\",\"url\":\"https:\/\/www.silicloud.com\/ja\/blog\/%e6%9c%80%e5%b0%8f%e3%83%92%e3%83%bc%e3%83%97%e3%81%ae%e4%ba%8c%e5%88%86%e6%9c%a8\/\",\"name\":\"\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728 - Blog - Silicon Cloud\",\"isPartOf\":{\"@id\":\"https:\/\/www.silicloud.com\/ja\/blog\/#website\"},\"datePublished\":\"2023-05-03T06:06:51+00:00\",\"dateModified\":\"2025-07-31T16:09:55+00:00\",\"author\":{\"@id\":\"https:\/\/www.silicloud.com\/ja\/blog\/#\/schema\/person\/e52a686063ac76fd8cc6f539d41497ac\"},\"description\":\"\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728\u3092\u5206\u304b\u308a\u3084\u3059\u304f\u89e3\u8aac\u3002\u5b9f\u8df5\u7684\u306a\u4f8b\u3068\u30b3\u30fc\u30c9\u3001\u6ce8\u610f\u70b9\u3092\u542b\u3081\u3066\u521d\u5fc3\u8005\u306b\u3082\u7406\u89e3\u3067\u304d\u308b\u3088\u3046\u8aac\u660e\u3057\u307e\u3059\u3002\",\"breadcrumb\":{\"@id\":\"https:\/\/www.silicloud.com\/ja\/blog\/%e6%9c%80%e5%b0%8f%e3%83%92%e3%83%bc%e3%83%97%e3%81%ae%e4%ba%8c%e5%88%86%e6%9c%a8\/#breadcrumb\"},\"inLanguage\":\"ja\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.silicloud.com\/ja\/blog\/%e6%9c%80%e5%b0%8f%e3%83%92%e3%83%bc%e3%83%97%e3%81%ae%e4%ba%8c%e5%88%86%e6%9c%a8\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.silicloud.com\/ja\/blog\/%e6%9c%80%e5%b0%8f%e3%83%92%e3%83%bc%e3%83%97%e3%81%ae%e4%ba%8c%e5%88%86%e6%9c%a8\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/www.silicloud.com\/ja\/blog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.silicloud.com\/ja\/blog\/#website\",\"url\":\"https:\/\/www.silicloud.com\/ja\/blog\/\",\"name\":\"Blog - Silicon Cloud\",\"description\":\"\",\"inLanguage\":\"ja\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.silicloud.com\/ja\/blog\/#\/schema\/person\/e52a686063ac76fd8cc6f539d41497ac\",\"name\":\"\u7d50\u8863, \u6625\u82b1\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ja\",\"@id\":\"https:\/\/www.silicloud.com\/ja\/blog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/c74c6e2eb915a3c8e795b3934aa25a7333e0b38e7f1c7baf52785286ad51105e?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/c74c6e2eb915a3c8e795b3934aa25a7333e0b38e7f1c7baf52785286ad51105e?s=96&d=mm&r=g\",\"caption\":\"\u7d50\u8863, \u6625\u82b1\"},\"url\":\"https:\/\/www.silicloud.com\/ja\/blog\/author\/yuiharuka\/\"},{\"@type\":\"ImageObject\",\"inLanguage\":\"ja\",\"@id\":\"https:\/\/www.silicloud.com\/ja\/blog\/%e6%9c%80%e5%b0%8f%e3%83%92%e3%83%bc%e3%83%97%e3%81%ae%e4%ba%8c%e5%88%86%e6%9c%a8\/#local-main-organization-logo\",\"url\":\"\",\"contentUrl\":\"\",\"caption\":\"Blog - Silicon Cloud\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728 - Blog - Silicon Cloud","description":"\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728\u3092\u5206\u304b\u308a\u3084\u3059\u304f\u89e3\u8aac\u3002\u5b9f\u8df5\u7684\u306a\u4f8b\u3068\u30b3\u30fc\u30c9\u3001\u6ce8\u610f\u70b9\u3092\u542b\u3081\u3066\u521d\u5fc3\u8005\u306b\u3082\u7406\u89e3\u3067\u304d\u308b\u3088\u3046\u8aac\u660e\u3057\u307e\u3059\u3002","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.silicloud.com\/ja\/blog\/\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728\/","og_locale":"ja_JP","og_type":"article","og_title":"\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728","og_description":"\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728\u3092\u5206\u304b\u308a\u3084\u3059\u304f\u89e3\u8aac\u3002\u5b9f\u8df5\u7684\u306a\u4f8b\u3068\u30b3\u30fc\u30c9\u3001\u6ce8\u610f\u70b9\u3092\u542b\u3081\u3066\u521d\u5fc3\u8005\u306b\u3082\u7406\u89e3\u3067\u304d\u308b\u3088\u3046\u8aac\u660e\u3057\u307e\u3059\u3002","og_url":"https:\/\/www.silicloud.com\/ja\/blog\/\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728\/","og_site_name":"Blog - Silicon Cloud","article_published_time":"2023-05-03T06:06:51+00:00","article_modified_time":"2025-07-31T16:09:55+00:00","og_image":[{"url":"https:\/\/cdn.silicloud.com\/blog-img\/blog\/img\/656494d0daa94e2bdf7bf291\/4-0.png"}],"author":"\u7d50\u8863, \u6625\u82b1","twitter_card":"summary_large_image","twitter_misc":{"\u57f7\u7b46\u8005":"\u7d50\u8863, \u6625\u82b1","\u63a8\u5b9a\u8aad\u307f\u53d6\u308a\u6642\u9593":"29\u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.silicloud.com\/ja\/blog\/%e6%9c%80%e5%b0%8f%e3%83%92%e3%83%bc%e3%83%97%e3%81%ae%e4%ba%8c%e5%88%86%e6%9c%a8\/","url":"https:\/\/www.silicloud.com\/ja\/blog\/%e6%9c%80%e5%b0%8f%e3%83%92%e3%83%bc%e3%83%97%e3%81%ae%e4%ba%8c%e5%88%86%e6%9c%a8\/","name":"\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728 - Blog - Silicon Cloud","isPartOf":{"@id":"https:\/\/www.silicloud.com\/ja\/blog\/#website"},"datePublished":"2023-05-03T06:06:51+00:00","dateModified":"2025-07-31T16:09:55+00:00","author":{"@id":"https:\/\/www.silicloud.com\/ja\/blog\/#\/schema\/person\/e52a686063ac76fd8cc6f539d41497ac"},"description":"\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728\u3092\u5206\u304b\u308a\u3084\u3059\u304f\u89e3\u8aac\u3002\u5b9f\u8df5\u7684\u306a\u4f8b\u3068\u30b3\u30fc\u30c9\u3001\u6ce8\u610f\u70b9\u3092\u542b\u3081\u3066\u521d\u5fc3\u8005\u306b\u3082\u7406\u89e3\u3067\u304d\u308b\u3088\u3046\u8aac\u660e\u3057\u307e\u3059\u3002","breadcrumb":{"@id":"https:\/\/www.silicloud.com\/ja\/blog\/%e6%9c%80%e5%b0%8f%e3%83%92%e3%83%bc%e3%83%97%e3%81%ae%e4%ba%8c%e5%88%86%e6%9c%a8\/#breadcrumb"},"inLanguage":"ja","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.silicloud.com\/ja\/blog\/%e6%9c%80%e5%b0%8f%e3%83%92%e3%83%bc%e3%83%97%e3%81%ae%e4%ba%8c%e5%88%86%e6%9c%a8\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.silicloud.com\/ja\/blog\/%e6%9c%80%e5%b0%8f%e3%83%92%e3%83%bc%e3%83%97%e3%81%ae%e4%ba%8c%e5%88%86%e6%9c%a8\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/www.silicloud.com\/ja\/blog\/"},{"@type":"ListItem","position":2,"name":"\u6700\u5c0f\u30d2\u30fc\u30d7\u306e\u4e8c\u5206\u6728"}]},{"@type":"WebSite","@id":"https:\/\/www.silicloud.com\/ja\/blog\/#website","url":"https:\/\/www.silicloud.com\/ja\/blog\/","name":"Blog - Silicon Cloud","description":"","inLanguage":"ja"},{"@type":"Person","@id":"https:\/\/www.silicloud.com\/ja\/blog\/#\/schema\/person\/e52a686063ac76fd8cc6f539d41497ac","name":"\u7d50\u8863, \u6625\u82b1","image":{"@type":"ImageObject","inLanguage":"ja","@id":"https:\/\/www.silicloud.com\/ja\/blog\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/c74c6e2eb915a3c8e795b3934aa25a7333e0b38e7f1c7baf52785286ad51105e?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/c74c6e2eb915a3c8e795b3934aa25a7333e0b38e7f1c7baf52785286ad51105e?s=96&d=mm&r=g","caption":"\u7d50\u8863, \u6625\u82b1"},"url":"https:\/\/www.silicloud.com\/ja\/blog\/author\/yuiharuka\/"},{"@type":"ImageObject","inLanguage":"ja","@id":"https:\/\/www.silicloud.com\/ja\/blog\/%e6%9c%80%e5%b0%8f%e3%83%92%e3%83%bc%e3%83%97%e3%81%ae%e4%ba%8c%e5%88%86%e6%9c%a8\/#local-main-organization-logo","url":"","contentUrl":"","caption":"Blog - Silicon Cloud"}]}},"_links":{"self":[{"href":"https:\/\/www.silicloud.com\/ja\/blog\/wp-json\/wp\/v2\/posts\/624","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.silicloud.com\/ja\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.silicloud.com\/ja\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.silicloud.com\/ja\/blog\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/www.silicloud.com\/ja\/blog\/wp-json\/wp\/v2\/comments?post=624"}],"version-history":[{"count":1,"href":"https:\/\/www.silicloud.com\/ja\/blog\/wp-json\/wp\/v2\/posts\/624\/revisions"}],"predecessor-version":[{"id":42962,"href":"https:\/\/www.silicloud.com\/ja\/blog\/wp-json\/wp\/v2\/posts\/624\/revisions\/42962"}],"wp:attachment":[{"href":"https:\/\/www.silicloud.com\/ja\/blog\/wp-json\/wp\/v2\/media?parent=624"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.silicloud.com\/ja\/blog\/wp-json\/wp\/v2\/categories?post=624"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.silicloud.com\/ja\/blog\/wp-json\/wp\/v2\/tags?post=624"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}