Colas de prioridad

Una cola de prioridades es una estructura de datos en la que los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen.

Este tipo especial de colas tienen las mismas operaciones que las colas , pero con la condición de que los elementos se atienden en orden de prioridad.

Ejemplos de la vida diaria serían la sala de urgencias de un hospital, ya que los enfermos se van atendiendo en función de la gravedad de su enfermedad.

Entendiendo la prioridad como un valor numérico y asignando a altas prioridades valores pequeños, las colas de prioridad nos permiten añadir elementos en cualquier orden y recuperarlos de menor a mayor.

Hay 2 formas de implementación:

  • Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
  • Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

Tipos

  • Colas de prioridades con ordenamiento ascendente: en ellas los elementos se insertan de forma arbitraria, pero a la hora de extraerlos, se extrae el elemento de menor prioridad.
  • Colas de prioridades con ordenamiento descendente: son iguales que la colas de prioridad con ordenamiento ascendente, pero al extraer el elemento se extrae el de mayor prioridad.

+

Propiedad estructural

La única estructura que proporciona cotas de tiempo logarítmicas es el árbol por lo que parece natural que el montículo organice sus datos como tal. Como queremos que la cota logarítmica se mantenga en el caso peo, el árbol debería estar equilibrado.

Un árbol binario completo es un árbol completamente lleno, con la excepción del nivel inferior, que debe llenarse de izquierda a derecha. La característica distintiva del árbol binario completo es que no faltan nodos en el árbol.

El uso de un vector para almacenar  un árbol  recibe el nombre de representación implícita . Como un resultado de usar esta implementaron, no solamente  no son necesarias las referencias a los hijos, sino que ademas las operaciones de recorrido de los arboles son muy simples y muy probablemente lo bastante rápidos en la mayoría de los computadores. El montículo consistirá en un vector de objetos y un entero que representa el tamaño actual de montículo.

Operaciones permitidas

Las operaciones de las colas de prioridad son las mismas que las de las colas genéricas:

  • Crear: se crea la cola vacía.
  • Encolar: se añade un elemento a la cola, con su correspondiente prioridad.
  • Desencolar: se elimina el elemento frontal de la cola.
  • Frente: se devuelve el elemento frontal de la cola.
  • Destruye: elimina la cola de memoria.

La cola de prioridad es una estructura de datos fundamental que solo permite el acceso al elemento mínimo. El montículo binario soporta la inserción de nuevos elementos y la eliminación del elemento mínimo en tiempo logarítmico en el caso peor. Solamente usa un vector y es muy simple de implementar.


  1. package EstructurasDAtos;
  2. import Soporte.*; importo Soporte.Comparable;
  3. import Excepciones.*;
  4. //Clase MonticuloBinario
  5. //
  6. // CONSTRUCCIÓN: con un centinela con valor menos infinito
  7. //
  8. // ********************OPERACIONES PÚBLICAS*********************
  9. // void insertar ( x )                  –> Inserta x
  10. // Comparable eleminarMin ( )    —> Elimina y devuleve el menor
  11. // Comparable buscarMin ( )         –> Devuleve el menor elemento
  12. // boolean esVacia ( ) –> Devuleve true si está vacío
  13. //void vaciar ( ) –> Elemina todos los elementos
  14. // void introducir ( x ) –> Inserta x (perezosamente)
  15. //************************ERRORES****************************
  16. //buscarMin y eleminarMin lanzan DesbordaminetoInferior si vacío
  17. /**
  18. Implementa un monticulo binario.
  19. Permite insecion perezosa y porporciona un metodo linal de
  20. construccion de monticulos.
  21. Observe que todas las comparaciones estan basada en compara.
  22. /
  23. public class MonticuloBinario implements ColaPriorirdad
  24. {
  25. publuc MonticuloBinario ( Comparable indNeg )
  26. {
  27. tamActual = 0;
  28. ordenado = true;
  29. obtenerVector ( CAPACIDAD);
  30. vrector [ 0 ] = infNeg;
  31. }
  32. public void insertar ( Comparable x)
  33. {
  34. comprobarTam( );
  35. vector [ ++tamActual ] = x:
  36. if(  x.menorQue( vecotr [ tamActual / 2 * ) )
  37. ordenado = false;
  38. }
  39. public void isertar ( Comparable x )
  40. {
  41. if(¡ordenado )
  42. {
  43. introducir ( x );
  44. return;
  45. }
  46. comprobarTam( );
  47. //Reflotamiento
  48. int huevo = ++tamActual;
  49. for( ; x.menorQue( vector[ huevo / 2  ] ); huevo /= 2 )
  50. vector[ hueco ] = vector [ hueco / 2 ];
  51. vector[ huevo ] = x;
  52. }
  53. public Comparable buscarMin ( ) throws DesbordamientoInferior
  54. {
  55. if( esVacia( ) )
  56. throw new DebordamientoInferior ( “Monticulo vacio2 );
  57. if( ¡ordenado )
  58. arreglarMonticulo( );
  59. retu vector [ 1 ]:
  60. }
  61. public Comparable eliminarMin( ) thores DesbordamientoInferior
  62. {
  63. Comparable elemMin = buscarMin (  );
  64. Vector [ 1 ] = vecotr [ tamActual -- ];
  65. Hundir ( 2 );
  66. Return elemenMin;
  67. }
  68. public boolean esVacia ( )
  69. { return tamActual== 0; }
  70. pblic void vacia 8 )
  71. { tamActual = 0; )
About these ads
This entry was posted in Estructuras de datos. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s