Created
May 20, 2022 07:25
-
-
Save lag945/d687a93c23e5cd7c231f5d338806336d to your computer and use it in GitHub Desktop.
STL Priority Queue for Structure or Class
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <queue> | |
//source https://www.geeksforgeeks.org/stl-priority-queue-for-structure-or-class/ | |
class Person { | |
public: | |
int age; | |
float height; | |
// this is used to initialize the variables of the class | |
Person(int age, float height) | |
: age(age), height(height) | |
{ | |
} | |
struct Min { | |
bool operator()(Person const& p1, Person const& p2) | |
{ | |
return p1.height > p2.height; | |
} | |
}; | |
struct Max { | |
bool operator()(Person const& p1, Person const& p2) | |
{ | |
return p1.height < p2.height; | |
} | |
}; | |
}; | |
int main() | |
{ | |
std::priority_queue<Person,std::vector<Person>,Person::Min> pq; | |
pq.push(Person(30, 176)); | |
pq.push(Person(20, 180)); | |
pq.push(Person(25, 178)); | |
auto& r = pq.top(); | |
std::cout << r.age << ":" << r.height << std::endl; | |
pq.pop(); | |
auto& r2 = pq.top(); | |
std::cout << r.age << ":" << r.height << std::endl; | |
pq.pop(); | |
auto& r3 = pq.top(); | |
std::cout << r.age << ":" << r.height << std::endl; | |
} |
Author
lag945
commented
May 20, 2022
•
Method | vector v1 | vector v2 | vector v3 | priority_queue | (ordered_)map |
---|---|---|---|---|---|
enqueue | binarySeartch+push_back=O(n) | push_back=O(1) | push_back=O(1) | O(log(n)) | insert=O(log(n)) |
dequeue | []+pop_back=O(1) | Sort+[]+pop_back=O(n log(n)) | iterate+erase=O(n) | O(log(n)) | erase(begin)=O(1) |
iterate | O(n) | O(n) | O(n) | O(n log(n)) | O(n) |
order iterate | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
remove method comparison
Method | CList | priority_queue | (ordered_)map |
---|---|---|---|
push | O(n) | O(log(n)) | insert=O(log(n)) |
pop | O(1) | O(log(n)) | erase(begin)=O(1) |
remove | O(n) | O(nlog(n) | find+erase=O(log(n)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment