Cola prioritaria con operaciones de disminución de clave y aumento de clave

11

Un montón de Fibonnaci admite las siguientes operaciones:

  • insert(key, data) : agrega un nuevo elemento a la estructura de datos
  • find-min() : devuelve un puntero al elemento con clave mínima
  • delete-min() : elimina el elemento con clave mínima
  • delete(node) : elimina el elemento señalado por node
  • decrease-key(node) : disminuye la clave del elemento señalado por node

Todas las operaciones que no son de eliminación son tiempo (amortizado), y las operaciones de eliminación son tiempo amortizado.O(1)O(logn)

¿Hay implementaciones de una cola prioritaria que también sea compatible increase-key(node)con el tiempo (amortizado)?O(1)

Joe
fuente
@Raphael si aumentas la clave del elemento mínimo para que ahora sea la clave más grande, no es obvio de inmediato (al menos para mí) que no tienes que hacer una cantidad de reequilibrio súper constante.
Joe

Respuestas:

10

Suponga que tiene una cola de prioridad que tiene , y . Luego, el siguiente es un algoritmo de clasificación que toma tiempo :O(1) find-minincrease-keyinsertO(n)

vector<T>
fast_sort(const vector<T> & in) {
  vector<T> ans;
  pq<T> out;
  for (auto x : in) {
    out.insert(x);
  }
  for(auto x : in) {
    ans.push_back(*out.find_min());
    out.increase_key(out.find_min(), infinity);
  }
  return ans;
}
jbapple
fuente
1
Supuse que (de|in)crease-keysolo hacía más o menos uno.
Raphael
¿Y existe un DS que permita la operación de tecla de aumento en tiempo constante pero disminución en logarítmico (o más)? (Por un montón)
Gonzalo Solera
2
@GonzaloSolera: La prueba de imposibilidad en esta respuesta no se preocupa por la tecla de disminución; O (1) find-min, aumentar-clave e insertar ya son un problema juntos (y la dependencia de la prueba en la inserción no es realmente necesaria; O (n) heapify es suficiente, o probablemente podamos reutilizar el mismo montón en múltiples tipo para demostrar que viola los límites de clasificación de comparación independientemente del costo de heapify o insert).
user2357112 es compatible con Monica el
Ok, lo siento, me perdí leer eso. ¡Gracias por tu comentario!
Gonzalo Solera