Skip to content

Instantly share code, notes, and snippets.

@lag945
Created May 20, 2022 07:25
Show Gist options
  • Save lag945/d687a93c23e5cd7c231f5d338806336d to your computer and use it in GitHub Desktop.
Save lag945/d687a93c23e5cd7c231f5d338806336d to your computer and use it in GitHub Desktop.
STL Priority Queue for Structure or Class
#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;
}
@lag945
Copy link
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)

@lag945
Copy link
Author

lag945 commented Jun 22, 2022

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