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?
algorithms
data-structures
heaps
priority-queues
GatotPujo
la source
la source
Réponses:
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.
la source
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é.
la source
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 deinsert.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.
la source