{"id":576,"date":"2025-07-24T15:23:30","date_gmt":"2025-07-24T07:23:30","guid":{"rendered":"https:\/\/189505.xyz\/?p=576"},"modified":"2025-07-24T15:23:41","modified_gmt":"2025-07-24T07:23:41","slug":"finding-max-element-in-min-heap","status":"publish","type":"post","link":"https:\/\/189505.xyz\/?p=576","title":{"rendered":"Finding max element in min heap"},"content":{"rendered":"<p><a href=\"https:\/\/stackoverflow.com\/questions\/59858719\/finding-max-element-in-min-heap\">https:\/\/stackoverflow.com\/questions\/59858719\/finding-max-element-in-min-heap<\/a><\/p>\n<p>The following is an STL-like algorithm implementation for finding the maximum element in a min-heap provided by an iterator pair:<\/p>\n<pre><code>template&lt;typename RandomIt&gt;\nauto min_heap_max_element(RandomIt first, RandomIt last) {\n   auto n = last - first;\n\n   if (n &lt; 2)\n      return first;\n\n   auto first_leaf_it = first + (n - 2) \/ 2 + 1;\n   return std::max_element(first_leaf_it, last);\n}<\/code><\/pre>\n<p>To use it with your example:<\/p>\n<pre><code>auto max_it = min_heap_max_element(h.begin(), h.end());<\/code><\/pre>\n<p>How to find the first leaf node in a heap<br \/>\nThe last element of the heap \u2013 the one pointed by h.end() \u2013 is clearly a leaf node, and its parent is the last non-leaf node because if there were a non-leaf node following this one, the element that we assumed to be the last element of the heap wouldn't be the last element, which is a contradiction.<\/p>\n<p>Therefore, the first leaf node will be the element immediately following the last node's parent.<\/p>\n<p>You can easily find out where's the parent node of the last node: Given i the index of a heap element, its parent is at index (i - 1) \/ 2 . So, the index of the last non-leaf node is (h.size() - 2) \/ 2 and the index of the first leaf node is therefore (h.size() - 2) \/ 2 + 1.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/stackoverflow.com\/questions\/59858719\/finding-ma &#8230; <a title=\"Finding max element in min heap\" class=\"read-more\" href=\"https:\/\/189505.xyz\/?p=576\" aria-label=\"More on Finding max element in min heap\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/189505.xyz\/index.php?rest_route=\/wp\/v2\/posts\/576"}],"collection":[{"href":"https:\/\/189505.xyz\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/189505.xyz\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/189505.xyz\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/189505.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=576"}],"version-history":[{"count":2,"href":"https:\/\/189505.xyz\/index.php?rest_route=\/wp\/v2\/posts\/576\/revisions"}],"predecessor-version":[{"id":578,"href":"https:\/\/189505.xyz\/index.php?rest_route=\/wp\/v2\/posts\/576\/revisions\/578"}],"wp:attachment":[{"href":"https:\/\/189505.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=576"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/189505.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=576"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/189505.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=576"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}