Algoritmos de aprendizaje

Capítulo 4. Amontonarse

Este trabajo se ha traducido utilizando IA. Agradecemos tus opiniones y comentarios: [e-mail]

En este capítulo aprenderás

• Los tipos de datos cola y cola prioritaria.

• La estructura binaria de datos del montón, inventada en 1964, que puede almacenarse en una matriz.

• Que en un montón binario máximo, se considera que una entrada con una prioridad numérica mayor tiene mayor prioridad que una entrada con una prioridad numérica menor. En un montón binario mínimo, las entradas con prioridad numérica menor tienen mayor prioridad.

• Cómo poner en cola una entrada (valor, prioridad) en un montón binario en O(log N), donde N es el número de entradas del montón.

• Cómo encontrar el valor con mayor prioridad en un montón binario en O(1).

• Cómo eliminar el valor con mayor prioridad de un montón binario en O(log N).

En lugar de almacenar simplemente una colección de valores, ¿qué pasaría si almacenaras una colección de entradas, donde cada entrada tuviera un valor y unaprioridad asociada representada como un número? Dadas dos entradas, aquella cuya prioridad sea mayor será más importante que la otra. El reto esta vez es hacer posible insertar nuevas entradas (valor, prioridad) en una colección y poder eliminar y devolver el valor de la entrada con mayor prioridad de la colección.

Este comportamiento define una cola de prioridad, untipo de datos que admite eficazmente enqueue(value, priority) y dequeue(), que elimina el valor con mayor prioridad. La cola de prioridad es diferente de la tabla de símbolos comentada en el capítulo anterior, porque no necesitas conocer la prioridad de antemano cuando solicites eliminar el valor con mayor prioridad.

Cuando una discoteca muy concurrida se llena demasiado, se forma una cola de gente fuera, como se muestra en la Figura 4-1. A medida que más gente intenta entrar en la discoteca, tiene que esperar al final de la cola. La primera persona que entra en la discoteca desde la cola es la que ha esperado más tiempo. Este comportamiento representa el tipo de datos abstracto esencial dela cola, con una operación enqueue(value) que añadevalue para convertirse en el valor más nuevo al final de la cola, ydequeue() elimina el value más antiguo que queda en la cola. Otra forma de describir esta experiencia es "Primero en entrar, primero en salir" (FIFO), que es la abreviatura de "El primero [en entrar] en [la cola es el] primero [en salir] de [la cola]".

Figura 4-1. Esperando en la cola de un club nocturno

En el capítulo anterior, describí la estructura de datos de lista enlazada, que volveré a utilizar con un Node que almacena un value para la cola:

class Node:
  def __init__(self, val):
    self.value = val
    self.next = None

Utilizando esta estructura, la implementación de Queue delListado 4-1 tiene una operación enqueue() para añadir un valor al final de una lista enlazada. La Figura 4-2 muestra el resultado de encolar (en este orden) "Joe", "Jane" y "Jim" a una cola de discoteca.

"Joe" será el primer cliente retirado de la cola, lo que dará lugar a una cola con dos clientes, en la que "Jane" seguirá siendo la primera de la cola.

En Queue, las operaciones enqueue() y dequeue() se realizan en tiempo constante, independientemente del número total de valores en la cola.

Figura 4-2. Modelización de una cola de discoteca con tres nodos

Listado 4-1. Implementación en lista enlazada del tipo de datos Queue

class Queue:
  def __init__(self):
    self.first = None                     
    self.last = None

  def is_empty(self):
    return self.first is None             

  def enqueue(self, val):
    if self.first is None:                
      self.first = self.last = Node(val)
    else:
      self.last.next = Node(val)          
      self.last = self.last.next

  def dequeue(self):
    if self.is_empty():
      raise RuntimeError('Queue is empty')

    val = self.first.value                
    self.first = self.first.next          
    return val

Inicialmente, first y last son None.

Un Queue está vacío si first es None.

Si Queue está vacío, establece first y last en el recién creado Node.

Si Queue no está vacío, añade después de last, y ajusta last para que apunte al recién creado Node.

first se refiere a la dirección Node que contiene el valor que hay que devolver.

Configura first para que sea el segundo Node de la lista, si existe.

Cambiemos de situación: la discoteca decide permitir a los clientes que gasten cualquier cantidad de dinero comprar un pase especial que registra la cantidad total gastada. Por ejemplo, un cliente puede comprar un pase de 50 $, mientras que otro compra un pase de 100 $. Cuando el club se llena demasiado, la gente se une a la cola para esperar. Sin embargo, la primera persona que entra en la discoteca desde la cola es la que tiene un pase que representa el pago más alto de todos los que están en la cola. Si dos o más personas de la cola están empatadas por haber gastado más dinero, se elige a una de ellas para entrar en la discoteca. Se considera que los clientes sin pase han pagado 0$.

En la Figura 4-3, el cliente del centro con un pase de 100$ es el primero en entrar en el club, seguido de los dos clientes de 50$ (en cierto orden). Todos los demás clientes sin pase se consideran equivalentes, por lo que cualquiera de ellos podría ser el siguiente en entrar en el club.

