La cola de prioridad es una estructura de datos en la que los datos se almacenan en función de su prioridad. En una cola de prioridad indexada , los datos se almacenan como una cola de prioridad estándar y, junto con esto, el valor de un dato se puede actualizar usando su clave. Se llama » indexado » porque se puede usar un mapa hash para almacenar el índice en un contenedor usando la clave de entrada del par clave-valor como la clave del mapa hash. Esto es útil al implementar el Algoritmo de Dijkstra usando min-heap . También se puede usar en cualquier otro programa en el que se requiera poner pares clave-valor en la cola de prioridad y, junto con él, debe actualizar el valor de las claves con la función push o pop.
Operaciones en una Cola de Prioridad Indexada: Las operaciones que se pueden realizar en una Cola de Prioridad Indexada son:
- push : agregar un par clave-valor en la cola de prioridad indexada de acuerdo con su prioridad. Implementación: para hacer esto, agregue el par clave-valor en el contenedor y luego acumule según el valor en el par clave-valor. Complejidad de tiempo: O( log(n) )
- pop: eliminando el par clave-valor de mayor prioridad. Implementación: Retire la parte superior del montón y luego apile el resto del contenedor. Complejidad de tiempo: O( log(n))
- top : Devuelve el par clave-valor al usuario. Implementación: devuelve el par clave-valor que se encuentra en la parte superior del montón. Complejidad de tiempo: O(1)
- size : devuelve el número de pares clave-valor en la cola de prioridad indexada. Implementación: realice un seguimiento del número de elementos en cola en la clase y devuelva la variable cuando se llame a la función size(). Complejidad de tiempo: O(1)
- vacío : devuelve verdadero cuando la cola de prioridad indexada está vacía. Implementación: devuelve verdadero cuando la variable número de elementos es igual a cero. Complejidad de tiempo: O(1)
- changeAtKey : esta función diferencia la cola de prioridad indexada de la cola de prioridad estándar. Toma dos argumentos del usuario, el primero es la clave y el segundo es el valor nuevo, y actualiza el valor antiguo asociado con la clave al nuevo valor proporcionado y actualiza su posición de acuerdo con la prioridad del nuevo valor. Implementación: mantenga un mapa hash cuya clave sea clave en el par clave-valor y apunte al índice de la clave en el contenedor. Cuando se llama a la función, actualice el valor en el índice requerido y posicione el elemento actual de acuerdo con su prioridad y finalmente cambie el valor del índice en el mapa hash. Complejidad de tiempo: O( log(n) )
Implementación de cola de prioridad indexada:
La cola de prioridad indexada se implementa mediante el almacenamiento dinámico binario ; sin embargo, también se puede implementar mediante el almacenamiento dinámico de Fibonacci o el almacenamiento dinámico K-ary.
Hay cuatro parámetros que se deben pasar al definir una instancia de Cola de prioridad indexada (dos obligatorios y dos opcionales) que son:
- Tipo de datos de la clave : este es el primer parámetro en la definición y debe ser un tipo de datos que se pueda codificar en el mapa hash o que el usuario pase su propia función hash como cuarto parámetro. Para obtener más información sobre la función hash en el mapa hash, consulte este artículo.
- Tipo de datos de valor : este es el segundo parámetro en la definición.
- Comparador : este es el tercer parámetro opcional. De forma predeterminada, la Cola de prioridad indexada se implementará utilizando el montón máximo para cambiar que el usuario tenga que pasar un comparador diferente con su parámetro (es decir, el parámetro del comparador) como el tipo de datos de valor.
- Función hash : este es el cuarto parámetro y solo se requiere cuando el usuario pasa un tipo de datos personalizado (como una clase) para la clave, luego el usuario tiene que pasar su propia función hash.
A continuación se muestra la implementación de la cola de prioridad indexada:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2,
class Comparator = less<T2>,
class Hash = hash<T1> >
class indexed_priority_queue {
// Storing indices of values using key
unordered_map<T1, long long int, Hash> m;
// Container
vector<pair<T1, T2> > v;
// Size
long long numberOfElement;
// Creating a instance of Comparator class
Comparator comp;
// Max Capacity
long long capacity = LLONG_MAX;
// Obtaining the index value from hash map
long long int getValueIndex(T1 key)
{
if (m[key] == 0) {
cout << "No Such Key Exist";
return -1;
}
return v[m[key] - 1];
}
// heapify the container
void heapify(vector<pair<T1, T2> >& v,
long long int heap_size,
long long index)
{
long long leftChild = 2 * index + 1,
rightChild = 2 * index + 2,
suitableNode = index;
if (leftChild < heap_size
&& comp(v[suitableNode].second,
v[leftChild].second)) {
suitableNode = leftChild;
}
if (rightChild < heap_size
&& comp(v[suitableNode].second,
v[rightChild].second)) {
suitableNode = rightChild;
}
if (suitableNode != index) {
// swap the value
pair<T1, T2> temp = v[index];
v[index] = v[suitableNode];
v[suitableNode] = temp;
// updating the map
m[v[index].first] = index + 1;
m[v[suitableNode].first]
= suitableNode + 1;
// heapify other affected nodes
heapify(v, numberOfElement,
suitableNode);
}
}
public:
indexed_priority_queue()
{
numberOfElement = 0;
m.clear();
v.clear();
}
void push(T1 key, T2 value)
{
if (numberOfElement == capacity) {
cout << "Overflow";
return;
}
if (m[key] != 0) {
cout << "Element Already Exists";
return;
}
// Adding element
v.push_back(make_pair(key, value));
numberOfElement++;
m[key] = numberOfElement;
long long index = numberOfElement - 1;
// Comparing to parent node
while (index != 0
&& comp(v[(index - 1) / 2].second,
v[index].second)) {
// swap the value
pair<T1, T2> temp = v[index];
v[index] = v[(index - 1) / 2];
v[(index - 1) / 2] = temp;
// updating the map
m[v[index].first] = index + 1;
m[v[(index - 1) / 2].first]
= (index - 1) / 2 + 1;
// updating index in map
index = (index - 1) / 2;
}
}
void pop()
{
if (numberOfElement == 0) {
cout << "UnderFlow";
return;
}
// Removing element
v.erase(v.begin());
numberOfElement--;
heapify(v, numberOfElement, 0);
}
pair<T1, T2> top() { return v[0]; }
long long int size() { return numberOfElement; }
bool empty() { return numberOfElement == 0; }
void changeAtKey(T1 key, T2 value)
{
if (m[key] == 0) {
cout << "No Such Key Exist";
return;
}
long long index = m[key] - 1;
v[index].second = value;
// Comparing to child nodes
heapify(v, numberOfElement, index);
// Comparing to Parent Node
while (index != 0
&& comp(v[(index - 1) / 2].second,
v[index].second)) {
// swap the value
pair<T1, T2> temp = v[index];
v[index] = v[(index - 1) / 2];
v[(index - 1) / 2] = temp;
// updating the map
m[v[index].first] = index + 1;
m[v[(index - 1) / 2].first]
= (index - 1) / 2 + 1;
// updating index in map
index = (index - 1) / 2;
}
}
};
void display(indexed_priority_queue<int, int> IPQ)
{
indexed_priority_queue<int, int> temp = IPQ;
while (!IPQ.empty()) {
pair<int, int> tmp;
tmp = IPQ.top();
IPQ.pop();
cout << "( " << tmp.first << ", "
<< tmp.second << " ) ";
}
cout << '\n';
}
// Driver Code
int main()
{
// First parameter is key datatype
// and it should be hashable
// Second parameter is value datatype comparator
// function (by default it implements maxheap)
indexed_priority_queue<int, int> IPQ;
// Check if empty
cout << "Checking if initially the IPQ is empty\n";
if (IPQ.empty())
cout << "IPQ is empty\n";
else
cout << "IPQ is not empty\n";
// Insertion
cout << "Inserting pairs (2, 1), (3, 7), "
<< " (1, 0) and (4, 5)\n";
IPQ.push(2, 1);
IPQ.push(3, 7);
IPQ.push(1, 0);
IPQ.push(4, 5);
// Printing the contents of IPQ
cout << "IPQ: ";
display(IPQ);
cout << '\n';
// Checking size and top after pushing
cout << "Size: " << IPQ.size() << endl;
cout << "Top: " << IPQ.top().first
<< ", " << IPQ.top().second
<< "\n\n";
// Replace operation
cout << "Changing value associated with"
<< " key 3 to 2 and 1 to 9\n";
IPQ.changeAtKey(3, 2);
IPQ.changeAtKey(1, 9);
// Checking size and top after replacement
cout << "Size: " << IPQ.size() << endl;
cout << "Top: " << IPQ.top().first
<< ", " << IPQ.top().second
<< "\n\n";
// Deleting 2 elements from IPQ
cout << "Poping an element from IPQ: ";
IPQ.pop();
cout << "\nPoping an element from IPQ: ";
IPQ.pop();
cout << '\n\n';
// Printing the contents of IPQ after deletion
cout << "IPQ: ";
display(IPQ);
cout << '\n';
// Checking size and top after pushing
cout << "Size: " << IPQ.size() << endl;
cout << "Top: " << IPQ.top().first
<< ", " << IPQ.top().second
<< "\n\n";
return 0;
}
Salida: Comprobando si inicialmente el IPQ está vacío IPQ está vacío Inserción de pares (2, 1), (3, 7), (1, 0) y (4, 5) IPQ: ( 3, 7 ) ( 4, 5 ) ( 2, 1 ) ( 1, 0 ) Tamaño: 4 Superior: 3, 7 Cambio del valor asociado con la tecla 3 a 2 y 1 a 9 Tamaño: 4 Superior: 1, 9 Extraer un elemento de IPQ: Extraer un elemento de IPQ: IPQ : ( 3, 2 ) ( 2, 1 ) Tamaño: 2 Parte superior: 3, 2
Publicación traducida automáticamente
Artículo escrito por tarun2kishore y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA