Augmenter-clé et diminuer-clé dans un min-tas binaire

16

Dans de nombreuses discussions sur le tas binaire, seule la touche de diminution est normalement répertoriée comme opération prise en charge pour un tas min. Par exemple, CLR chapitre 6.1 et cette page wikipedia . Pourquoi la clé d'augmentation n'est-elle pas normalement répertoriée pour le segment de mémoire minimal? J'imagine qu'il est possible de le faire en O (hauteur) en échangeant de manière itérative l'élément augmenté (x) avec le minimum de ses enfants, jusqu'à ce qu'aucun de ses enfants ne soit plus grand que x.

par exemple

IncreaseKey(int pos, int newValue)
{
   heap[pos] = newValue;
   while(left(pos) < heap.Length)
   {
      int smallest = left(pos);
      if(heap[right(pos)] < heap[left(pos)])
         smallest = right(pos);
      if(heap[pos] < heap[smallest])
      { 
         swap(smallest, pos);
         pos= smallest;
      }
      else return;
   }   
}

Est-ce que ce qui précède est correct? Sinon, pourquoi? Si oui, pourquoi la clé d'augmentation n'est-elle pas répertoriée pour le segment de mémoire minimal?

GatotPujo
la source
1
Après avoir lu toutes les réponses, je dirais que c'est une étrange omission, probablement causée par la première utilisation historique de min-heap dans l'algorithme de Dijkstra.
maaartinus
3
Vous pouvez bien sûr toujours implémenter la clé d'augmentation en utilisant une suppression suivie d'une insertion, et la suppression elle-même peut être implémentée en tant que touche de diminution (à -∞) suivie de la suppression-min.
davmac
Le commentaire @maaartinus est la bonne réponse.
max

Réponses:

6

L'algorithme que vous proposez est simplement heapify. Et en effet - si vous augmentez la valeur d'un élément dans un min-heap, puis heapify son sous-arbre, alors vous vous retrouverez avec un min-heap légal.

Shaull
la source
alors pourquoi le CLR ou la liste Wikipedia n'augmentent-ils pas la clé pour être une opération prise en charge? Cela m'a un peu induit en erreur en pensant que ce n'est pas possible dans un tas de min
GatotPujo
Je suis d'accord que c'est trompeur, mais je ne vois aucune erreur dans l'algorithme.
Shaull
5

La raison pour laquelle votre opération n'est pas répertoriée est que l'on n'est pas simplement intéressé par toutes les opérations qui peuvent être facilement implémentées à l'aide d'une certaine structure de données, mais plutôt dans l'autre sens. Compte tenu d'un ensemble d'opérations, quel est le moyen le plus efficace (en termes d'espace et de temps) de mettre en œuvre ces opérations. (Mais j'en ajouterai plus tard)

Les segments binaires implémentent la file d'attente de priorité de la structure de données abstraite, qui demande les opérations is_empty, add_element (une clé avec sa priorité), find_min et delete_min. Des files d'attente plus avancées permettent également de diminuer la priorité de la clé (dans un min_heap) ou même de l'augmenter. En fait, vous avez donné une implémentation.

Deux remarques. Votre opération est utilisée dans la fonction heapify, qui construit efficacement un tas à partir d'un tableau. Dans heapify, votre opération est répétée (à partir de la dernière clé).

Ensuite, plus important encore, votre code utilise la position du nœud. Pour la file d'attente prioritaire de structure de données pure qui triche. Cette structure de données demande d'effectuer une certaine opération avec une clé. Donc, pour diminuer ou augmenter la priorité d'un élément, vous devrez d'abord le localiser. Je pense que c'est la principale raison pour laquelle il n'est pas répertorié.

Hendrik Jan
la source
1
Merci pour l'explication. Cependant, dans CLR, la touche de diminution a également la position comme nœud en tant que paramètre.
GatotPujo
Tu as raison. Je n'ai pas trouvé de raison de cette asymétrie dans la définition des files d'attente prioritaires dans la section 6.5 du CLRS. Remarque: la touche d'augmentation n'est pas utilisée dans Heapsort, l'application de ce chapitre. Il semble que l'asymétrie entre augmentation et diminution ne soit liée qu'à la façon dont la structure des données est utilisée, par exemple dans l'algorithme de Dijkstra. Là (en utilisant un min-tas), certains nœuds sélectionnés peuvent devenir plus urgents et sont déplacés vers le haut dans le tas.
Hendrik Jan
0

Je pense que la première chose à considérer est ce qu'est une opération prise en charge?

Est-ce que "l'insertion d'une valeur avec une clé fixe spécifique" (par exemple pour les clés extraites du domaine entier, l'insertion avec la clé = 3) correspond à une opération prise en charge pour le segment min?

Non, car cette opération peut être implémentée de manière triviale avec des opérations prises en charge plus générales. De même, l'insertion de 2 éléments à la fois peut être effectuée avec l' insertopération existante .

D'un autre côté, l' insertopération ne peut pas être définie autrement qu'en exposant les détails de l'implémentation. C'est à peu près la même chose pour les opérations répertoriées sur la page wikipedia, heapifysauf, qui pourraient probablement être implémentées par une séquence de insert.

En d'autres termes, il existe des opérations élémentaires fournies sur le type, qui sont étroitement liées aux détails de mise en œuvre pour qu'elles fonctionnent correctement, et il existe d'autres opérations, qui ne respectent pas cette règle, et peuvent donc être mises en œuvre en tant que combinaisons des canoniques.

Avec cette définition à l'esprit, pensez-vous que l'augmentation-clé pourrait être implémentée avec d'autres opérations prises en charge exclusivement, sans perte de performances? Si c'est le cas, alors ce n'est pas une opération prise en charge par la définition ci-dessus, sinon, vous pourriez bien avoir raison.

On peut dire que la définition d'une opération soutenue que je fournis est la mienne, pour autant que je sache. Ce n'est pas formel et donc sujet à discussion (même si cela me semble assez clair). Cependant, je serais heureux si quelqu'un pouvait fournir une source qui définisse clairement et sans ambiguïté ce qu'est une opération prise en charge pour les types de données, ou au moins la définit en de meilleurs termes que la mienne (cette définition est-elle donnée dans CLR? Je n'ai pas de copie ).

Mon deuxième point sera sur la façon dont nous définissons une file d'attente prioritaire (qui est la raison d'être des tas binaires). L' increase_keyopération est-elle nécessaire pour ce type de données, c'est-à-dire pour sa bonne utilisation?

Comme vous pouvez le voir, mon angle est axé sur les définitions. Je ne donne pas vraiment de réponse à vos questions, je me contente de quelques conseils, les améliorations sont donc les bienvenues.

didierc
la source
1
un exemple de cas d'utilisation peut être si je veux maintenir une file d'attente prioritaire d'objets basée sur les moins récemment utilisés (par exemple pour que je puisse supprimer facilement les objets les moins récemment utilisés). Je peux utiliser un min-tas avec la dernière date d'accès comme clé. Si un objet est accessible, sa clé devra être augmentée.
GatotPujo
Très bon point. Mon point de vue est un peu limité semble-t-il. Vraiment, la réponse @HendrikJan apporte une très bonne explication.
didierc