Figura 4-3. Los clientes pueden avanzar más rápido con el pase comprado

Nota

Un tipo de datos de cola de prioridad no especifica qué hacer cuando dos o más valores comparten la misma prioridad máxima. De hecho, en función de su implementación, la cola de prioridad podría no devolver los valores en el orden en que fueron encolados. Una cola de prioridad basada en un montón -como la que se describe en este capítulo- no devuelve valores con la misma prioridad en el orden en que se pusieron en cola. El módulo integrado heapq implementa una cola de prioridad utilizando un montón, del que hablo en el Capítulo 8.

Este comportamiento revisado define el tipo de datos abstracto cola de prioridad; sin embargo, enqueue() y dequeue() ya no pueden implementarse eficientemente en tiempo constante. Por un lado, si utilizas una estructura de datos de lista enlazada, enqueue() seguiría siendo O(1), pero dequeue() tendría que comprobar potencialmente todos los valores de la cola de prioridad para localizar el de mayor prioridad, lo que requeriría O(N) en el peor de los casos. Por otro lado, si mantienes todos los elementos ordenados por prioridad, dequeue()requiere O(1), pero ahora enqueue() requiere O(N) en el peor de los casos para encontrar dónde insertar el nuevo valor.

Dada nuestra experiencia hasta la fecha, aquí tienes cinco posibles estructuras que utilizan todas un objeto Entry para almacenar una entrada (valor, prioridad):

Matriz

Un array de entradas desordenadas que no tiene estructura y espera lo mejor. enqueue() es una operación de tiempo constante, pero dequeue() debe buscar en todo el array el valor de mayor prioridad para eliminarlo y devolverlo. Como el array tiene un tamaño fijo, esta cola de prioridad podría llenarse.

Incorporado

Una lista desordenada manipulada mediante operaciones incorporadas en Python que ofrece un rendimiento similar al de Matriz.

PedidoA

Una matriz que contiene entradas ordenadas por prioridad creciente. Enenqueue(), utiliza la variación Búsqueda binaria de matrices (delListado 2-4) para localizar dónde debe colocarse la entrada, y desplaza manualmente las entradas de la matriz para hacer sitio. dequeue() es de tiempo constante porque las entradas están totalmente ordenadas, y la entrada de mayor prioridad se encuentra al final de la matriz. Como la matriz tiene un tamaño fijo, esta cola de prioridad podría llenarse.

Enlazado

Una lista enlazada de entradas cuya primera entrada tiene la máxima prioridad de todas las entradas de la lista; cada entrada posterior es menor o igual que la entrada anterior. Esta implementación encola los nuevos valores en su ubicación adecuada en la lista enlazada para permitir que dequeue() sea una operación en tiempo constante.

PedidoL

Una lista Python que contiene entradas ascendentes por prioridad creciente. Enenqueue(), utiliza la variación de Búsqueda de Matrices Binarias para insertar dinámicamente la entrada en su ubicación correcta. dequeue() es tiempo constante porque la entrada de mayor prioridad siempre está al final de la lista.

Para comparar estas implementaciones, ideé un experimento que realiza de forma segura 3N/2 enqueue() operaciones y 3N/2 dequeue()operaciones. Para cada implementación, mido el tiempo total de ejecución y lo divido por 3N para calcular el coste medio de la operación. Como se muestra enla Tabla 4-1, una matriz de tamaño fijo es la más lenta, mientras que las listas incorporadas de Python reducen el tiempo a la mitad. Una matriz de entradas ordenadas vuelve a reducir el tiempo a la mitad, y una lista enlazada mejora otro 20%. Aun así, el claro ganador es OrderL.

Tabla 4-1. Rendimiento medio de la operación (tiempo en ns) en instancias del problema de tamaño N

N	Pila	PedidoL	Enlazado	PedidoA	Incorporado	Matriz
256	6.4	2.5	3.9	6.0	8.1	13.8
512	7.3	2.8	6.4	9.5	14.9	26.4
1,024	7.9	3.4	12.0	17.8	28.5	52.9
2,048	8.7	4.1	23.2	33.7	57.4	107.7
4,096	9.6	5.3	46.6	65.1	117.5	220.3
8,192	10.1	7.4	95.7	128.4	235.8	446.6
16,384	10.9	11.7	196.4	255.4	470.4	899.9
32,768	11.5	20.3	—	—	—	—
65,536	12.4	36.8	—	—	—	—

Para estos enfoques, el coste medio de una operación enqueue() o dequeue()aumenta en proporción directa a N. Sin embargo, la columna denominada "Montón" de laTabla 4-1 muestra los resultados de rendimiento utilizando una estructura de datosHeap; su coste medio aumenta en proporción directa alog(N), como puedes ver en la Figura 4-4, y supera significativamente a la implementación que utiliza listas ordenadas de Python. Sabes que tienes un rendimiento logarítmico cuando sólo observas un aumento constante del tiempo de ejecución cuando se duplica el tamaño del problema. Enla Tabla 4-1, con cada duplicación, el tiempo de rendimiento aumenta unos 0,8 nanosegundos.

