¿Cómo implementarías una cola de prioridad acotada y estable?

1. Problema

Implementa StableBoundedPriorityQueue. Cada entrada tiene priority, sequence y value; compara primero priority y segundo sequence. Con capacidad C, push mantiene como máximo C entradas. Una nueva entrada reemplaza la peor entrada actual solo cuando es mejor; de lo contrario, se rechaza. pop devuelve la mejor entrada.

2. Restricciones y aclaraciones

• C es un entero positivo; con C=0, cada inserción se rechaza sin tocar el límite de un arreglo.
• Un número menor significa mayor prioridad; las prioridades iguales deben salir en orden de inserción.
• Rechazar el peor elemento cuando está llena requiere encontrar dicho elemento. Un único min-heap no puede exponerlo directamente en O(log C), por lo que se debe usar un segundo índice, un max-heap, o aceptar una búsqueda lineal.
• Comienza con una implementación de un solo hilo. Los productores y consumidores concurrentes necesitan un bloqueo externo o una cola concurrente dedicada.

3. Enfoque principal

Usa un min-heap para el siguiente elemento, ordenado por (priority, sequence). Usa un max-heap para el peor elemento, ordenado de modo que una prioridad mayor y una secuencia posterior sean peores. Ambos montículos apuntan al mismo registro de entrada. La eliminación marca una entrada como alive=false; cada montículo descarta los nodos muertos cuando llegan a su raíz. Esta eliminación perezosa evita la eliminación en posiciones arbitrarias del montículo.

Para capacidades pequeñas, una búsqueda lineal del peor elemento es más simple: pop sigue siendo O(log C), mientras que un push con la cola llena cuesta O(C). Menciona esta compensación antes de presentar la optimización de dos montículos.

4. Implementación de referencia

record Entry(priority, sequence, value, alive=true)

push(priority, value):
  if capacity == 0: return false
  candidate = Entry(priority, nextSequence(), value)
  if size < capacity:
    add candidate to minHeap and maxHeap
    size += 1
    return true
  discard dead nodes from maxHeap
  worst = maxHeap.peek()
  if (priority, candidate.sequence) >= (worst.priority, worst.sequence):
    return false
  worst.alive = false
  pop maxHeap
  add candidate to both heaps
  return true

pop():
  discard dead nodes from minHeap
  if minHeap is empty: return EMPTY
  entry = pop minHeap
  entry.alive = false
  size -= 1
  return entry.value

La clave del max-heap significa "mayor es peor": una prioridad mayor es peor, y para igual prioridad, una secuencia mayor es posterior y por lo tanto peor. Si un lenguaje no tiene max-heap, niega la clave o proporciona un comparador. nextSequence debe ser monótono; usa un entero amplio o reinícialo solo cuando la cola esté vacía.

5. Complejidad y compensaciones

Una inserción aceptada agrega un nodo a cada montículo, por lo que cuesta O(log C); pop cuesta O(log C). El reemplazo también es O(log C). La eliminación perezosa puede dejar nodos muertos temporalmente, pero cada nodo muerto se extrae una vez, lo que da operaciones de O(log C) amortizado y un espacio de O(C) con un incremento de factor constante. Una variante de búsqueda lineal usa menos espacio y código más corto, pero cuesta O(C) para una inserción con la cola llena.

6. Verificación y observabilidad

• Cubre C=0, C=1, una cola vacía, rechazos repetidos y reemplazos repetidos.
• Inserta varias entradas de igual prioridad y verifica el orden FIFO por secuencia.
• Prueba un candidato peor, igual y mejor frente a una cola llena; espera rechazo, rechazo y reemplazo.
• Compara trazas de operaciones aleatorias con un modelo de referencia que ordene todas las entradas activas por (priority, sequence) y las trunque a C.
• Registra la longitud de la cola, el recuento de rechazos y el recuento de limpieza de nodos perezosos. Una tasa de rechazo creciente puede activar una limitación ascendente o la descarga de carga.

7. Errores comunes

• Ordenar solo por prioridad, lo que pierde la estabilidad FIFO en caso de empates.
• Asumir que una prioridad numérica mayor es más importante sin confirmar la dirección.
• Extraer la raíz del montículo antes de la admisión, lo que descarta la mejor tarea cuando la cola está llena.
• No descartar los nodos muertos, por lo que peek devuelve una entrada ya reemplazada o cancelada.
• Usar marcas de tiempo de reloj de pared para los números de secuencia; el retroceso del reloj o inserciones en el mismo tic pueden romper FIFO.

8. Preguntas de seguimiento

¿Cómo aplicarías cuotas por inquilino?

Mantén un recuento y un límite para cada inquilino. Verifica tanto la capacidad global como la cuota del inquilino antes de la inserción, y cuenta los dos motivos de rechazo por separado para que los inquilinos con alta demanda sean visibles.

¿Cómo cancelarías o repriorizarías una entrada?

Asigna a cada entrada un ID y usa eliminación perezosa. La cancelación la marca como muerta; la repriorización crea una nueva entrada e invalida la anterior. Limpia los nodos muertos al consultar la raíz o al extraer, en lugar de eliminar posiciones arbitrarias del montículo.

¿Cuándo deberías usar una cola de prioridad concurrente de biblioteca?

Usa una implementación concurrente probada cuando múltiples hilos o procesos produzcan y consuman, se requieran esperas con bloqueo o los límites de memoria sean estrictos. Un diseño personalizado de dos montículos es apropiado solo con un límite claro de un solo hilo y un ciclo de vida comprobable.