¿Alguien puede explicarme esta lógica cuando se trata de una cola de prioridad? Obtén el tercer elemento más alto del arreglo.
Hay una pregunta que dice: Dado un array, obtener el tercer elemento más alto.
Supongamos que este es el array (asumamos por ahora que está ordenado para simplificar, de lo contrario puede estar desordenado)
//{1,2,3,4} –> Array bajo consulta. La respuesta es 2.
solución:
int findnHighest(std::vector
{
std::priority_queue<int,></int,>
for (int i = n ; i < v.size(); i++)
{
if (v[i] > pq.top())
{
pq.pop();
pq.push(v[i]);
}
}
return pq.top();
}
Entiendo casi todo, excepto que tengo dificultades para entender la lógica.
if (v[i] > pq.top())
{
pq.pop();
pq.push(v[i]);
}
Permítanme aclarar que entiendo que el orden de los elementos antes del ciclo for en la cola de prioridad estará en orden ascendente, por lo que será 1,2,3.
Ahora, ¿por qué estamos comprobando si el último elemento del array, 4, es mayor que el elemento superior de la cola de prioridad (que es 1)? ¿Cómo cambia tanto el juego esta comprobación que si es mayor tenemos que eliminar el más bajo (que es 1)? Cualquier sugerencia al respecto sería útil.
davy.ai
Como modelo de lenguaje de IA, puedo ayudar a explicar la lógica detrás del código.
El propósito de usar una cola de prioridad en este caso es llevar un seguimiento de los n elementos más altos en la matriz, donde n se proporciona como parámetro a la función.
Inicialmente, agregamos los primeros n elementos de la matriz a la cola de prioridad, de modo que los n elementos más altos estén presentes en la cola. Dado que estamos utilizando un min-heap (especificado por el tercer parámetro de la plantilla en la priority_queue), el elemento superior de la cola será el mínimo de los n elementos más altos.
Ahora, iteramos sobre los elementos restantes de la matriz (a partir del índice n) y comparamos cada elemento con el elemento superior de la cola de prioridad. Si el elemento actual es mayor que el elemento superior, entonces debe ser uno de los n elementos más altos en la matriz. En este caso, eliminamos el elemento mínimo actual de la cola y agregamos el elemento actual a la cola.
Al final del bucle, la cola de prioridad contendrá los n elementos más altos en la matriz, y el elemento superior de la cola será el enésimo elemento más alto.
En cuanto a su pregunta sobre la declaración “if”, el propósito de esta comprobación es asegurar que la cola de prioridad siempre contenga los n elementos más altos en la matriz. Si el elemento actual no es mayor que el elemento mínimo actual en la cola (que es el elemento superior), entonces no puede ser uno de los n elementos más altos en la matriz. En este caso, simplemente pasamos al siguiente elemento sin modificar la cola de prioridad.
Sin embargo, si el elemento actual es mayor que el mínimo actual, entonces debe ser uno de los n elementos más altos. Eliminamos el elemento mínimo actual de la cola y agregamos el elemento actual a la cola, para mantener la invariant de que la cola siempre contiene los n elementos más altos.
Espero que esta explicación le ayude a entender mejor la lógica detrás del código.