Finding extreme values with STL algorimths

Recently  while doing a code review I was surprised to notice that the developer rolled out his own method to find the maximal  element in a  container.  With the STL offering several ways to do just that,  it’s difficult to imagine why  reinventing this particular  wheel justify the effort.

in this post,  I’ll  review 4 ways if finding the maximum and minimal elements in a container.  Choosing the algorithm best suited for your situation depends on the constraints  and the problem you are trying to solve.

max_element / min_element

this is the most trivial algorithm.  It  will scan the entire container searching for the min/max element,  returning an iterator  pointing to it.
If your  compiler supports C++ 11  and up, you can use the minmax_element  method to find  both minimal and maximal elements in the same run.

	vector<int> numbers = {3,7,8,93,11,4,-1,0};
	printVector(numbers);
	auto max = max_element(begin(numbers), end(numbers));
	printMax(*max);

3,7,8,93,11,4,-1,0
max val: 93

Cost:   O(n) as the entire  n elements of the container must be scanned.

Priority Queue

A priority queue is an ordered sequence starting with a zero sized container, each  new element is  inserted into a position that maintains the order of the queue:

	cout << "\n Priority queue - max value\n" << endl;
		vector<int> numbers = { 3,7,8,93,11,4,-1,0 };
		priority_queue<int> max_queue;
		cout << "<empty>" << endl;
		for ( auto n : { 7, 3,8,-1,0 } )
		{
			cout << " insert " << n << endl;
			max_queue.push(n);
			print_queue(max_queue);
		}
		auto  max1 = max_queue.top();
		printMax(max1);
		cout << "removing max value" << endl;
		max_queue.pop();
		print_queue(max_queue);

Priority queue – max value
<empty>
insert 7
7
insert 3
7,3
insert 8
8,7,3
insert -1
8,7,3,-1
insert 0
8,7,3,0,-1
8,7,3,0,-1
max val: 8
removing max value
7,3,0,-1

It worth pointing out that a queue structure is built over another container overriding  push and pop operations of  the original container ensure the priority structure maintains its order after an element is inserted or removed from the queue.

By default the order of the elements is determined by std::less :  suppose there are two elements x,y than – x will be placed before y if x < y  (max queue).
Your can create a min queue by using std::greater instead of std::less :

			cout << "Minimum max_queue" << endl;
			priority_queue<int, vector<int>, greater<int> > min_queue;
			cout << "<empty>" << endl;
			for (auto n : { 7, 3,8,-1,0 })
			{
				cout << " insert " << n << endl;
				min_queue.push(n);
				print_queue(min_queue);
	
			cout << "Minimum max_queue" << endl;
			priority_queue<int, vector<int>, greater<int> > min_queue;
			cout << "<empty>" << endl;
			for (auto n : { 7, 3,8,-1,0 })
			{
				cout << " insert " << n << endl;
				min_queue.push(n);
				print_queue(min_queue);
	
Partial Sort

as its suggests –  partial sort will only sort part of the container so that the first m elements  are sorted.  It’s a good strategy to employ if you need a set of the first extreme values.

	cout << "\n Partial Sort \n" << endl;
	vector<int> numbers = { 13,7,8,93,11,4,-1,0 };
	printVector(numbers);
	cout << "Sorting 3 frist elements" << endl;
	partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end());
	printVector(numbers);

13,7,8,93,11,4,-1,0
Sorting first 3 elements
-1,0,4,93,13,11,8,77

As you can see the first 3 values in the list are sorted in descending order. Values past the 3’d elements has no predictable order.

Accessing the max element can be done by simply iterating over the first m elements of the sorted container or by using partial_sort_copy that will sort the container and copies the result to a different container

Cost: sorting the first m elements out of a – n size container will cost O(n lg (m))  which is nearly linear for small m in the. The cost of Inserting elements is  container dependent (e.g. it will cost O(1) for a list).

Heap

You can use an existing container is a heap by calling make_heap. The containers elements order will change so that the extreme value will be on  top of the heap.


		cout << "\n Heap \n" << endl;
		vector<int> numbers = { 3,7,8,93,11,4,-1,0 };
		printVector(numbers);
		make_heap(numbers.begin(), numbers.end());
		cout << "\nafter make_heap: " << endl;
		printVector(numbers);

Getting the extreme element and removing it are three distinct operations:

  1.  Getting the max/min element is done with the containers front method.
  2.  calling the heap pop_heap to move the current extreme element to the end of the container.
  3. Calling the container’s pop_back to remove the value from the container.
int max1 = numbers.front();
		cout << "\nmax value : " << max1 << endl;
		pop_heap(numbers.begin(), numbers.end());  
		cout << "\nafter pop_heap, max value is now last:" << endl;
		printVector(numbers);
		cout << "\nremove  max  element " << endl;
		numbers.pop_back();    // vector / list no re-allocation triggered
		printVector(numbers);

Note:  I almost included the heap method as an honorable mention, while is  possible to use a heap. It’s very easy to mess it up by calling the underlying container methods. Honestly, I find it difficult to imagine a scenario where a bare heap will be useful  for this purpose, but  If you do need to use this method, you’ll probably want to hide the container in another class, exposing specialized insert/retrieve method that will make sure the heap structure is maintained.

Cost: the initial cost of creating the heap is O(3n), once the heap is created it will cost O(2lg n) to retrieve the minimum/maximum value and O(lg n) to push a new value into the container with push_heap.

Conclusion

When it comes to finding a max element, the STL offers something to everyone. There have to be convincing arguments to justify implementing your own algorithm instead of using the fully field tested and super optimized implementation of the standard library.

I am sure there are more ways to find the min/max values,   leave a comment if you have other ways of extracting the min/max using the standard library. 

Leave a Reply

Your email address will not be published. Required fields are marked *