File d'attente prioritaire avec opérations de diminution et d'augmentation des clés

11

Un tas Fibonnaci prend en charge les opérations suivantes:

  • insert(key, data) : ajoute un nouvel élément à la structure des données
  • find-min() : renvoie un pointeur sur l'élément avec une clé minimale
  • delete-min() : supprime l'élément avec une clé minimale
  • delete(node) : supprime l'élément pointé par node
  • decrease-key(node) : diminue la clé de l'élément pointé par node

Toutes les opérations sans suppression sont en temps (amorti) et les opérations de suppression sont en temps O ( log n ) amorti.O(1)O(logn)

Existe-t-il des implémentations d'une file d'attente prioritaire qui prennent également en charge increase-key(node)en temps (amorti)?O(1)

Joe
la source
@Raphael si vous augmentez la clé de l'élément minimum pour qu'elle soit maintenant la plus grande clé, il n'est pas immédiatement évident (du moins pour moi) que vous n'avez pas à effectuer un rééquilibrage super constant.
Joe

Réponses:

10

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
la source
1
J'avais supposé que (de|in)crease-keyseulement plus ou moins un.
Raphael
Et existe-t-il un DS qui permet une opération d'augmentation des touches en temps constant mais une diminution du logarithmique (ou plus)? (Pour un tas)
Gonzalo Solera
2
@GonzaloSolera: La preuve d'impossibilité dans cette réponse ne se soucie pas de la clé de diminution; O (1) find-min, augmenter-clé et insérer sont déjà un problème ensemble (et la dépendance de la preuve sur l'insertion n'est pas vraiment nécessaire; O (n) heapify est suffisant, ou nous pouvons probablement réutiliser le même tas sur plusieurs pour prouver qu'il viole les limites de tri de la comparaison, quel que soit le coût de la segmentation ou de l'insertion).
user2357112 prend en charge Monica
D'accord, désolé, j'ai raté ça. Merci pour votre commentaire!
Gonzalo Solera