Colas de prioridad

  • Introducción
  • STL, priotity_queue

Introducción

Antes de explicar que son las colas de prioridad se explicará que es un heap, montículo, debido a que es una de las mejores estructuras para implementar una cola de prioridad.

Un heap es una estructura de datos que almacena un árbol binario completo. Además, el árbol debe cumplir la siguiente propiedad: para cada nodo su valor debe ser menor (mayor) al valor de sus hijos en un Min (Max) Heap.

Para representar un heap como un arreglo se toman las siguientes convenciones:

1) el nodo que está en la posición i tiene su hijo izquierdo en la posición 2i y el hijo derecho en la posición 2i+1;
2) el padre de i está en la posición entero(i/2).

Figura 1. Un Min Heap

Debido a que en un min (max) heap el valor de cada nodo es menor (mayor) que el valor de sus hijos, esto nos garantiza que el nodo raíz es el menor (mayor) de los elementos contenidos en el heap; si usamos un arreglo para representar el heap, el nodo raíz es el primer elemento del arreglo.

Para obtener el siguiente menor (mayor) elemento del heap seguimos los siguientes pasos:

1) quitamos la raíz del heap 2) convetimos el último nodo en la raíz del heap 3) restauramos la propiedad del heap.

Si usamos un arreglo, el paso 1 y 2 consiste en reemplazar el primer elemento del arreglo por el último y disminuir en uno el tamaño del arreglo. Para restaurar la propiedad del heap, usamos la función make_heap de la clase algorithm de la STL; está construye un Max Heap.

Ejemplo de uso de la función make_heap

#include <cstdio>    // printf
#include <algorithm> // make_heap

using namespace std;

main()
{
  int A[] = {1, 4, 2, 8, 5, 7}, N = 6;

  printf("Valores antes de construir el Heap:\n");
  for (int i=0; i<N; i++)  printf("%d ", A[i]);
  printf("\n");
  // 1 4 2 8 5 7

  make_heap(A, A+N);

  printf("Valores despues de construir el Heap:\n");
  for (int i=0; i<N; i++)  printf("%d ", A[i]);
  printf("\n");
  // 8 5 7 4 1 2
}
 

Las colas de prioridad son estructuras de datos en la que los datos se recuperan de acuerdo a su prioridad. Es decir, de dos elementos primero se recupera al que tenga mayor prioridad, y si tienen la misma prioridad primero se recupera al que llego primero. Se suelen implementar usando heaps.

STL, priotity_queue

La STL nos proporciona una cola de prioridad, implementada usando un Max Heap, esta función usa el operador < para determinar la prioridad de los elementos. Para usarla se debe incluir la libreria queue:

#include < queue >.

Para definir una cola de prioridad se usa el siguiente código:

priority_queue nombre;

Las funciones que podemos usar para trabajar con ella son las siguientes:

pq.empty(); regresa true si la cola de prioridad pq esta vacía
pq.push(x); inserta x en la cola de prioridad pq
pq.front(); regresa el elemento de mayor prioridad en la cola pq
pq.pop(); elimina el elemento de mayor prioridad en la cola pq

Ejemplo

En el siguiente ejemplo se almacenan los valores 3, 1, 2, 5 y 4 en una cola de prioridad, después se recuperan y se imprimen.

#include <cstdio>  // printf
#include <queue>   // priority_queue

using namespace std;

void main()
{
  priority_queue <int> pq;

  // insertamos los valores
  pq.push(3); pq.push(1); pq.push(5); pq.push(5); pq.push(4);

  // recuperamos e imprimirmos: 1, 2, 3, 4, 5
  while(!pq.empty()) {
    printf("%d ", pq.top());
    pq.pop();
  }
  printf("\n");
}