Priority_queue de STL es la implementación de Heap Data-structure . De forma predeterminada, es un montón máximo y podemos usarlo fácilmente para tipos de datos primitivos. Hay algunas aplicaciones importantes que se pueden encontrar aquí .
Prerrequisito: Conceptos básicos de Priority_queue
En este artículo, veremos cómo podemos usar la cola de prioridad para tipos de datos personalizados como clase o estructura.
supongamos que tenemos un nombre de estructura Persona que consiste en dos variables Edad y altura
y queremos almacenar eso en la cola de prioridad, entonces un método simple no funcionará aquí.
A continuación se muestra un ejemplo de la declaración de struct Person:
C++
struct Person{ int Age; float Height; }
Al definir la cola de prioridad como se muestra a continuación, nos dará un error ya que la cola de prioridad no sabe en qué orden (mínimo o máximo) necesitamos organizar los objetos.
C++
priority_queue<Person> pq;
Para rectificar el error anterior, utilizaremos la sobrecarga de operadores para definir la prioridad. Para que la cola de prioridad pueda decidir cómo almacenar el objeto de estructura.
A continuación se muestra la implementación de la cola de prioridad con la siguiente estructura:
C++
// program in c++ to use priority_queue with structure #include <iostream> #include <queue> using namespace std; #define ROW 5 #define COL 2 struct Person { int age; float height; // this will used to initialize the variables // of the structure Person(int age, float height) : age(age), height(height) { } }; // this is an structure which implements the // operator overloading struct CompareHeight { bool operator()(Person const& p1, Person const& p2) { // return "true" if "p1" is ordered // before "p2", for example: return p1.height < p2.height; } }; int main() { priority_queue<Person, vector<Person>, CompareHeight> Q; // When we use priority_queue with structure // then we need this kind of syntax where // CompareHeight is the function or comparison function float arr[ROW][COL] = { { 30, 5.5 }, { 25, 5 }, { 20, 6 }, { 33, 6.1 }, { 23, 5.6 } }; for (int i = 0; i < ROW; ++i) { Q.push(Person(arr[i][0], arr[i][1])); // insert an object in priority_queue by using // the Person structure constructor } while (!Q.empty()) { Person p = Q.top(); Q.pop(); cout << p.age << " " << p.height << "\n"; } return 0; }
Producción :
33 6.1 20 6 23 5.6 30 5.5 25 5
A continuación se muestra la implementación de priority_queue usando Class
C++
// program in c++ to use priority_queue with class #include <iostream> #include <queue> using namespace std; #define ROW 5 #define COL 2 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) { } }; // we are doing operator overloading through this bool operator<(const Person& p1, const Person& p2) { // this will return true when second person // has greater height. Suppose we have p1.height=5 // and p2.height=5.5 then the object which // have max height will be at the top(or // max priority) return p1.height < p2.height; } int main() { priority_queue<Person> Q; float arr[ROW][COL] = { { 30, 5.5 }, { 25, 5 }, { 20, 6 }, { 33, 6.1 }, { 23, 5.6 } }; for (int i = 0; i < ROW; ++i) { Q.push(Person(arr[i][0], arr[i][1])); // insert an object in priority_queue by using // the Person class constructor } while (!Q.empty()) { Person p = Q.top(); Q.pop(); cout << p.age << " " << p.height << "\n"; } return 0; }
Producción :
33 6.1 20 6 23 5.6 30 5.5 25 5
Publicación traducida automáticamente
Artículo escrito por PortgasDAce y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA