Comment implémenter l’opération de clé de réduction O (logn) pour la queue prioritaire basée sur min-tas?

Je travaille sur une application qui démontre l’ algorithme de Djikstra , et pour l’utiliser, je dois restaurer la propriété heap lorsque la valeur de mes éléments est réduite.

Le problème concernant la complexité est que lorsque l’algorithme modifie la valeur d’un élément, l’index de cet élément dans la structure interne (tas dans ce cas) utilisé pour la queue prioritaire est inconnu . En tant que tel, je dois actuellement effectuer une recherche O (n), afin de récupérer l’index, avant de pouvoir exécuter une clé de réduction réelle dessus.

De plus, je ne suis pas vraiment sûr du code réel nécessaire pour l’opération. J’utilise le D-Heap ici pour ma queue prioritaire. Le pseudocode aiderait, mais je préférerais un exemple en Java sur la façon dont cela devrait être fait.

Vous pouvez effectuer les opérations suivantes: stocker un hashmap dans votre segment de mémoire qui mappe vos valeurs de segment en index de segment de mémoire. Ensuite, vous devriez étendre un peu votre logique de tas habituelle:

on Swap(i, j): map[value[i]] = j; map[value[j]] = i; 

 on Insert(key, value): map.Add(value, heapSize) in the beginning; 

 on ExtractMin: map.Remove(extractedValue) in the end; 

 on UpdateKey(value, newKey): index = map[value]; keys[index] = newKey; 

BubbleUp(index) dans le cas de DecreaseKey et BubbleDown/Heapify(index) dans le cas de IncreaseKey , pour restaurer la propriété min-heap.

Voici mon implémentation C #: http://pastebin.com/kkZn123m

Insert et ExtractMin call Swap journaux (N) fois lors de la restauration de la propriété heap. Et vous ajoutez la surcharge O (1) à Swap, donc les deux opérations restnt O (log (n)). UpdateKey est aussi log (N): vous cherchez d’abord l’index dans un hashmap pour O (1), puis vous restaurez la propriété heap pour O (log (N)) comme vous le faites dans Insert / ExtractMin.

Remarque importante: l’utilisation de valeurs pour la recherche d’index nécessitera qu’elles soient UNIQUES. Si vous n’êtes pas d’accord avec cette condition, vous devrez append un identifiant unique à vos paires clé-valeur et maintenir le mappage entre cet identifiant unique et cet index de segment de mémoire au lieu du mappage d’index de valeur. Mais pour Dijkstra, ce n’est pas nécessaire, car vos valeurs seront des nœuds de graphe et vous ne voulez pas de nœuds dupliqués dans votre queue prioritaire.

Pour cette question SO, il est inutile d’avoir une méthode de clé décroissante pour implémenter l’algorithme de Dijkstra.

Vous pouvez simplement append un élément à la queue prioritaire autant de fois que nécessaire et garder une trace des nœuds visités pour éliminer les doublons. La première fois que vous visitez un nœud en l’extrayant de la queue, vous avez trouvé le chemin le plus court vers ce nœud et pouvez en ignorer toutes les occurrences futures dans la queue prioritaire.

Avoir plusieurs noeuds supplémentaires sur la queue prioritaire n’est pas un problème car c’est une structure O(log N) . (Vous devez effectuer environ 20 comparaisons pour 1 million d’articles et 30 comparaisons pour 1 milliard d’articles.)

Edit: Suite à cette question plus tard, je suis un peu déçu par ma réponse: toutes ces choses devront sortir de la queue à moins que vous ne fassiez plus tard des canipulations spéciales. Comme beaucoup de choses dans la vie, cela dépend de la façon dont vous gérez votre mémoire et des coûts associés. Mais le point général demeure: la clé décroissante n’est pas nécessaire , même si cela peut être souhaitable.

Si vous utilisez c ++ stl make_heap () / pop_heap () / push_heap (), il n’y a aucun moyen de conserver un index de l’ID de noeud à indexer dans le vecteur de segment de soulignement, je pense que vous devez implémenter vos propres fonctions logn) dans l’opération Increase-Key / Decrease-key.