https://stackoverflow.com/questions/59858719/finding-max-element-in-min-heap
The following is an STL-like algorithm implementation for finding the maximum element in a min-heap provided by an iterator pair:
template<typename RandomIt>
auto min_heap_max_element(RandomIt first, RandomIt last) {
auto n = last - first;
if (n < 2)
return first;
auto first_leaf_it = first + (n - 2) / 2 + 1;
return std::max_element(first_leaf_it, last);
}To use it with your example:
auto max_it = min_heap_max_element(h.begin(), h.end());How to find the first leaf node in a heap
The last element of the heap – the one pointed by h.end() – 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.
Therefore, the first leaf node will be the element immediately following the last node's parent.
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.