{"id":11410,"date":"2022-09-27T07:52:02","date_gmt":"2022-09-27T02:22:02","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/"},"modified":"2022-09-27T07:52:02","modified_gmt":"2022-09-27T02:22:02","slug":"solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/","title":{"rendered":"[Solved] How do i get the reference to the last (yet unfilled) element in a binary tree? [closed]"},"content":{"rendered":"<p> [ad_1]<br \/>\n<\/p>\n<div id=\"answer-50650728\" class=\"answer js-answer accepted-answer js-accepted-answer\" data-answerid=\"50650728\" data-parentid=\"50648149\" data-score=\"1\" data-position-on-page=\"1\" data-highest-scored=\"1\" data-question-has-accepted-highest-score=\"1\" itemprop=\"acceptedAnswer\" itemscope itemtype=\"https:\/\/schema.org\/Answer\">\n<div class=\"post-layout\">\n<div class=\"votecell post-layout--left\"><\/div>\n<div class=\"answercell post-layout--right\">\n<div class=\"s-prose js-post-body\" itemprop=\"text\">\n<p>In the discussion below, I demonstrate using a min-heap. A max-heap works the same way, except the root is the largest node rather than the smallest, and parents are larger than their children. Things work the same way, except that you reverse the sense of the comparisons.<\/p>\n<p>Insertion into a binary heap follows these rules:<\/p>\n<ol>\n<li>Add the new item to lowest, left-most position.<\/li>\n<li>If the item is smaller than its parent, swap it with its parent.<\/li>\n<li>Repeat step 2 until the item is not smaller than its parent.<\/li>\n<\/ol>\n<p>So let&#8217;s take the items <code>[7,4,3,1]<\/code>.<\/p>\n<p>You add the first one to the heap as the root, then you add the 4 as the root&#8217;s left child, giving.<\/p>\n<pre><code>    7\n  4\n<\/code><\/pre>\n<p>4 is smaller than 7, so swap it with its parent.<\/p>\n<pre><code>    4\n  7\n<\/code><\/pre>\n<p>The next value, 3, goes onto the heap in the first open position:<\/p>\n<pre><code>   4\n 7   3\n<\/code><\/pre>\n<p>3 is smaller than 4, so we swap with the parent, resulting in the heap:<\/p>\n<pre><code>   3\n 7   4\n<\/code><\/pre>\n<p>Finally, we add 1 to the lowest, left-most slot:<\/p>\n<pre><code>      3\n    7   4\n  1\n<\/code><\/pre>\n<p>1 is smaller than 7, so we swap the nodes:<\/p>\n<pre><code>      3\n    1   4\n  7\n<\/code><\/pre>\n<p>And 1 is smaller than 3, so we swap again:<\/p>\n<pre><code>      1\n    3   4\n  7\n<\/code><\/pre>\n<p>The resulting array representation of the binary heap is <code>[1,3,4,7]<\/code>.<\/p>\n<h2>Original answer<\/h2>\n<p>This answer was based on the question title asking how to turn an array into a binary heap.<\/p>\n<p>The method that transforms an array into a binary heap works by moving nodes down the heap into their proper positions. Let me illustrate with an example.<\/p>\n<p>Start with an array, <code>[7,4,3,6,1,2,5]<\/code>. Displayed as a binary heap, it would be:<\/p>\n<pre><code>             7\n           4   3\n          6 1 2 5\n<\/code><\/pre>\n<p>Obviously, that isn&#8217;t a binary min heap. What you do is start at the level directly above the leaf level, and start moving nodes down if required.<\/p>\n<p>So we start with 4. If it is larger than either of its children, then swap it with its smallest child. You end up with:<\/p>\n<pre><code>             7\n           1   3\n          6 4 2 5\n<\/code><\/pre>\n<p>Do the same thing with 3. It&#8217;s larger than 2, so swap it:<\/p>\n<pre><code>             7\n           1   2\n          6 4 3 5\n<\/code><\/pre>\n<p>And, finally, we have to move the 7. It&#8217;s larger than 1 and 2. We swap it with the smaller for the two, giving:<\/p>\n<pre><code>             1\n           7   2\n          6 4 3 5\n<\/code><\/pre>\n<p>7 is still larger than its children, so we swap it with the smaller of the two:<\/p>\n<pre><code>             1\n           4   2\n          6 7 3 5\n<\/code><\/pre>\n<p>And there&#8217;s your heap. The resulting array is <code>[1,4,2,6,7,3,5]<\/code>.<\/p>\n<\/p><\/div>\n<div class=\"mt24\"><\/div>\n<\/div>\n<p>            <span class=\"d-none\" itemprop=\"commentCount\">2<\/span> <\/p><\/div>\n<\/div>\n<p>[ad_2]<\/p>\n<p>solved How do i get the reference to the last (yet unfilled) element in a binary tree? [closed] <\/p>\n","protected":false},"excerpt":{"rendered":"<p>[ad_1] In the discussion below, I demonstrate using a min-heap. A max-heap works the same way, except the root is the largest node rather than the smallest, and parents are larger than their children. Things work the same way, except that you reverse the sense of the comparisons. Insertion into a binary heap follows these &#8230; <a title=\"[Solved] How do i get the reference to the last (yet unfilled) element in a binary tree? [closed]\" class=\"read-more\" href=\"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/\" aria-label=\"More on [Solved] How do i get the reference to the last (yet unfilled) element in a binary tree? [closed]\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[457,859],"class_list":["post-11410","post","type-post","status-publish","format-standard","hentry","category-solved","tag-algorithm","tag-data-structures"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.5 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>[Solved] How do i get the reference to the last (yet unfilled) element in a binary tree? [closed] - JassWeb<\/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:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] How do i get the reference to the last (yet unfilled) element in a binary tree? [closed] - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] In the discussion below, I demonstrate using a min-heap. A max-heap works the same way, except the root is the largest node rather than the smallest, and parents are larger than their children. Things work the same way, except that you reverse the sense of the comparisons. Insertion into a binary heap follows these ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-09-27T02:22:02+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\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\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] How do i get the reference to the last (yet unfilled) element in a binary tree? [closed]\",\"datePublished\":\"2022-09-27T02:22:02+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/\"},\"wordCount\":390,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"algorithm\",\"data-structures\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/\",\"name\":\"[Solved] How do i get the reference to the last (yet unfilled) element in a binary tree? [closed] - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2022-09-27T02:22:02+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] How do i get the reference to the last (yet unfilled) element in a binary tree? [closed]\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] How do i get the reference to the last (yet unfilled) element in a binary tree? [closed] - JassWeb","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:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] How do i get the reference to the last (yet unfilled) element in a binary tree? [closed] - JassWeb","og_description":"[ad_1] In the discussion below, I demonstrate using a min-heap. A max-heap works the same way, except the root is the largest node rather than the smallest, and parents are larger than their children. Things work the same way, except that you reverse the sense of the comparisons. Insertion into a binary heap follows these ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/","og_site_name":"JassWeb","article_published_time":"2022-09-27T02:22:02+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] How do i get the reference to the last (yet unfilled) element in a binary tree? [closed]","datePublished":"2022-09-27T02:22:02+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/"},"wordCount":390,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["algorithm","data-structures"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/","url":"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/","name":"[Solved] How do i get the reference to the last (yet unfilled) element in a binary tree? [closed] - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2022-09-27T02:22:02+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-how-do-i-get-the-reference-to-the-last-yet-unfilled-element-in-a-binary-tree-closed\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] How do i get the reference to the last (yet unfilled) element in a binary tree? [closed]"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/11410","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=11410"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/11410\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=11410"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=11410"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=11410"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}