{"id":996,"date":"2019-12-27T11:13:57","date_gmt":"2019-12-27T11:13:57","guid":{"rendered":"https:\/\/golangbyexamples.com\/?p=996"},"modified":"2019-12-27T11:16:26","modified_gmt":"2019-12-27T11:16:26","slug":"heapsort-in-golang","status":"publish","type":"post","link":"https:\/\/golangbyexamples.com\/heapsort-in-golang\/","title":{"rendered":"HeapSort 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\/heapsort-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\/heapsort-in-golang\/#Steps_for_HeapSort\" title=\"Steps for HeapSort:\">Steps for HeapSort:<\/a><\/li><li class=\"ez-toc-page-1 ez-toc-heading-level-1\"><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/golangbyexamples.com\/heapsort-in-golang\/#Full_Working_Code\" title=\"Full Working Code\">Full Working Code<\/a><\/li><li class=\"ez-toc-page-1 ez-toc-heading-level-1\"><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/golangbyexamples.com\/heapsort-in-golang\/#Time_Complexity\" title=\"Time Complexity\">Time Complexity<\/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\">HeapSort is a comparison-based sorting algorithm that uses the Heap Data Structure. Please refer to this link for more information about Heap &#8211;<a href=\"https:\/\/golangbyexamples.com\/heap-in-golang\/\">https:\/\/golangbyexamples.com\/heap-in-golang\/<\/a><\/p>\n\n\n\n<p class=\"has-medium-font-size\">We demonstrate the heapsort in this article using min-heap. The same can be achieved using max heap as well. <\/p>\n\n\n\n<ul class=\"has-medium-font-size wp-block-list\"><li>Left Child \u2013 2*i + 1<\/li><li>Right Child \u2013 2*i + 2<\/li><\/ul>\n\n\n\n<p class=\"has-medium-font-size\">Below is a representation of a minheap<\/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><\/p>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Steps_for_HeapSort\"><\/span><strong>Steps for HeapSort:<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<ul class=\"has-medium-font-size wp-block-list\"><li>Build minheap. After the minheap is built, the first element becomes the smallest<\/li><\/ul>\n\n\n\n<ul class=\"has-medium-font-size wp-block-list\"><li>Move the first element to the last in the array. Call heapify again with size-1. Repeat it for the size of the array<\/li><\/ul>\n\n\n\n<ul class=\"has-medium-font-size wp-block-list\"><li>The final array is sorted from largest to smallest<\/li><\/ul>\n\n\n\n<p><\/p>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Full_Working_Code\"><\/span><strong>Full Working Code<\/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    arr []int\n}\n\nfunc newMinHeap(arr []int) *minheap {\n    minheap := &minheap{\n        arr: arr,\n    }\n    return minheap\n}\n\nfunc (m *minheap) leftchildIndex(index int) int {\n    return 2*index + 1\n}\n\nfunc (m *minheap) rightchildIndex(index int) int {\n    return 2*index + 2\n}\n\nfunc (m *minheap) swap(first, second int) {\n    temp := m.arr[first]\n    m.arr[first] = m.arr[second]\n    m.arr[second] = temp\n}\n\nfunc (m *minheap) leaf(index int, size int) bool {\n    if index >= (size\/2) && index <= size {\n        return true\n    }\n    return false\n}\n\nfunc (m *minheap) downHeapify(current int, size int) {\n    if m.leaf(current, size) {\n        return\n    }\n    smallest := current\n    leftChildIndex := m.leftchildIndex(current)\n    rightRightIndex := m.rightchildIndex(current)\n    if leftChildIndex < size &#038;&#038; m.arr[leftChildIndex] < m.arr[smallest] {\n        smallest = leftChildIndex\n    }\n    if rightRightIndex < size &#038;&#038; m.arr[rightRightIndex] < m.arr[smallest] {\n        smallest = rightRightIndex\n    }\n    if smallest != current {\n        m.swap(current, smallest)\n        m.downHeapify(smallest, size)\n    }\n    return\n}\n\nfunc (m *minheap) buildMinHeap(size int) {\n    for index := ((size \/ 2) - 1); index >= 0; index-- {\n        m.downHeapify(index, size)\n    }\n}\n\nfunc (m *minheap) sort(size int) {\n    m.buildMinHeap(size)\n    for i := size - 1; i > 0; i-- {\n        \/\/ Move current root to end\n        m.swap(0, i)\n        m.downHeapify(0, i)\n    }\n}\n\nfunc (m *minheap) print() {\n    for _, val := range m.arr {\n        fmt.Println(val)\n    }\n}\n\nfunc main() {\n    inputArray := []int{6, 5, 3, 7, 2, 8, -1}\n    minHeap := newMinHeap(inputArray)\n    minHeap.sort(len(inputArray))\n    minHeap.print()\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\">8\n7\n6\n5\n3\n2\n-1<\/code><\/pre>\n\n\n\n<p><\/p>\n\n\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Time_Complexity\"><\/span><strong>Time Complexity<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<p class=\"has-medium-font-size\">Time Complexity of Heap Sort is \u00a0O(nLogn).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Table of Contents IntroductionSteps for HeapSort:Full Working CodeTime Complexity Introduction HeapSort is a comparison-based sorting algorithm that uses the Heap Data Structure. Please refer to this link for more information about Heap&#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":[3,118,119],"class_list":["post-996","post","type-post","status-publish","format-standard","hentry","category-tech","tag-go","tag-heapsort","tag-heapsort-in-go"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v22.7 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>HeapSort 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\/heapsort-in-golang\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"HeapSort in Golang - Welcome To Golang By Example\" \/>\n<meta property=\"og:description\" content=\"Table of Contents IntroductionSteps for HeapSort:Full Working CodeTime Complexity Introduction HeapSort is a comparison-based sorting algorithm that uses the Heap Data Structure. Please refer to this link for more information about Heap...\" \/>\n<meta property=\"og:url\" content=\"https:\/\/golangbyexamples.com\/heapsort-in-golang\/\" \/>\n<meta property=\"og:site_name\" content=\"Welcome To Golang By Example\" \/>\n<meta property=\"article:published_time\" content=\"2019-12-27T11:13:57+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2019-12-27T11:16:26+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=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/golangbyexamples.com\/heapsort-in-golang\/\",\"url\":\"https:\/\/golangbyexamples.com\/heapsort-in-golang\/\",\"name\":\"HeapSort in Golang - Welcome To Golang By Example\",\"isPartOf\":{\"@id\":\"https:\/\/golangbyexamples.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/golangbyexamples.com\/heapsort-in-golang\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/golangbyexamples.com\/heapsort-in-golang\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/golangbyexamples.com\/wp-content\/uploads\/2019\/12\/MinHeap-Example-1.png\",\"datePublished\":\"2019-12-27T11:13:57+00:00\",\"dateModified\":\"2019-12-27T11:16:26+00:00\",\"author\":{\"@id\":\"https:\/\/golangbyexamples.com\/#\/schema\/person\/8833ea7638dafd763cb1db6c0ca4576f\"},\"breadcrumb\":{\"@id\":\"https:\/\/golangbyexamples.com\/heapsort-in-golang\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/golangbyexamples.com\/heapsort-in-golang\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/golangbyexamples.com\/heapsort-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\/heapsort-in-golang\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/golangbyexamples.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"HeapSort 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":"HeapSort 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\/heapsort-in-golang\/","og_locale":"en_US","og_type":"article","og_title":"HeapSort in Golang - Welcome To Golang By Example","og_description":"Table of Contents IntroductionSteps for HeapSort:Full Working CodeTime Complexity Introduction HeapSort is a comparison-based sorting algorithm that uses the Heap Data Structure. Please refer to this link for more information about Heap...","og_url":"https:\/\/golangbyexamples.com\/heapsort-in-golang\/","og_site_name":"Welcome To Golang By Example","article_published_time":"2019-12-27T11:13:57+00:00","article_modified_time":"2019-12-27T11:16:26+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":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/golangbyexamples.com\/heapsort-in-golang\/","url":"https:\/\/golangbyexamples.com\/heapsort-in-golang\/","name":"HeapSort in Golang - Welcome To Golang By Example","isPartOf":{"@id":"https:\/\/golangbyexamples.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/golangbyexamples.com\/heapsort-in-golang\/#primaryimage"},"image":{"@id":"https:\/\/golangbyexamples.com\/heapsort-in-golang\/#primaryimage"},"thumbnailUrl":"https:\/\/golangbyexamples.com\/wp-content\/uploads\/2019\/12\/MinHeap-Example-1.png","datePublished":"2019-12-27T11:13:57+00:00","dateModified":"2019-12-27T11:16:26+00:00","author":{"@id":"https:\/\/golangbyexamples.com\/#\/schema\/person\/8833ea7638dafd763cb1db6c0ca4576f"},"breadcrumb":{"@id":"https:\/\/golangbyexamples.com\/heapsort-in-golang\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/golangbyexamples.com\/heapsort-in-golang\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/golangbyexamples.com\/heapsort-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\/heapsort-in-golang\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/golangbyexamples.com\/"},{"@type":"ListItem","position":2,"name":"HeapSort 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-g4","amp_validity":null,"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/posts\/996","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=996"}],"version-history":[{"count":4,"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/posts\/996\/revisions"}],"predecessor-version":[{"id":1000,"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/posts\/996\/revisions\/1000"}],"wp:attachment":[{"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/media?parent=996"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/categories?post=996"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/golangbyexamples.com\/wp-json\/wp\/v2\/tags?post=996"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}