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

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(\log n)$

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

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-keyinsert$O(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;
}