Kolejka priorytetowa z operacjami zmniejszania i zwiększania

Fibonnaci Heap obsługuje następujące operacje:

• insert(key, data) : dodaje nowy element do struktury danych
• find-min() : zwraca wskaźnik do elementu z minimalnym kluczem
• delete-min() : usuwa element z minimalnym kluczem
• delete(node) : usuwa element wskazany przez node
• decrease-key(node) : zmniejsza klucz wskazanego elementu node

Wszystkie operacje niezwiązane z usuwaniem mają czas (amortyzowany), a operacje usuwania to czas amortyzowany.$O(1)$$O(\log n)$

Czy istnieją implementacje priorytetową kolejce które również wsparcie increase-key(node)w (zamortyzowanego) czas?$O(1)$

Zakładam, że masz kolejkę priorytetową który ma , oraz . Poniżej znajduje się algorytm sortowania, który zajmuje czas:O ( n $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;
}