La estructura de datos montón, inventada en 1964, proporciona un rendimiento O(log N) para las operaciones de una cola prioritaria. En el resto de este capítulo, no me preocupan los valores que se encolan en una entrada: pueden ser cadenas o valores numéricos, o incluso datos de imagen; ¿a quién le importa? Sólo me preocupa la prioridad numérica de cada entrada. En cada una de las figuras restantes de este capítulo, sólo se muestran las prioridades de las entradas que estaban en cola. Dadas dos entradas en un montón máximo, aquella cuya prioridad sea mayor en valor tiene mayor prioridad.

Un montón tiene un tamaño máximo, M -conocido de antemano-, que puede almacenar N < M entradas. A continuación explico la estructura de un montón, muestro cómo puede crecer y decrecer con el tiempo dentro de su tamaño máximo, y muestro cómo una matriz ordinaria almacena sus N entradas.

Figura 4-4. El comportamiento O(log N) de Heap supera el comportamiento O(N) de otros enfoques

Montones binarios máximos

Puede parecer una idea extraña, pero ¿y si sólo "ordeno parcialmente" las entradas? La Figura 4-5 muestra un max montón que contiene 17 entradas; para cada entrada, sólo se muestra su prioridad. Como puedes ver, el nivel 0 contiene una única entrada que tiene la prioridad más alta entre todas las entradas del montón máximo. Cuando hay una flecha, x → y, puedes ver que la prioridad de la entrada x ≥ la prioridad de la entrada y.

Figura 4-5. Un ejemplo de montón binario máximo

Estas entradas no están totalmente ordenadas como lo estarían en una lista ordenada, así que tienes que buscar un rato para encontrar la entrada con menor prioridad (pista: está en el nivel 3). Pero la estructura resultante tiene algunas buenas propiedades. Hay dos entradas en el nivel 1, una de las cuales debe ser la segunda más prioritaria (o empatada con la más prioritaria, ¿no?). Cada nivel k-exceptoel último- está lleno y contiene 2^k entradas. Sólo el nivel inferior está parcialmente lleno (es decir, tiene 2 entradas de 16 posibles), y se llena de izquierda a derecha. También puedes ver que puede existir la misma prioridad en el montón: las prioridades 8 y 14 aparecen varias veces.

Cada entrada no tiene más de 2 flechas que salen de ella, lo que hace que sea unmontón binario máximo. Tomemos la entrada del nivel 0 cuya prioridad es 15: la primera entrada del nivel 1 con prioridad 13 es su hija izquierda; la segunda entrada del nivel 1 con prioridad 14 es su hija derecha. La entrada con prioridad 15 es el padre de las dos entradas hijas del nivel 1.

A continuación se resumen las propiedades de un montón binario máximo:

Propiedad ordenada en montón

La prioridad de una entrada es mayor o igual que la prioridad de su hija izquierda y de su hija derecha (si existe alguna de ellas). La prioridad de cada entrada (salvo la superior) es menor o igual que la prioridad de su entrada padre.

Propiedad forma de montón

Cada nivel k debe llenarse con 2^k entradas (de izquierda a derecha) antes de que aparezca cualquier entrada en el nivel k + 1.

Cuando un montón binario sólo contiene una única entrada, sólo hay un único nivel, 0, porque²⁰ = 1. ¿Cuántos niveles son necesarios para que un montón binario almacene N > 0 entradas? Matemáticamente, necesito definir una fórmula,L(N), que devuelva el número de niveles necesarios para N entradas.La Figura 4-6 contiene una visualización para ayudar a determinar L(N). Contiene 16 entradas, cada una etiquetada con un subíndice que comienza en _e1 en la parte superior y aumenta de izquierda a derecha hasta que no hay más entradas en ese nivel, antes de comenzar de nuevo en la entrada situada más a la izquierda en el siguiente nivel.

Figura 4-6. Determinar los niveles necesarios para un montón binario con N entradas

Si sólo hubiera 7 entradas en un montón, habría 3 niveles que contuvieran las entradas _e1 a _e7. Se necesitarían 4 niveles para 8 entradas. Si sigues las flechas de la izquierda desde arriba, puedes ver que los subíndices siguen un patrón específico: _e1, _e2, _e4, _e8 y _e16, lo que sugiere que las potencias de 2 desempeñarán un papel. Resulta que L(N) = 1 + floor(log(N)).

Consejo

Cada nuevo nivel completo del montón binario contiene más entradas que el número total de entradas de todos los niveles anteriores. Cuando aumentas la altura de un montón binario en un solo nivel, ¡el montón binario puede contener más del doble de entradas (un total de 2N + 1 entradas, donde N es el número de entradas existentes)!

Debes recordar que, con los logaritmos, cuando duplicas N, el valor delog(N) aumenta en 1. Esto se representa matemáticamente del siguiente modo:log(2N) = 1 + log(N). ¿Cuáles de las cuatro opciones dela Figura 4-7 son válidas para los montones binarios máximos?

Figura 4-7. ¿Cuáles de estos son montones binarios máximos válidos?

Primero revisa la propiedad forma de montón de cada una de estas opciones. Las opciones nº 1 y nº 2 son aceptables, ya que cada nivel está completamente lleno. La opción nº 3 es aceptable porque sólo su último nivel es parcial y contiene tres (de cuatro posibles) entradas de izquierda a derecha. La opción nº 4 incumple la propiedad de forma de montón porque su último nivel contiene tres entradas, pero falta la entrada más a la izquierda posible.

