Déterminer si un nœud existe dans un Boost binomial_heap

Question

J'essaie de déterminer si un élément existe dans un fichier boost :: heap :: binomial_heap car j'ai besoin de savoir si je dois appeler update() (si le noeud existe déjà) ou push() (si le noeud n'existe pas). Certaines files d'attente fournissent une fonction push_or_update() dans ce but précis. La seule chose que je pourrais faire est de garder une carte de propriétés avec le même type d'index que les nœuds de la file d'attente et value_type 'handle_t'. Ensuite, je peux rechercher dans la carte si l'élément a un handle valide afin que je puisse pousser si ce n'est pas le cas, ou mettre à jour si c'est le cas.

Y a-t-il une meilleure façon de procéder?

Here is the doc for reference.

Answer 1

Ce n'est pas quelque chose qu'un tas binomial est censé faire.

Une manière habituelle de résoudre votre problème serait: utiliser une carte de hachage (ou toute autre structure de données que vous aimez) pour stocker un mappage entre les valeurs et handle s. Vous pouvez ensuite interroger la carte de hachage pour le handle. S'il existe, ce handle vous permettra de modifier la valeur dans le tas. S'il n'existe pas, vous pouvez simplement ajouter une nouvelle valeur au tas (bien sûr, et un nouveau mappage dans la table de hachage)

Une autre façon de résoudre le problème consiste à utiliser un ensemble d'arbres/une carte, qui est plus facile et peut être plus efficace que la solution que j'ai décrite ci-dessus, en fonction du cas d'utilisation réel.