push_heap() Function
The std::push_heap() function is used to sort the heap after the insertion of an element at the end of the heap. We use the push_back() function of std::vector class to insert a new element at the end of the vector then use the push_heap() function to place that element at its appropriate position.
Syntax:
std::push_heap(begin_interator, end_iterator);
Example:
C++
// C++ program to demonstrate the use of push_heap()// function#include <algorithm>#include <iostream>#include <vector>using namespace std;void print(vector<int>& vc){ for (auto i : vc) { cout << i << " "; } cout << endl;}int main(){ vector<int> vc{ 20, 30, 40, 10 }; make_heap(vc.begin(), vc.end()); cout << "Initial Heap: "; print(vc); vc.push_back(50); cout << "Heap just after push_back(): "; print(vc); push_heap(vc.begin(), vc.end()); cout << "Heap after push_heap(): "; print(vc); return 0;} |
Initial Heap: 40 30 20 10 Heap just after push_back(): 40 30 20 10 50 Heap after push_heap(): 50 40 20 10 30
Time Complexity: O(logN), where N is the number of elements.
Note: The push_heap() function should only be used after the insertion of a single element at the back. This function behavior is undefined if used for random insertion or to build a heap. For these cases, make_heap() function should be used.
Heap in C++ STL
The heap data structure can be implemented in a range using STL which provides faster max or min item retrieval, and faster insertion and deletion on sorted data and also works as a sub-routine for heapsort.