Considera ahora la propiedad de ordenación del montón para los montones binarios máximos, que garantiza que la prioridad de cada padre es mayor o igual que las prioridades de sus hijos. La opción nº 1 es válida, como puedes confirmar comprobando cada flecha posible. La opción nº 3 no es válida porque la entrada con prioridad 8 tiene un hijo a la derecha cuya prioridad 9 es mayor. La opción nº 2 no es válida porque la entrada con prioridad 4 en el nivel 0 tiene una prioridad menor que sus dos entradas hijas.

Nota

La opción nº 2 es en realidad un ejemplo válido de montón binario mínimo, en el que la prioridad de cada entrada padre es menor o igual que la prioridad de sus hijos. Los montones binarios mínimos se utilizarán en el Capítulo 7.

Necesito asegurarme de que ambas propiedades del montón se mantienen después de enqueue() odequeue() (que elimina el valor con mayor prioridad en el montón máximo). Esto es importante porque entonces podré demostrar que ambas operaciones se realizarán en O(log N), una mejora significativa respecto a los enfoques documentados anteriormente en la Tabla 4-1, que eran limitados ya que enqueue() o dequeue() tenían un comportamiento en el peor de los casos de O(N).

Insertar un (valor, prioridad)

Después de invocar enqueue(value, priority) en un montón binario máximo, ¿dónde debe colocarse la nueva entrada? He aquí una estrategia que siempre funciona:

• Coloca la nueva entrada en el primer lugar vacío disponible del último nivel.

• Si ese nivel está lleno, amplía el montón para añadir un nuevo nivel, y coloca la nueva entrada en la posición más a la izquierda del nuevo nivel.

En la Figura 4-8, se inserta una nueva entrada con prioridad 12 en la tercera posición del nivel 4. Puedes confirmar que la propiedad forma de montón es válida (porque las entradas del nivel parcial 4 empiezan por la izquierda sin huecos). Sin embargo, podría darse el caso de que ahora se haya violado la propiedad de ordenación del montón.

La buena noticia es que posiblemente sólo tenga que reordenar las entradas que se encuentran en el camino desde la entrada recién colocada hasta la entrada más alta del nivel 0. La Figura 4-10 muestra el resultado final tras restaurar la propiedad de ordenación del montón; como puedes ver, las entradas de la ruta sombreada se han reordenado adecuadamente, en orden decreciente (o igual) de arriba hacia abajo.

Figura 4-8. El primer paso para insertar una entrada es colocarla en la siguiente posición disponible

Nota

Una ruta a una entrada concreta de un montón binario es una secuencia de entradas formada siguiendo las flechas (izquierda o derecha) desde la entrada única del nivel 0 hasta llegar a la entrada concreta.

Para rehacer el montón máximo de forma que satisfaga la propiedad de orden del montón, la nueva entrada añadida "nada" por este camino hasta su ubicación correcta, utilizando intercambios por pares. Basándonos en este ejemplo, la Figura 4-8 muestra que la entrada recién añadida con prioridad 12 invalida la prioridad ordenada en el montón, ya que su prioridad es mayor que la de su padre, cuya prioridad es 2. Intercambia estas dos entradas para producir el montón máximo de la Figura 4-9 y continúa hacia arriba.

Figura 4-9. El segundo paso hace subir la entrada un nivel según sea necesario

Puedes confirmar que, de 12 hacia abajo, la estructura es un montón binario máximo válido con dos entradas. Sin embargo, la entrada con 12 sigue invalidando la propiedad de ordenación del montón, ya que su entrada padre tiene una prioridad de 9, que es menor, así que intercambia con su padre, como se muestra en la Figura 4-10.

De la entrada resaltada 12 hacia abajo en la Figura 4-10, la estructura es un montón binario máximo válido. Cuando intercambiaste las entradas 9 y 12, no tuviste que preocuparte por la estructura desde la 8 hacia abajo , ya que se sabe que todos esos valores son menores o iguales que 8, lo que significa que todos serán menores o iguales que 12. Como 12 es menor que su entrada padre con prioridad 13, se satisface la propiedad de ordenación del montón.

Figura 4-10. El tercer paso hace subir la entrada un nivel según sea necesario

Intenta por tu cuenta enqueue(value, 16) en el montón representado enla Figura 4-10, que inicialmente coloca la nueva entrada en la cuarta ubicación del nivel 4, como hija derecha de la entrada con prioridad 9. Esta nueva entrada nadará hasta el nivel 0, dando como resultado el montón binario máximo que se muestra en la Figura 4-11.

Figura 4-11. Añadir entrada con prioridad 16 nada hacia arriba

El peor caso es cuando pones en cola una nueva entrada cuya prioridad es mayor que cualquier entrada del montón binario máximo. El número de entradas en el camino es 1 + floor(log(N)), lo que significa que el mayor número de intercambios es uno menor, o floor(log(N)). Ahora puedo afirmar claramente que el tiempo para rehacer el montón binario máximo después de una operación enqueue() es O(logN). Este gran resultado sólo aborda la mitad del problema, ya que también debo asegurarme de que puedo eliminar eficazmente la entrada con mayor prioridad en el montón binario máximo.

