priority_queue (min/max heap)
Building complexity: O(n) / priority_queue pq(iV.begin(),iV.end());
priority_queue s_pq;
for(auto i: iV) s_pq.push(i) //building time complexity O(n* log n)
pop : O(log n)
push : O(log n)
top : O(1)
default order: max heap( maximum item is on top) - descending order.
min heap (min item on top) - ascending order
priority_queue, std::greater> m_h(iV.begin(),iV.end());
Example code
vector<int> iV = { 3,5,8,3,6,1,20,4,8,1};
cout << "==========max heap=============" << endl;
// building time complexity O(n)
priority_queue<int> pq(iV.begin(), iV.end());// default order => max heap, descending order
pq.push(24);//O(log n) time complexity
while (!pq.empty()) {
cout << " " << pq.top() << endl; // --> acces the maximum item : O(1)
pq.pop();// O(log n) time complexity
}
//==========
cout << "==========min heap==============" << endl;
// min heap, O(n) building time complexity
priority_queue<int,vector<int>, std::greater<int>> m_h(iV.begin(),iV.end());
while (!m_h.empty()) {
cout << " " << m_h.top() << endl;
m_h.pop();
}
priority_queue<int, vector<int>, greater<int>> slow_bh; // O(1) building time
for (auto i : iV) slow_bh.push(i); // building time O (n* log n)
Custom data type
struct City {
int population;
string name;
City(int pop = 0, string s = "") {
population = pop;
name = s;
}
// for max heap
bool operator< (const City& c) const
{
return population < c.population || (population == c.population && name < c.name);
}
//for min heap
bool operator> (const City& c) const {
return population > c.population || (population == c.population && name > c.name);
}
//bool operator== (const City& c) const / for other methods
};
void test_priority_queue() {
vector<City> cV = { {100,"suwon"},{320,"incheon"},{40,"seoul"},{500,"kwangju"}};
// max heap
cout << "========== max heap =============" << endl;
priority_queue<City> pq(cV.begin(), cV.end());
while (!pq.empty()) {
cout << " " << pq.top().population << " " << pq.top().name << endl;
pq.pop();
}
cout << "========== min heap =============" << endl;
//min heap
priority_queue<City, vector<City>, std::greater<City>> mc_h(cV.begin(), cV.end());
while (!mc_h.empty()) {
cout << " " << mc_h.top().population << " " << mc_h.top().name << endl;
mc_h.pop();
}
}
Top comments (0)