STL, queue

En C++, la STL nos proporciona una clase cola. La forma de declararla es la siguiente

#include < queue > // aquí esta implementada la clase
queue< int > q; // queue < tipo_de_dato > nombre_de_la_cola;

Las funciones para trabajar con ella son las siguientes

q.empty() // esta vacia la cola? (empty)
q.push(x); // inserta x al final (push)
q.pop(); // elimina el elemento que esta al frente (pop)
q.front(); // regresa el elemento que esta al frente (front)

Ejemplo:

#include <cstdio>
#include <queue>

using namespace std;

main()
{
// queue <tipo, en este caso, entero> nombre_de_la_cola;
queue <int> q;

// insertamos tres elementos
q.push(1); q.push(2); q.push(3);

// el elemento insertado primero debe salir primero (FIFO): 1, 2, 3
while(!q.empty()) {
printf("%d ", q.front());
q.pop();
}
printf("\n");
}

El siguiente trozo de programa implementa este algoritmo:

m=a[1]; # La variable m lleva el máximo

a[1]=a[n--]; # Movemos el último a la raíz y achicamos el heap

j=1;

while(2*j<n) # mientras tenga algún hijo

{

k=2*j; # el hijo izquierdo

if(k+1<=n && a[k+1]>a[k])

k=k+1; # el hijo derecho es el mayor

if(a[j]>a[k])

break; # es mayor que ambos hijos

t=a[j];

a[j]=a[k];

a[k]=t;

j=k; # lo intercambiamos con el mayor hijo

}

Este algoritmo también demora un tiempo proporcional a la altura del árbol en el peor caso, esto es, O(log n).