Eliminar el valor con mayor prioridad

Encontrar la entrada con mayor prioridad en un montón binario máximo es sencillo: siempre será la entrada única del nivel 0 en la parte superior. Pero no puedes eliminar esa entrada, ya que entonces se violaría la propiedad de forma del montón al tener un hueco en el nivel 0. Afortunadamente, existe una estrategia en dequeue()que puede eliminar la entrada superior y rehacer eficientemente el montón binario máximo, como muestro en la siguiente secuencia de figuras:

1. Elimina la entrada situada más a la derecha en el nivel inferior y recuérdala. La estructura resultante satisfará las propiedades de orden y forma del montón.

2. Guarda el valor de la entrada de mayor prioridad en el nivel 0 para que pueda ser devuelto.

3. Sustituye la entrada del nivel 0 por la entrada que has eliminado del nivel inferior del montón. Esto podría romper la propiedad de ordenación del montón.

Para lograr este objetivo, primero elimina y recuerda la entrada 9, como se muestra en laFigura 4-12; la estructura resultante sigue siendo un montón. A continuación, registra el valor asociado a la prioridad más alta del nivel 0 para que pueda ser devuelto (no se muestra aquí).

Figura 4-12. El primer paso es eliminar la entrada inferior

Por último, sustituye la entrada única del nivel 0 por la entrada que se eliminó, lo que da como resultado el montón máximo roto que se muestra en la Figura 4-13. Como puedes ver, la prioridad de la entrada única del nivel 0 no es mayor que la de su hija izquierda (con prioridad 15) y su hija derecha (con prioridad 14). Para rehacer el montón máximo, tienes que "hundir" esta entrada a un lugar más abajo dentro del montón para restablecer la propiedad de ordenación del montón.

Figura 4-13. Montón roto al intercambiar la última entrada con el nivel 0

Empezando por la entrada que no es válida (es decir, la entrada de nivel 0 con prioridad 9), determina cuál de sus hijos (es decir, izquierdo o derecho) tiene mayor prioridad; si sólo existe el hijo izquierdo, utiliza ése. En este ejemplo, el hijo izquierdo con prioridad 15 tiene mayor prioridad que el hijo derecho con prioridad 14, y la Figura 4-14 muestra el resultado de intercambiar la entrada superior por la entrada hija seleccionada con mayor prioridad.

Figura 4-14. Intercambiar la entrada superior con su hija izquierda, que tenía mayor prioridad

Como puedes ver, toda la subestructura basada en la entrada con prioridad 14 del nivel 1 es un montón binario máximo válido, por lo que no necesita cambiar. Sin embargo, la nueva entrada intercambiada (con prioridad 9) viola la propiedad de ordenación del montón (es menor que la prioridad de sus dos hijas), por lo que esta entrada debe seguir "hundiéndose" hacia la izquierda, como se muestra en la Figura 4-15, ya que la entrada con prioridad 13 es la mayor de sus dos entradas hijas.

Figura 4-15. Descendiendo un nivel adicional

¡Ya casi está! La Figura 4-15 muestra que la entrada con prioridad 9 tiene un hijo derecho cuya prioridad 12 es mayor, así que intercambiamos estas entradas, lo que finalmente restaura la propiedad ordenada en el montón para este montón, como se muestra en la Figura 4-16.

Figura 4-16. Montón resultante tras hundir la entrada en su ubicación correcta

No existe un camino simple de entradas ajustadas, como vimos al encolar una nueva entrada en la cola de prioridad, pero aún así es posible determinar el número máximo de veces que se repitió el paso "hundir", es decir, un valor menor que el número de niveles del montón binario máximo, ofloor(log(N)).

También puedes contar el número de veces que se compararon entre sí las prioridades de dos entradas. En cada paso de "hundimiento hacia abajo", hay como máximo dos comparaciones: una comparación para encontrar la mayor de las dos entradas hermanas, y luego una comparación para determinar si la entrada padre es mayor que la mayor de estas dos entradas hermanas. En total, esto significa que el número de comparaciones no es superior a 2 × floor(log(N)).

Es increíblemente importante que el montón binario máximo pueda tanto añadir una entrada como eliminar la entrada con mayor prioridad en un tiempo que sea directamente proporcional a log(N) en el peor de los casos. Ahora es el momento de poner en práctica esta teoría mostrando cómo implementar un montón binario utilizando una matriz ordinaria.

¿Te has dado cuenta de que la propiedad "forma de montón" garantiza que puedas leer todas las entradas en secuencia de izquierda a derecha, desde el nivel 0 hacia abajo a través de cada nivel posterior? Puedo aprovechar esta idea almacenando un montón binario en una matriz normal.

Representar un montón binario en una matriz

La Figura 4-17 muestra cómo almacenar un montón binario máximo de N = 18 entradas dentro de una matriz fija de tamaño M > N. Este montón binario máximo de cinco niveles puede almacenarse en una matriz ordinaria asignando cada posición del montón binario a una posición de índice única. Cada cuadro discontinuo contiene un número entero que corresponde a la posición de índice en la matriz que almacena la entrada del montón binario. Una vez más, al representar un montón binario, sólo muestro las prioridades de las entradas.

