Algorithmes sur la fusion de deux tas

Question

Comme je le sais, il existe un tas binomial ou un tas appelé fusion, qui est utilisé pour fusionner deux tas. Ma question est la suivante: au lieu de fusionner ces tas de façon dynamique, si je copie ces deux tas dans un grand tableau et que je fais ensuite une procédure de construction de tas, est-ce que ce serait une bonne approche? Parce que je ne sais pas comment créer un tas en utilisant deux tas en utilisant simplement l'opération de tas. S'il vous plaît dites-moi si ce n'est pas un bon moyen, ou si vous le pouvez, s'il vous plaît donnez-moi un lien, où un tas binomial avec l'opération de fusion est mis en œuvre.

Answer 1

Si vous y réfléchissez, créer un tas en rejetant toutes les informations intégrées dans la commande des autres tas ne peut pas être optimal. Dans le pire des cas, vous devez ajouter tous les éléments dans le tas 2 à tas 1, et ce sera seulement la moitié du travail de création d'un tout nouveau tas à partir de zéro.

Mais en fait, vous pouvez faire façon mieux que cela. La fusion de deux tas bien formés n'implique pas plus que de trouver le point d'insertion de l'une des racines dans l'arbre de l'autre tas, et de l'insérer à ce point. Aucun travail supplémentaire n'est nécessaire, et vous n'avez pas fait plus de ln N de travail! Voir here pour l'algorithme détaillé.

Answer 2

Il résoudra le problème, et il vous donnera un tas correct - mais il ne sera pas efficace.

Création d'un tas [binaire] de n éléments à partir de zéro est O(n), tandis que merging 2 tas existants binomiale est O(logn).

Answer 3

Le processus de fusion de 2 binômes binomiaux est assez similaire à l'opération de fusion dans le tri par fusion. Si vous ne connaissez pas la procédure de fusion - heap, les étapes suivantes peuvent vous aider.

répétez les étapes 1 à 4 jusqu'à ce que l'un des tas est vide

1. Si les têtes (qui sont des arbres binomiaux) des 2 tas sont de même degré vous assigneront la tête du tas avec une plus grande clé comme l'enfant de l'enfant de la tête de tas avec plus petite clé. Par conséquent, le degré de la tête de ce dernier sera augmenté de 1 et fera de la tête du premier segment l'élément suivant de sa tête actuelle et passera à l'étape 2 sinon s'ils sont de degré différent, puis passera à l'étape 4

2. Si la tête et l'autre arbre binomial dans ce dernier tas à l'étape 1 sont de même degré, passez à l'étape 3 aller ailleurs à l'étape 1

3. Combine la tête et son élément suivant dans le tas, en de la même manière que vous l'avez fait à l'étape 1 et assignez le nouvel arbre binomial combiné comme tête et passez à l'étape 2.

4. Voyez lequel des 2 tas a la tête avec le degré le plus bas. Assigner la tête de ce tas comme la tête d'un autre tas et supprimer du tas où il était initialement présent

Answer 4

files d'attente Brodal et les files d'attente Brodal-Okasaki (bootstrapped tas binomial obliquité) donner les meilleures limites asymptotiques cas le plus défavorable pour les segments fusionnables, supportant O (1) insert, merge et findMin, et O (log n) deleteMin. Les files d'attente brodales sont éphémères et prennent en charge efficacement delete et declineKey. Les files d'attente Brodal-Okasaki sont persistantes (en fait purement fonctionnelles), mais ne supportent pas delete ou declineKey.Malheureusement, Brodal et Okasaki disent que ces deux implémentations sont inefficaces dans la pratique, et Brodal considère ses files d'attente trop compliquées pour être pratiques dans tous les cas.

Les amas de Fibonacci donnent des bornes amortie similaires (mais pas pires), et sont probablement plus efficaces et plus pratiques dans un contexte amorti. Le jumelage des tas est une autre bonne option: selon Wikipedia, leurs limites exactes sont inconnues, mais elles fonctionnent très bien dans la pratique.