{"id":853,"date":"2019-12-18T18:49:47","date_gmt":"2019-12-18T18:49:47","guid":{"rendered":"https:\/\/golangbyexamples.com\/?p=853"},"modified":"2022-04-04T23:14:58","modified_gmt":"2022-04-04T17:44:58","slug":"heap-in-golang","status":"publish","type":"post","link":"https:\/\/golangbyexamples.com\/heap-in-golang\/","title":{"rendered":"Heap in Golang"},"content":{"rendered":"\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_17 counter-hierarchy counter-decimal ez-toc-light-blue\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\">Table of Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" style=\"display: none;\"><i class=\"ez-toc-glyphicon ez-toc-icon-toggle\"><\/i><\/a><\/span><\/div>\n<nav><ul class=\"ez-toc-list ez-toc-list-level-1\"><li class=\"ez-toc-page-1 ez-toc-heading-level-1\"><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/golangbyexamples.com\/heap-in-golang\/#Introduction\" title=\"Introduction\">Introduction<\/a><\/li><li class=\"ez-toc-page-1 ez-toc-heading-level-1\"><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/golangbyexamples.com\/heap-in-golang\/#Implementation_of_MinHeap\" title=\"Implementation of MinHeap\">Implementation of MinHeap<\/a><\/li><\/ul><\/nav><\/div>\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Introduction\"><\/span><strong>Introduction<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<p class=\"has-medium-font-size\">A Heap is a complete binary tree. A complete binary tree is a binary tree in which all levels are full except the last level. Heap is of two types:<\/p>\n\n\n\n<ul class=\"has-medium-font-size wp-block-list\"><li><strong>MinHeap<\/strong>: A MinHeap is a complete binary tree in which the value of the parent node is lesser than or equal to the value of its left and right child.<\/li><\/ul>\n\n\n\n<p><\/p>\n\n\n\n<ul class=\"has-medium-font-size wp-block-list\"><li><strong>MaxHeap<\/strong> : A MaxHeap is a complete binary tree in which the value of the parent node is greater than or equal to the value of its left and right child.<\/li><\/ul>\n\n\n\n<p class=\"has-medium-font-size\">Below is a representation of a minheap. Notice that the parent node is always smaller than or equal to the child nodes<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"201\" height=\"191\" src=\"https:\/\/i2.wp.com\/golangbyexamples.com\/wp-content\/uploads\/2019\/12\/MinHeap-Example-1.png?resize=201%2C191&#038;ssl=1\" alt=\"\" class=\"wp-image-845\" data-recalc-dims=\"1\"\/><\/figure>\n\n\n\n<p class=\"has-medium-font-size\">Below is a representation of a maxheap.&nbsp; Notice that the parent node is always greater than or equal to the child nodes<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"201\" height=\"191\" src=\"https:\/\/i1.wp.com\/golangbyexamples.com\/wp-content\/uploads\/2019\/12\/Max-Heap.png?resize=201%2C191&#038;ssl=1\" alt=\"\" class=\"wp-image-849\" data-recalc-dims=\"1\"\/><\/figure>\n\n\n\n<p><\/p>\n\n\n\n<p class=\"has-medium-font-size\">Let&#8217;s look at the implementation of a minheap in GO in this post.<\/p>\n\n\n\n<p class=\"has-medium-font-size\">MaxHeap implementation you can find at link &#8211; <a href=\"https:\/\/golangbyexamples.com\/maxheap-in-golang\/\">https:\/\/golangbyexamples.com\/maxheap-in-golang\/<\/a><\/p>\n\n\n\n<p class=\"has-medium-font-size\">MinHeap full description can be found at link &#8211;<a href=\"https:\/\/golangbyexamples.com\/minheap-in-golang\/\">https:\/\/golangbyexamples.com\/minheap-in-golang\/<\/a><\/p>\n\n\n\n<p><\/p>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Implementation_of_MinHeap\"><\/span><strong>Implementation of MinHeap<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<pre class=\"wp-block-prismatic-blocks\"><code class=\"language-go\">package main\n\nimport \"fmt\"\n\ntype minheap struct {\n    heapArray []int\n    size      int\n    maxsize   int\n}\n\nfunc newMinHeap(maxsize int) *minheap {\n    minheap := &minheap{\n        heapArray: []int{},\n        size:      0,\n        maxsize:   maxsize,\n    }\n    return minheap\n}\n\nfunc (m *minheap) leaf(index int) bool {\n    if index >= (m.size\/2) && index <= m.size {\n        return true\n    }\n    return false\n}\n\nfunc (m *minheap) parent(index int) int {\n    return (index - 1) \/ 2\n}\n\nfunc (m *minheap) leftchild(index int) int {\n    return 2*index + 1\n}\n\nfunc (m *minheap) rightchild(index int) int {\n    return 2*index + 2\n}\n\nfunc (m *minheap) insert(item int) error {\n    if m.size >= m.maxsize {\n        return fmt.Errorf(\"Heal is ful\")\n    }\n    m.heapArray = append(m.heapArray, item)\n    m.size++\n    m.upHeapify(m.size - 1)\n    return nil\n}\n\nfunc (m *minheap) swap(first, second int) {\n    temp := m.heapArray[first]\n    m.heapArray[first] = m.heapArray[second]\n    m.heapArray[second] = temp\n}\n\nfunc (m *minheap) upHeapify(index int) {\n    for m.heapArray[index] < m.heapArray[m.parent(index)] {\n        m.swap(index, m.parent(index))\n    }\n}\n\nfunc (m *minheap) downHeapify(current int) {\n    if m.leaf(current) {\n        return\n    }\n    smallest := current\n    leftChildIndex := m.leftchild(current)\n    rightRightIndex := m.rightchild(current)\n    \/\/If current is smallest then return\n    if leftChildIndex < m.size &#038;&#038; m.heapArray[leftChildIndex] < m.heapArray[smallest] {\n        smallest = leftChildIndex\n    }\n    if rightRightIndex < m.size &#038;&#038; m.heapArray[rightRightIndex] < m.heapArray[smallest] {\n        smallest = rightRightIndex\n    }\n    if smallest != current {\n        m.swap(current, smallest)\n        m.downHeapify(smallest)\n    }\n    return\n}\nfunc (m *minheap) buildMinHeap() {\n    for index := ((m.size \/ 2) - 1); index >= 0; index-- {\n        m.downHeapify(index)\n    }\n}\n\nfunc (m *minheap) remove() int {\n    top := m.heapArray[0]\n    m.heapArray[0] = m.heapArray[m.size-1]\n    m.heapArray = m.heapArray[:(m.size)-1]\n    m.size--\n    m.downHeapify(0)\n    return top\n}\n\nfunc main() {\n    inputArray := []int{6, 5, 3, 7, 2, 8}\n    minHeap := newMinHeap(len(inputArray))\n    for i := 0; i < len(inputArray); i++ {\n        minHeap.insert(inputArray[i])\n    }\n    minHeap.buildMinHeap()\n    for i := 0; i < len(inputArray); i++ {\n        fmt.Println(minHeap.remove())\n    }\n    fmt.Scanln()\n}<\/code><\/pre>\n\n\n\n<p class=\"has-medium-font-size\"><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-prismatic-blocks\"><code class=\"language-go\">2\n3\n5\n6\n7\n8<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Table of Contents IntroductionImplementation of MinHeap Introduction A Heap is a complete binary tree. A complete binary tree is a binary tree in which all levels are full except the last level&#8230;.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":"","footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false},"categories":[1],"tags":[110,112,109,107],"class_list":["post-853","post","type-post","status-publish","format-standard","hentry","category-tech","tag-heap","tag-heap-in-go","tag-maxheap","tag-minheap"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v22.7 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Heap in Golang - Welcome To Golang By Example<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/golangbyexamples.com\/heap-in-golang\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Heap in Golang - Welcome To Golang By Example\" \/>\n<meta property=\"og:description\" content=\"Table of Contents IntroductionImplementation of MinHeap Introduction A Heap is a complete binary tree. A complete binary tree is a binary tree in which all levels are full except the last level....\" \/>\n<meta property=\"og:url\" content=\"https:\/\/golangbyexamples.com\/heap-in-golang\/\" \/>\n<meta property=\"og:site_name\" content=\"Welcome To Golang By Example\" \/>\n<meta property=\"article:published_time\" content=\"2019-12-18T18:49:47+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-04-04T17:44:58+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/golangbyexamples.com\/wp-content\/uploads\/2019\/12\/MinHeap-Example-1.png\" \/>\n<meta name=\"author\" content=\"admin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"admin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/golangbyexamples.com\/heap-in-golang\/\",\"url\":\"https:\/\/golangbyexamples.com\/heap-in-golang\/\",\"name\":\"Heap in Golang - Welcome To Golang By Example\",\"isPartOf\":{\"@id\":\"https:\/\/golangbyexamples.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/golangbyexamples.com\/heap-in-golang\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/golangbyexamples.com\/heap-in-golang\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/golangbyexamples.com\/wp-content\/uploads\/2019\/12\/MinHeap-Example-1.png\",\"datePublished\":\"2019-12-18T18:49:47+00:00\",\"dateModified\":\"2022-04-04T17:44:58+00:00\",\"author\":{\"@id\":\"https:\/\/golangbyexamples.com\/#\/schema\/person\/8833ea7638dafd763cb1db6c0ca4576f\"},\"breadcrumb\":{\"@id\":\"https:\/\/golangbyexamples.com\/heap-in-golang\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/golangbyexamples.com\/heap-in-golang\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/golangbyexamples.com\/heap-in-golang\/#primaryimage\",\"url\":\"https:\/\/golangbyexamples.com\/wp-content\/uploads\/2019\/12\/MinHeap-Example-1.png\",\"contentUrl\":\"https:\/\/golangbyexamples.com\/wp-content\/uploads\/2019\/12\/MinHeap-Example-1.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/golangbyexamples.com\/heap-in-golang\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/golangbyexamples.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Heap in Golang\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/golangbyexamples.com\/#website\",\"url\":\"https:\/\/golangbyexamples.com\/\",\"name\":\"Welcome To Golang By Example\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/golangbyexamples.com\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/golangbyexamples.com\/#\/schema\/person\/8833ea7638dafd763cb1db6c0ca4576f\",\"name\":\"admin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/golangbyexamples.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g\",\"caption\":\"admin\"},\"url\":\"https:\/\/golangbyexamples.com\/author\/admin\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Heap in Golang - Welcome To Golang By Example","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:\/\/golangbyexamples.com\/heap-in-golang\/","og_locale":"en_US","og_type":"article","og_title":"Heap in Golang - Welcome To Golang By Example","og_description":"Table of Contents IntroductionImplementation of MinHeap Introduction A Heap is a complete binary tree. A complete binary tree is a binary tree in which all levels are full except the last level....","og_url":"https:\/\/golangbyexamples.com\/heap-in-golang\/","og_site_name":"Welcome To Golang By Example","article_published_time":"2019-12-18T18:49:47+00:00","article_modified_time":"2022-04-04T17:44:58+00:00","og_image":[{"url":"https:\/\/golangbyexamples.com\/wp-content\/uploads\/2019\/12\/MinHeap-Example-1.png"}],"author":"admin","twitter_card":"summary_large_image","twitter_misc":{"Written by":"admin","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/golangbyexamples.com\/heap-in-golang\/","url":"https:\/\/golangbyexamples.com\/heap-in-golang\/","name":"Heap in Golang - Welcome To Golang By Example","isPartOf":{"@id":"https:\/\/golangbyexamples.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/golangbyexamples.com\/heap-in-golang\/#primaryimage"},"image":{"@id":"https:\/\/golangbyexamples.com\/heap-in-golang\/#primaryimage"},"thumbnailUrl":"https:\/\/golangbyexamples.com\/wp-content\/uploads\/2019\/12\/MinHeap-Example-1.png","datePublished":"2019-12-18T18:49:47+00:00","dateModified":"2022-04-04T17:44:58+00:00","author":{"@id":"https:\/\/golangbyexamples.com\/#\/schema\/person\/8833ea7638dafd763cb1db6c0ca4576f"},"breadcrumb":{"@id":"https:\/\/golangbyexamples.com\/heap-in-golang\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/golangbyexamples.com\/heap-in-golang\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/golangbyexamples.com\/heap-in-golang\/#primaryimage","url":"https:\/\/golangbyexamples.com\/wp-content\/uploads\/2019\/12\/MinHeap-Example-1.png","contentUrl":"https:\/\/golangbyexamples.com\/wp-content\/uploads\/2019\/12\/MinHeap-Example-1.png"},{"@type":"BreadcrumbList","@id":"https:\/\/golangbyexamples.com\/heap-in-golang\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/golangbyexamples.com\/"},{"@type":"ListItem","position":2,"name":"Heap in Golang"}]},{"@type":"WebSite","@id":"https:\/\/golangbyexamples.com\/#website","url":"https:\/\/golangbyexamples.com\/","name":"Welcome To Golang By Example","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/golangbyexamples.com\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/golangbyexamples.com\/#\/schema\/person\/8833ea7638dafd763cb1db6c0ca4576f","name":"admin","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/golangbyexamples.com\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","caption":"admin"},"url":"https:\/\/golangbyexamples.com\/author\/admin\/"}]}},"jetpack_featured_media_url":"","jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/paOs1b-dL","amp_validity":null,"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/posts\/853","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/comments?post=853"}],"version-history":[{"count":6,"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/posts\/853\/revisions"}],"predecessor-version":[{"id":6912,"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/posts\/853\/revisions\/6912"}],"wp:attachment":[{"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/media?parent=853"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/categories?post=853"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/tags?post=853"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}