Figura 4-17. Almacenar un montón binario máximo en una matriz

Cada entrada tiene una ubicación correspondiente en la matriz storage[]. Para simplificar todos los cálculos, la ubicación storage[0] no se utiliza y nunca almacena una entrada. La entrada superior con prioridad 15 se coloca enstorage[1]. Puedes ver que su hijo izquierdo, con prioridad 13, se coloca en storage[2]. Si la entrada de storage[k] tiene un hijo izquierdo, esa entrada es storage[2*k]; la Figura 4-17 confirma esta observación (basta con inspeccionar los cuadros discontinuos). Del mismo modo, si la entrada de storage[k]tiene un hijo derecho, esa entrada está en storage[2*k+1].

Para k > 1, el padre de la entrada en storage[k] puede encontrarse enstorage[k//2], donde k//2 es el valor entero resultante de truncar el resultado de k dividido por 2. Al colocar la entrada más alta del montón en storage[1], sólo tienes que realizar la división entera por dos para calcular la ubicación del padre de una entrada. El padre de la entrada en storage[5] (con prioridad 11) se encuentra en storage[2] porque 5//2 = 2.

La entrada en storage[k] es una entrada válida cuando 0 < k ≤ N, donde N representa el número de entradas en el montón binario máximo. Esto significa que la entrada en storage[k] no tiene hijos si 2 × k > N; por ejemplo, la entrada en storage[10] (que tiene prioridad 1) no tiene ningún hijo a la izquierda, porque 2 × 10 = 20 > 18. También sabes que la entrada de storage[9](que casualmente tiene prioridad 9) no tiene hijo derecho, porque 2 × 9 + 1 = 19 > 18.

Puesta en práctica de Nadar y Hundirse

Para almacenar un montón binario máximo, empieza con un Entry que tenga un value con su priority asociado:

class Entry:
  def __init__(self, v, p):
    self.value = v
    self.priority = p

El listado 4-2 almacena un montón binario máximo en una matriz,storage. Cuando se instancia, la longitud de storage es uno mayor que el parámetro size, para ajustarse a los cálculos descritos anteriormente, en los que la primera entrada se almacena en storage[1].

Hay dos métodos de ayuda que simplifican la presentación del código. Has visto cuántas veces he comprobado si una entrada tiene una prioridad menor que otra entrada. La función less(i,j) devuelveTrue cuando la prioridad de la entrada en storage[i] es menor que la prioridad de la entrada en storage[j]. Cuando nado hacia arriba o me hundo hacia abajo, necesito intercambiar dos entradas. La función swap(i,j) intercambia las ubicaciones de las entradas en storage[i] y storage[j].

Listado 4-2. Implementación del montón mostrando los métodos enqueue() y swim()

class PQ:
  def less(self, i, j):                               
    return self.storage[i].priority < self.storage[j].priority

  def swap(self, i, j):                               
    self.storage[i],self.storage[j] = self.storage[j],self.storage[i]

  def __init__(self, size):                           
    self.size = size
    self.storage = [None] * (size+1)
    self.N = 0

  def enqueue(self, v, p):                            
    if self.N == self.size:
      raise RuntimeError ('Priority Queue is Full!')

    self.N += 1
    self.storage[self.N] = Entry(v, p)
    self.swim(self.N)

  def swim(self, child):                              
    while child > 1 and self.less(child//2, child):   
      self.swap(child, child//2)                      
      child = child // 2                              

less() determina si storage[i] tiene menor prioridad que storage[j].

swap() cambia la ubicación de las entradas i y j.

storage[1] hasta storage[size] almacenarán las entradas;storage[0] no se utiliza.

Para enqueue una entrada (v, p), colócala en la siguiente ubicación vacía y nada hacia arriba.

swim() rehace la matriz storage para que se ajuste a la propiedad de ordenación del montón.

El padre de la entrada en storage[child] se encuentra en storage[child//2], donde child//2 es el resultado entero de dividir child por 2.

Intercambia entradas en storage[child] y su padre storage[child//2].

Continúa hacia arriba ajustando child a su ubicación principal según sea necesario.

¡El método swim() es realmente breve! La entrada identificada por child es la nueva entrada en cola, mientras que child//2 es su entrada padre, en caso de que exista. Si la entrada padre tiene menor prioridad que la hija, se intercambian y el proceso continúa hacia arriba.

La Figura 4-18 muestra los cambios en storage iniciados porenqueue(value, 12) en la Figura 4-8. Cada fila posterior corresponde a una figura identificada anteriormente y muestra las entradas que cambian en storage. La última fila representa un montón binario máximo que se ajusta a las propiedades de orden y forma del montón.

Figura 4-18. Cambios en el almacenamiento tras la puesta en cola de la Figura 4-8

El camino desde la entrada superior hasta la entrada recién insertada con prioridad 12 consta de cinco entradas, como se sombrea en la Figura 4-18. Después de pasar dos veces por el bucle while en swim(), la entrada con prioridad 12 se intercambia con su padre, nadando finalmente hasta storage[4], donde satisface la propiedad ordenada en el montón. El número de intercambios nunca será superior a log(N), donde N es el número de entradas del montón binario.

La implementación del Listado 4-3 contiene el método sink() para restablecer la estructura del montón binario máximo después de invocar a dequeue().

Listado 4-3. Implementación del montón completada con los métodos dequeue() y sink()

  def dequeue(self):
    if self.N == 0:
      raise RuntimeError ('PriorityQueue is empty!')

    max_entry = self.storage[1]                         
    self.storage[1] = self.storage[self.N]              
    self.storage[self.N] = None
    self.N -= 1                                         
    self.sink(1)
    return max_entry.value                              

  def sink(self, parent):
    while 2*parent <= self.N:                           
      child = 2*parent
      if child < self.N and self.less(child, child+1):  
        child += 1
      if not self.less(parent, child)                   
        break
      self.swap(child, parent)                          
      parent = child

Guarda la entrada de mayor prioridad en el nivel 0.

Sustituye la entrada en storage[1] por la entrada del nivel más bajo del montón y borra de storage.

Reduce el número de entradas antes de invocar sink en storage[1].

Devuelve el valor asociado a la entrada de mayor prioridad.

Sigue comprobándolo mientras el padre tenga un hijo.

Selecciona el hijo derecho si existe y es mayor que el izquierdo.

Si parent no es menor que child, se cumple la propiedad de ordenación del montón.

Cámbialo si es necesario, y sigue hundiéndote hacia abajo, utilizando child como nuevo parent.

La Figura 4-19 muestra los cambios en storage iniciados pordequeue() a partir del montón binario máximo inicial mostrado en laFigura 4-11. La primera fila de la Figura 4-19 muestra el montón con 19 entradas. En la segunda fila, la última entrada del montón con prioridad 9 seintercambia para convertirse en la entrada superior del montón binario máximo, lo que rompe la propiedad de orden del montón; además, el montón ahora sólo contiene 18 entradas, ya que se ha eliminado una.

Figura 4-19. Cambios en el almacenamiento tras la puesta en cola de la Figura 4-11

Después de tres pasadas sucesivas por el bucle while en sink(), la entrada con prioridad 9 ha descendido a una ubicación que garantiza la propiedad de ordenación del montón. En cada fila, la entrada resaltada más a la izquierda es la entrada con prioridad 9, y las entradas sombreadas a la derecha son sus entradas hijas. Siempre que la entrada padre de 9 sea menor que una de sus hijas, debe descender para intercambiarse con la mayor de sus hijas. El número de intercambios nunca será superior a log(N).

El método sink() es el más difícil de visualizar porque no hay un camino recto que seguir, como ocurre con swim(). En la representación final destorage en la Figura 4-19, puedes ver que la entrada resaltada con prioridad 9 sólo tiene un hijo sombreado (con prioridad 2). Cuandosink() termina, sabes que la entrada que se estaba hundiendo o bien ha alcanzado una posición de índice, p, en la que no tiene hijos (es decir, porque 2 × p es una posición de índice inválida storage mayor que N), o bien es mayor o igual (es decir, no menor que) que la mayor de sus entradas hijas.

Advertencia

El orden de las sentencias en dequeue() es crítico. En concreto, tienes que reducir N en 1 antes de llamar a sink(1), de lo contrario sink()pensará erróneamente que la ubicación del índice en storage correspondiente a la entrada recientemente retirada de la cola sigue formando parte del montón. Puedes ver en el código que storage[N] se establece en None para garantizar que no se piense erróneamente que la entrada forma parte del montón.

Si quieres convencerte de que la lógica de dequeue() es correcta, considera cómo funciona con un montón que contiene una sola entrada. Recuperará max_entry y pondrá N a 0 antes de llamar a sink(), que no hará nada ya que 2 × 1 > 0.

Resumen

La estructura binaria del montón ofrece una implementación eficiente del tipo de datos abstracto cola de prioridad. Numerosos algoritmos, como los tratados en el Capítulo 7, dependen de las colas de prioridad.

• Puedes enqueue() una entrada (valor, prioridad) en rendimiento O(log N).

• Puedes dequeue() la entrada con mayor prioridad en rendimiento O(log N).

• Puedes informar del número de entradas de un montón con un rendimiento de O(1).

En este capítulo me he centrado exclusivamente en los montones binarios max. Sólo tienes que hacer un pequeño cambio para realizar un montón binario mín, en el que las entradas de mayor prioridad tengan valores numéricos de prioridad más pequeños. Esto será relevante enel capítulo 7. En el Listado 4-2, sólo tienes que reescribir el método less()para utilizar mayor-que (>) en lugar de menor-que (<). El resto del código permanece igual.

def less(self, i, j):
  return self.storage[i].priority > self.storage[j].priority

Aunque una cola prioritaria puede crecer o decrecer con el tiempo, la implementación basada en el montón predetermina un tamaño inicial, M, para almacenar las entradas N < M. Una vez que el montón está lleno, no se pueden poner más entradas en la cola de prioridad. Es posible hacer crecer (y encoger) automáticamente la matriz de almacenamiento, de forma similar a lo que mostré en el Capítulo 3. Siempre que utilices el redimensionamiento geométrico, que duplica el tamaño del almacenamiento cuando está lleno, entonces el rendimiento amortizado global para enqueue() sigue siendo O(log N).

Ejercicios de Desafío

1. Es posible utilizar una matriz fija, storage, como estructura de datos para implementar eficientemente una cola, de forma que las operaciones enqueue() y dequeue()tengan un rendimiento O(1). Este enfoque se conoce como cola circular, que hace la novedosa sugerencia de que el primer valor de la matriz no siempre es storage[0]. En su lugar, lleva un registro de first, la posición del índice para el valor más antiguo de la cola, y last, la posición del índice donde se colocará el siguiente valor en cola, como se muestra en laFigura 4-20.

   

   Figura 4-20. Utilizar una matriz como cola circular

   A medida que coloques y retires valores de la cola, tendrás que manipularlos con cuidado. Te resultará útil llevar un registro de N, el número de valores que ya están en la cola. ¿Puedes completar la implementacióndel Listado 4-4 y validar que estas operaciones se completan en tiempo constante? Es de esperar que utilices el operador módulo % en tu código.

   Listado 4-4. Completa esta implementación Queue de una cola circular

   class Queue:
     def __init__(self, size):
       self.size = size
       self.storage = [None] * size
       self.first = 0
       self.last = 0
       self.N = 0
   
     def is_empty(self):
       return self.N == 0
   
     def is_full(self):
       return self.N == self.size
   
     def enqueue(self, item):
       """If not full, enqueue item in O(1) performance."""
   
     def dequeue(self):
       """If not empty, dequeue head in O(1) performance."""

2. Inserta N = 2^k - 1 elementos en orden ascendente en un montón binario máximo vacío de tamaño N. Cuando inspeccionas la matriz subyacente resultante (aparte de la posición de índice 0, que no se utiliza), ¿puedes predecir las posiciones de índice para los valores k más grandes de la matriz de almacenamiento? Si insertas N elementos en orden descendente en un montón máximo vacío, ¿puedes predecir las posiciones de índice de todos los N valores?

3. Dados dos montones máximos de tamaño M y N, diseña un algoritmo que devuelva un array de tamaño M + N que contenga los elementos combinados de M y N en orden ascendente con un rendimiento de O(M log M + N log N). Genera una tabla de rendimiento en tiempo de ejecución para aportar pruebas empíricas de que tu algoritmo funciona.

4. Utiliza un montón binario máximo para encontrar los k valores más pequeños de una colección de N elementos en O(N log k). Genera una tabla de rendimiento en tiempo de ejecución para aportar pruebas empíricas de que tu algoritmo funciona.

5. En un montón binario máximo, cada entrada padre tiene hasta dos hijos. Considera una estrategia alternativa, que llamaré montón factorial, en el que la entrada superior tiene dos hijos; cada uno de estos hijos tiene tres hijos (que llamaré nietos). Cada uno de estos nietos tiene cuatro hijos, y así sucesivamente, como se muestra en la Figura 4-21. En cada nivel sucesivo, las entradas tienen un hijo adicional. La forma del montón y la propiedad ordenado en el montón siguen vigentes. Completa la implementación almacenando el montón factorial en un array, y realiza una evaluación empírica para confirmar que los resultados son más lentos que el montón binario máximo. Clasificar el rendimiento en tiempo de ejecución es más complicado, pero deberías poder determinar que es O(log N/log(log N)).

   

   Figura 4-21. Una novedosa estructura factorial de montón

6. Utilizando la estrategia de redimensionamiento geométrico del Capítulo 3, amplía la implementación de PQde este capítulo para redimensionar automáticamente la matriz de almacenamiento duplicando su tamaño cuando esté llena y reduciéndolo a la mitad cuando esté ¼ llena.

7. Un iterador para una estructura de datos del montón basada en matrices debería producir los valores en el orden en que se pondrían en cola sin modificar la matriz subyacente (ya que un iterador no debería tener efectos secundarios). Sin embargo, esto no se puede conseguir fácilmente, ya que la retirada de valores de la cola modificaría la estructura del montón. Una solución es crear una función generadora deiterator(pq) que reciba una cola de prioridad, pq, y cree otra cola de prioridad pqit cuyos valores sean posiciones de índice en la matriz storage para pq, y cuyas prioridades sean iguales a las prioridades correspondientes a estos valores. pqit accede directamente a la matriz storage para pq para llevar la cuenta de las entradas a devolver sin alterar el contenido de storage.

   Completa la siguiente implementación, que comienza insertando enpqit la posición del índice, 1, que hace referencia a la pareja de pq con mayor prioridad. Completa el resto del bucle while:

   def iterator(pq):
     pqit = PQ(len(pq))
     pqit.enqueue(1, pq.storage[1].priority)
   
     while pqit:
       idx = pqit.dequeue()
       yield (pq.storage[idx].value, pq.storage[idx].priority)
   
       ...

   Mientras el pq original permanezca inalterado, este iterador proporcionará cada uno de los valores en orden de prioridad.