C++ std::pop_heap with std::vector














































C++ std::pop_heap with std::vector



 This article is about the pop_heap() algorithm function with std::vector container. It is
 an STL algorithm in <algorithm> header file. After the first element is popped out of the
 heap it is placed in the last index. The pop_heap function does this, along with that
 rearranges the elements of the heap so that it still preserves the property of the heap.
 After this the part which is considered as a heap is shortened by 1. It changes from
 [first, last) to [first, last-1). After a heap is created the pop_heap function can be used
 to remove elements from the heap.
 
pop_heap() can take two forms:
(1) template <class RandomAccessIterator> void pop_heap (RandomAccessIterator first, RandomAccessIterator last); (2) template <class RandomAccessIterator, class Compare> void pop_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
In 1st is the default case and the 2nd one is the custom case. It uses comp function for
 the comparison. comp is a binary function which accepts 2 values and returns a bool value
 which indicates whether the first element is less than the second or not. If the heap is not
 empty or one element heap then this comp function is used.

Here the first definition is discussed.

 Program:
 Marks of few students are stored in a database. Remove the top n marks from the list.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
int i, n, m;
// marks of the students
vector<int> marks{98,86,45,78,63,85,56,69,34,87,67,90,99};

make_heap(marks.begin(), marks.end());

cout<<"Enter the number of top students to be removed: ";
cin>>n;

for(i=0;i<n;i++)
{
pop_heap(marks.begin(), marks.end());
marks.pop_back();
}

cout<<"Highest Marks: "<<marks.front()<<endl;
return 0;
}

Comments