CODEWITHSUNDEEP
c++algorithmoptimizationstlheap
Andreas
Andreas

Reputation: 33

Finding max element in min heap

I have a min heap:

std::vector<int> h;
...
std::make_heap(h.begin(), h.end(), std::greater<int>());

The min heap operations std::push_heap and std::pop_heap are what I need for most cases but under very rare circumstances I need to find the maximum element in the min heap. I can do it with std::max_element:

std::max_element(h.begin(), h.end());

However, this must scan all the heap elements.

Does the standard library offer a more efficient algorithm for finding the max element in a min heap?

Upvotes: 2

Views: 943

Answers (2)

jfMR
jfMR

Reputation: 24788

TL;DR In a min-heap, the maximum element is in a leaf nodeX. Therefore, you can restrict your search to roughly half of the elements of the heap, i.e., by limiting your search of the maximum element to the leaf nodes only:

auto max_it = std::max_element(first_leaf_it, h.end());

Note that this still takes linear time, but the constant factor is lower, roughly a half, than scanning through all the elements.

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.

X Let's assume that the maximum element in a min-heap is located in a non-leaf node instead. This would imply that it has, at least, a child node. Due to the min-heap property, this child node has to be greater than or equal to its parent. If the child is greater than its parent – which is the maximum element – the child node is greater than the maximum. This is not possible because we have a contradiction. So, all its children nodes have to be maximums as well, and so on for these children as well. So, eventually, there is a maximum located in one of the leaf nodes if the maximum value is repeated in the heap or the only maximum value must correspond to a leaf node.

Upvotes: 2

trincot
trincot

Reputation: 351308

If you really need better (i.e. sub-linear) time complexity, then consider using a Min-max heap. Any node in this tree obeys the following property:

When a value is on an even level, then it is the greatest among its descendants.
When a value is on an odd level, then it is the least among its descendants.

The root thus has the smallest value, and one of its two children has the greatest value.

The time complexities of the insert/extract operations are the same as for a min heap.

Check Is there a C++ MinMax Heap implementation?

Upvotes: 2

Related Questions