LG

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
=====Sous forme d'arbre=====
[[https://people.ksp.sk/~kuko/gnarley-trees/|Gnarley trees]] : présente tous les types de stockage de données sous forme d'arbres. Un must. Le tout accompagné d'une [[https://github.com/kuk0/alg-vis|application]] de visualisation.

{{ doc:donnees:stockage:people.ksp.sk.web.tar.xz |Archive du site}}

{{ doc:donnees:stockage:algvis.jar |Archive de l'application}} avec le code du Apr 6, 2015.

{{ doc:donnees:stockage:alg-vis.tar.xz |Source}} (Apr 6, 2015).

Les avantages / inconvénients indiqués dans les tableaux sont par rapport à l'arbre présenté dans la ligne précédente.

====Dictionnaire trié====
Un dictionnaire permet l'insertion, la recherche, la modification et la suppression des données dans n'importe quel ordre. Le stockage est réalisé sous forme d'un arbre trié.

^ Type ^ Insertion et optimisation ^ Suppression ^ Commentaire ^
| Dictionnaire, Arbre binaire de recherche \\ {{:doc:donnees:stockage:1-dictionaries-1-binary_search_tree.png?200|arbre binaire de recherche}} | On descend à droite si plus grand, à gauche si plus petit. \\ On insère lorsque l'enfant n'existe pas. \\ __Complexité__ : entre $O(log(n))$ et $O(n)$ \\ {{:doc:donnees:stockage:1-dictionaries-1-binary_search_tree-2.png.png?200|}} | Si un seul enfant, on fait la liaison entre le père et l'enfant. \\ Si deux enfants, on remplace le nœud par l'enfant le plus gauche dans l'arbre de l'enfant à droite. \\ __Complexité__ : entre $O(log(n))$ et $O(n)$ \\ {{:doc:donnees:stockage:1-dictionaries-1-binary_search_tree-3.png?200|}} | Insertion et suppression simple à implémenter mais arbre peu équilibré. \\ [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.8991&rep=rep1&type=pdf|Source 1]], {{ doc:donnees:stockage:10.1.1.14.8991.pdf |Archive 1}}, [[http://cgm.cs.mcgill.ca/~reedbook/papers/2003_R_1.pdf|Source 2]], {{ doc:donnees:stockage:2003_r_1.pdf |Archive 2}}, [[http://www.jeffeppinger.com/jle/EppingerCACM83.pdf|Source 3]], {{ doc:donnees:stockage:eppingercacm83.pdf |Archive 3}} |
| Dictionnaire, Rotation \\ On se base sur un arbre existant. | On n'insère pas, on optimise seulement. On remonte d'un niveau le nœud choisi et le parent descend. \\ Soit 4 blocs : le nœud et son parent, un bloc par enfant du nœud et leur descendance, un bloc pour l'autre enfant du parent et sa descendance. \\ Le bloc du centre (lié au nœud montant) devient lié au parent (qui descend) et son niveau ne change donc pas. \\ Les deux blocs des extrémités ne changent pas de parent. Le bloc lié au parent descend avec lui et le bloc lié à l'enfant monte avec lui. \\ {{:doc:donnees:stockage:1-dictionaries-2-rotations.png?200|}} {{:doc:donnees:stockage:1-dictionaries-2-rotations-2.png?200|}} {{:doc:donnees:stockage:1-dictionaries-2-rotations-3.png?200|}} | - | L'objectif de cette opération est de réduire la hauteur de l'arbre. \\ [[http://www.cs.cmu.edu/~sleator/papers/rotation-distance.pdf|Source]], {{ doc:donnees:stockage:rotation-distance.pdf |Archive}} |
| Dictionnaire, AVL tree \\ Base : arbre binaire de recherche. \\ {{:doc:donnees:stockage:1-dictionaries-3-avl.png?200|ex}} | __Insertion__ : identique à l'arbre binaire de recherche. \\ __Optimisation__ : on remonte le chemin du nouveau nœud. À chaque nœud on calcule la différence de profondeur maximale entre les deux enfants. Si la différence est d'au moins de 2, on ne remonte plus. \\ Si le chemin du dessous est droite-droite ou gauche-gauche, on ne fait qu'une seule rotation entre le nœud et l'enfant. {{:doc:donnees:stockage:1-dictionaries-3-avl-2.png?200|}} \\ Si le chemin du dessous est gauche-droite ou droite-gauche, on fait deux rotations : le petit-enfant et l'enfant puis le nouveau enfant et le nœud. {{:doc:donnees:stockage:1-dictionaries-3-avl-3.png?200|}} \\ __Complexité__ : $O(log(n))$ | Identique à l'arbre binaire de recherche. \\ On applique les mêmes optimisations qu'en insertion depuis le nœud supprimé. \\ __Complexité__ : $O(log(n))$ | __Avantage__ : la disposition de l'arbre est optimal pour fonctionner en $O(log(n))$. \\ __Inconvénient__ : l'insertion est plus longue et nécessite soit de stocker constamment le nombre de niveaux maximum en dessous de chaque nœud soit de parcourir toute la descendance de chaque nœud du parcours du nouveau nœud. \\ [[https://www.youtube.com/playlist?list=PLmXKhU9FNesRRy20Hjr2GuQ7Y6wevfsc5|Source]], {{ doc:donnees:stockage:insertion_in_avl_tree_data_structure_part_6-gst_mo60wue.mp4?linkonly |Archive}} |
| Dictionnaire, 2-3 tree \\ Un nœud simple a 0 ou 2 enfants. Un nœud double a 0 ou 3 enfants.  \\ {{:doc:donnees:stockage:1-dictionaries-4-2-3-tree.png?200|}} | __Insertion__ : on descend à droite si plus grand, à gauche si plus petit, au milieu si entre deux. On insère dans le nœud existant qui n'a pas d'enfant, par ordre croissant. \\ __Optimisation__ : si le nœud possède 3 valeurs, on le sépare en 3 nœuds. Le nœud de gauche a comme enfants les valeurs inférieures au nœud du centre et le nœud de droite a comme enfants les valeurs supérieures au nœud du centre. Le nœud du centre est intégré au nœud parent. On recommence l'opération tant que le nœud parent a 3 valeurs. \\ __Complexité__ : $O(log(n))$ \\ {{:doc:donnees:stockage:1-dictionaries-4-2-3-tree-2.png?200|}} | Identique à l'arbre binaire de recherche. \\ Si on supprime la valeur à gauche du nœud, on parcourt l'arbre enfant du centre et non celui de droite. \\ Si un nœud se retrouve sans valeur, on récupère une valeur du parent et on fusion l'un des nœuds avec l'autre pour respecter le bon nombre d'enfants. \\ __Complexité__ en $O(log(n))$ \\ {{:doc:donnees:stockage:1-dictionaries-4-2-3-tree-3.png?200|}} | __Avantage__ : pas de stockage de données supplémentaire ou d'enfants à parcourir. Tous les nœuds les plus inférieurs ont le même niveau. \\ __Inconvénient__ : deux données à comparer par nœud à la place d'une seule. |
| Dictionnaire, 2-3-4-tree \\ cf. B-tree d'ordre 4 \\ {{:doc:donnees:stockage:1-dictionaries-5-2-3-4-tree.png?200|}} |  -  |  -  |  -  |
| Dictionnaire, B-tree \\ Entre $(B-1)/2$ et $B-1$ données par nœud. Jusqu'à B enfants. | __Insertion__ : on descend à droite si plus grand, à gauche si plus petit, au nœud entre deux valeurs sinon. On insère dans le nœud existant qui n'a pas d'enfant, par ordre croissant. \\ __Optimisation__ : si le nœud possède B valeurs, on le sépare en 3 nœuds. Le nœud de gauche a comme enfants les valeurs inférieures au nœud du centre et le nœud de droite a comme enfants les valeurs supérieures au nœud du centre. Le nœud du centre est intégré au nœud parent. On recommence l'opération tant que le nœud parent a B valeurs. | __Complexité__ en $O(log(n))$ \\ __Avantage__ :  pas vraiment sûr. Peut-être une implémentation parallèle CUDA avec B = 32. \\ [[http://infolab.usc.edu/csci585/Spring2010/den_ar/indexing.pdf|Source 1]], {{ doc:donnees:stockage:indexing.pdf |Archive 1}}, [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.3426&rep=rep1&type=pdf|Source 2]], {{ doc:donnees:stockage:10.1.1.45.3426.pdf |Archive 2}} | Représentation \\ {{:doc:donnees:stockage:1-dictionaries-6-b_tree.png?200|}} |
| Dictionnaire, Red-black tree \\ Base : arbre binaire de recherche. | __Insertion__ : on descend à droite si plus grand, à gauche si plus petit. \\ __Optimisation__ : 4 cas. Plusieurs cas successifs peuvent s'appliquer sur un même nœud puis on applique les cas sur le nœud parent jusqu'à la racine ou que les modifications s'arrêtent. \\ * Nœud racine rouge : il devient noir. \\ * Nœud père rouge et oncle rouge : le parent et l'oncle deviennent noir et le grand père devient rouge. \\ * Nœud père rouge et oncle noir ou absent avec le grand-père du même coté que le nœud par rapport au parent : Rotation entre le nœud et le parent. \\ * Nœud père rouge et oncle noir ou absent avec le grand-père du coté opposé au nœud par rapport au parent : Rotation entre le grand-père et le parent. \\ Une fois tout terminé, on colorise. | __Complexité__ en $O(log(n))$ \\ __Intérêt__ : amélioration de AVL tree, un seul bit de donnée supplémentaire est nécessaire. \\ [[https://www.youtube.com/watch?v=5IBxA-bZZH8|Source 1]] {{ doc:donnees:stockage:red-black_trees_in_5_minutes_insertions_strategy_-5ibxa-bzzh8.webm?linkonly |Archive 1}}, [[https://www.youtube.com/watch?v=A3JZinzkMpk|Source 2]] {{ doc:donnees:stockage:red-black_trees_in_5_minutes_insertions_examples_-a3jzinzkmpk.mp4?linkonly |Archive 2}}, [[https://www.cs.swarthmore.edu/~adanner/cs41/f08/LLRB.pdf|Source 3]], {{ doc:donnees:stockage:llrb.pdf |Archive 3}}, [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.9178&rep=rep1&type=pdf|Source 4]], {{ doc:donnees:stockage:10.1.1.136.9178.pdf |Archive 4}} | Représentation \\ {{:doc:donnees:stockage:1-dictionaries-7-red-black_tree.png?200|}} \\ Optimisation \\ {{:doc:donnees:stockage:1-dictionaries-7-red-black_tree-2.png?200|}} {{:doc:donnees:stockage:1-dictionaries-7-red-black_tree-3.png?200|}} {{:doc:donnees:stockage:1-dictionaries-7-red-black_tree-4.png?200|}} {{:doc:donnees:stockage:1-dictionaries-7-red-black_tree-5.png?200|}} {{:doc:donnees:stockage:1-dictionaries-7-red-black_tree-6.png?200|}} |
| Dictionnaire, AA tree \\ Base : arbre binaire de recherche. | __Insertion__ : on descend à droite si plus grand, à gauche si plus petit. Le nouveau nœud a un point de 1. \\ __Optimisation__ : \\ * Si le nœud a un enfant du coté opposé au parent et que l'enfant, le nœud et le parent ont le même point, on fait une rotation entre le nœud et le parent et on incrémente le poids du nœud. \\ * Si le nœud a un parent à droite avec le même poids, on fait une rotation entre le nœud et le parent. | __Complexité__ en $O(log(n))$ \\ __Intérêt__ : amélioration de Red-black tree avec un algorithme d'optimisation plus simple mais plus long et c'est un nombre qui est stocké à la place d'un seul bit. \\ [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.6192&rep=rep1&type=pdf|Source]], {{ doc:donnees:stockage:10.1.1.118.6192.pdf |Archive}} | Représentation \\ {{:doc:donnees:stockage:1-dictionaries-8-aa_tree.png?200|}} \\ Optimisation \\ {{:doc:donnees:stockage:1-dictionaries-8-aa_tree-2.png?200|}} |
| Dictionnaire, Scapegoat \\ Base : arbre binaire de recherche avec un cœf $0.5 \leqslant \alpha < 1$. | __Insertion__ : on descend à droite si plus grand, à gauche si plus petit. \\ __Optimisation__ : \\ * Une fois la nouvelle valeur insérée, on vérifie que la hauteur globale de l'arbre $h(T)$ (le nombre de liens entre le nœud racine et le nœud le plus bas) est $\leqslant$ à $ h_\alpha(n)$ $= \frac{log(n)}{log(1/\alpha)}$ avec n le nombre de nœuds de l'arbre entier. Le non respect de cette condition est nécessaire mais non suffisant pour réorganiser l'arbre. Ensuite, il faut trouver le premier nœud, en partant du nouveau nœud et en remontant jusqu'à la racine, qui ne respecte pas la condition de largeur du sous-arbre : $s(x) \leqslant \alpha \cdot s(x.parent)$ avec $s(x)$ le nombre de nœud dans le sous arbre ayant comme nœud racine $x$. Une fois trouvé, on réorganise le sous-arbre ayant comme nœud racine $x.parent$. \\ * On linéarise le sous-arbre. On prend le nœud racine et on fait une rotation depuis le nœud enfant gauche qui devient le nœud racine. Et on continue jusqu'à ce que le nœud racine n'ait plus d'enfant à gauche. On descend alors à droite et on recommence avec les enfants à gauche et ainsi de suite jusqu'à ce qu'il n'y ait plus d'enfant. \\ * On repart du nœud racine du sous-arbre et on fait une rotation avec le nœud enfant droit. On descend à droite du nouveau nœud racine et on fait une rotation avec le nœud enfant droit. On recommence à faire un rotation un nœud sur deux. Puis on repart du nœud racine et on recommence en faisant une rotation sur un nœud enfant à droite sur deux. On recommence jusqu'à ce que l'arbre soit équilibré. J'ai remarqué une particularité simple, on fait 2 fois moins de rotation à chaque passe (arrondi à l'entier inférieur) : si le sous-arbre a 30 nœuds, la première passe, on fait 15 rotations, la 2ème 7 rotations, la 3ème 3 et la 4ème 1. | __Complexité__ en $O(log(n))$ \\ __Avantage__ : recherche parfaitement en $O(log(n))$. \\ __Inconvénient__ : il faut trouver le $\alpha$ et l'insertion est lente car elle nécessite de fréquente reconstruction de l'arbre. \\ [[http://people.scs.carleton.ca/~maheshwa/Honor-Project/scapegoat.pdf|Source 1]], {{ doc:donnees:stockage:scapegoat.pdf |Archive 1}}, [[http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f07/Artikler/03/Galperin93.pdf|Source 2]], {{ doc:donnees:stockage:galperin93.pdf |Archive 2}}, [[http://www.geeksforgeeks.org/scapegoat-tree-set-1-introduction-insertion/|Source 3]], {{ :doc:donnees:stockage:scapegoat_tree_set_1_introduction_and_insertion_-_geeksforgeeks_2020-04-26_11_52_59_pm_.html |Archive 3}}, [[http://user.it.uu.se/~arnea/ps/gb.pdf|Source 4]], {{ doc:donnees:stockage:gb.pdf |Archive 4}}, [[http://user.it.uu.se/~arnea/ps/gbimpl.pdf|Source 5]], {{ doc:donnees:stockage:gbimpl.pdf |Archive 5}} | Représentation \\ {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree.png?200|}} \\ Optimisation 1 \\ {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-2.png?200|}} {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-3.png?200|}} {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-4.png?200|}} \\ Optimisation 2 \\ {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-5.png?200|}} {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-6.png?200|}} {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-7.png?200|}} {{:doc:donnees:stockage:1-dictionaries-11-scapegoat_tree-8.png?200|}} |
| Dictionnaire, Splay \\ Base : arbre binaire de recherche. | __Insertion__ : on descend à droite si plus grand, à gauche si plus petit. Mais on insère pas, on se base sur le nœud en fin de parcours pour l'optimisation. \\ __Optimisation__ : on remonte le nœud jusqu'en haut de l'arbre. Rotation selon 3 cas : \\ * Fils de la racine de l'arbre : rotation du nœud. \\ * Le grand-père est du même coté que le nœud par rapport au parent : rotation du nœud qui monte d'un cran puis rotation à nouveau du nœud qui monte encore d'un cran. \\ * Le grand-père est du coté opposé par rapport au parent : rotation du parent du nœud puis rotation du nœud. \\ Puis lier le nouveau nœud au nouveau nœud racine. | __Complexité__ en $O(log(n))$ \\ __Avantage__ : tri sans stocker la moindre information supplémentaire en se basant uniquement sur le père et le grand père. \\ __Inconvénient__ : nombreuses rotations et l'arbre n'est pas équilibré. | Représentation \\ {{:doc:donnees:stockage:1-dictionaries-12-splay_tree.png?200|}} \\ Optimisations \\ {{:doc:donnees:stockage:1-dictionaries-12-splay_tree-2.png?200|}}{{:doc:donnees:stockage:1-dictionaries-12-splay_tree-3.png?200|}}{{:doc:donnees:stockage:1-dictionaries-12-splay_tree-4.png?200|}}{{:doc:donnees:stockage:1-dictionaries-12-splay_tree-5.png?200|}} |
| Dictionnaire, Treap \\ Base : arbre binaire de recherche. | __Insertion__ : on descend à droite si plus grand, à gauche si plus petit. \\ __Optimisation__ : \\ Une fois le nœud inséré, on lui attribut un point aléatoire. On effectue des rotations successifs entre le nœud et le parent jusqu'à ce que le poids du nœud soit inférieur au point du nœud parent. | __Complexité__ entre $O(n)$ et $O(log(n))$ \\ __Avantage__ : Génération aléatoire. \\ [[https://faculty.washington.edu/aragon/pubs/rst96.pdf|Source 1]], {{ doc:donnees:stockage:rst96.pdf |Archive 1}}, [[https://cis.temple.edu/~wolfgang/cis551/martinez.pdf|Source 2]], {{ doc:donnees:stockage:martinez.pdf |Archive 2}} | Représentation \\ {{:doc:donnees:stockage:1-dictionaries-9-treap.png?200|}} |
| Dictionnaire, Skiplist \\ Base : tableaux de listes chaînées. | __Insertion__ : On parcourt la première liste jusqu'à ce que la valeur soit supérieure à la valeur suivante. On passe à la liste chainée en dessous et ainsi de suite jusqu'à la dernière liste chaînée. \\ __Optimisation__ : \\ Une fois la nouvelle valeur insérée, on prend une chance sur deux pour insérer la valeur dans la liste précédente. Puis on continue jusqu'à ce que la chance fasse que la valeur ne soit plus propagée à la liste chaînée précédente. | __Complexité__ entre $O(n)$ et $O(log(n))$ \\ __Avantage__ : Génération aléatoire. \\ __Inconvénient__ : nombreuse duplication de la donnée en mémoire. \\ [[http://web.cs.ucdavis.edu/~amenta/w04/skiplists.pdf|Source 1]], {{ doc:donnees:stockage:skiplists.pdf |Archive 1}}, [[http://drum.lib.umd.edu/bitstream/handle/1903/544/CS-TR-2286.1.pdf;jsessionid=EDF1149F468202365E4F6A98A2D975CC?sequence=2|Source 2]], {{ doc:donnees:stockage:cs-tr-2286.pdf |Archive 2}}, [[http://drum.lib.umd.edu/bitstream/handle/1903/542/CS-TR-2222.pdf?sequence=2|Source 3]], {{ doc:donnees:stockage:cs-tr-2222.pdf |Archive 3}}, [[http://www.ic.unicamp.br/~celio/peer2peer/skip-net-graph/deterministic-skip-lists-munro.pdf|Source 4]], {{ doc:donnees:stockage:deterministic-skip-lists-munro.pdf |Archive 4}}, [[http://luc.devroye.org/devroye_1992_a_limit_theory_for_random_skip_lists.pdf|Source 5]], {{ doc:donnees:stockage:devroye_1992_a_limit_theory_for_random_skip_lists.pdf |Archive 5}} | Représentation \\ {{:doc:donnees:stockage:1-dictionaries-10-skiplist.png?200|}} |

====File de priorité (Queue)====
===Stockage interne sous forme d'un tableau===
Principe [[https://www.cs.auckland.ac.nz/software/AlgAnim/heaps.html|Data Structures and Algorithms_ Heaps]] {{ :doc:donnees:stockage:data_structures_and_algorithms_heaps_2020-04-29_6_23_14_pm_.html |Archive du 1998 le 29/04/2020}}

{{:doc:donnees:stockage:heap5.gif|}}{{:doc:donnees:stockage:heap6.gif|}}

Tous les nœuds d'une rang horizontal doivent être remplis avant de passer au rang inférieur. Le rang en cours se remplit de gauche à droite sans laisser de nœud vide.

Cette structure de données a pour but d'avoir accès à 2 opérations : insertion avec priorité et récupérer la priorité la plus importante. Par contre, la fusion de deux files de priorité est $O(n)$.

Les deux files de priorité du tableau ci-dessous sont stockées sous forme compact en mémoire (tableau).
^ Type ^ Insertion ^ Commentaire ^ Exemple ^
| Heap \\ Une donnée par nœud. Jusqu'à deux enfants. | __Insertion__ : on insère le nœud à la suite de l'arbre. \\ __Optimisation__ : on remonte le nœud jusqu'à ce que la valeur du nœud parent soit supérieure. | [[http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/heaps.pdf|Source]], {{ doc:donnees:stockage:heaps.pdf |Archive}} | Représentation \\ {{:doc:donnees:stockage:2-priority_queues-1-heap.png?200|}} |
| d-ary heap \\ Une donnée par nœud. Jusqu'à d enfants. | Identique à Heap. \\ Aucun tri entre les enfants. | [[http://blog.mischel.com/2013/10/05/the-d-ary-heap/|Source]] {{ :doc:donnees:stockage:the_d-ary_heap_jim_s_random_notes_2020-04-29_6_38_57_pm_.html |Archive du 05/10/2013 le 29/04/2020}} | Représentation \\ {{:doc:donnees:stockage:2-priority_queues-2-d-ary_heap.png?200|}} |

===Stockage interne sous forme d'arbres===
__Inconvénient__ : stockage clairsemé en mémoire.
<WRAP center round tip 60%>
Pourtant, ils ont tous le nom ''heap'', il est possible de tout stocker sous forme d'une pile ?
</WRAP>

__Avantage__ : fusion de deux piles en $O(1)$.

^ Type ^ Insertion ^ Commentaire ^ Exemple ^
| Leftist heap \\ Une donnée par nœud. \\ Jusqu'à deux enfants. | __Insertion__ : on compare toujours avec le nœud enfant à droite. S'il est plus grand, on descend à droite. S'il est plus petit, on devient son parent et lui l'enfant à droite. \\ __Optimisation__ : pour chaque nœud du chemin d'insertion : \\ - on calcule le rang $R$ . C'est égal au $min(R(d);R(g))+1$ avec une valeur de $R$ égale 0 si le nœud enfant n'existe pas. \\ - si le nœud frère (à gauche) possède un rang plus petit, on inverse les deux nœuds. | [[http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/heaps.pdf|Source]], {{ doc:donnees:stockage:heaps.pdf |Archive}} | Représentation \\ {{:doc:donnees:stockage:3-meldable_priority_queues-1-leftist_heap.png?200|}} \\ Optimisation \\ {{:doc:donnees:stockage:3-meldable_priority_queues-1-leftist_heap-2.png?200|}} |
| Skew heap \\ Une donnée par nœud. \\ Jusqu'à deux enfants. | __Insertion__ : identique à Leftist heap. \\ __Optimisation__ : on part de la racine et on descend toujours à droite. Pour tous les nœuds du chemin, on inverse le nœud à droite et à gauche même si le frère n'existe pas. | __Avantage__ : pas de calcul de rang. \\ [[https://www.cs.cmu.edu/~sleator/papers/adjusting-heaps.pdf|Source 1]] {{ doc:donnees:stockage:adjusting-heaps.pdf |Archive 1}} [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.8717&rep=rep1&type=pdf|Source 2]] {{ doc:donnees:stockage:10.1.1.56.8717.pdf |Archive 2}} [[http://www.win.tue.nl/~berry/papers/lowskew.pdf|Source 3]] {{ doc:donnees:stockage:lowskew.pdf |Archive 3}} | Représentation \\ {{:doc:donnees:stockage:3-meldable_priority_queues-2-skew_heap.png?200|}} \\ Optimisation \\ {{:doc:donnees:stockage:3-meldable_priority_queues-2-skew_heap-2.png?200|}} |
| Pairing heap \\ Une donnée par nœud. \\ Infinité d'enfants. | __Insertion__ : si la valeur est supérieur à la racine, le nœud devient la nouvelle racine et la racine un enfant. Si la valeur est inférieur à la racine, on insère le nœud comme enfant de la racine. | __Avantage__ : insertion rapide. \\ [[http://www.cs.cmu.edu/afs/cs.cmu.edu/user/sleator/www/papers/pairing-heaps.pdf|Source 1]] {{ doc:donnees:stockage:pairing-heaps.pdf |Archive 1}} [[https://hal.inria.fr/file/index/docid/75954/filename/RR-0600.pdf|Source 2]] {{ doc:donnees:stockage:rr-0600.pdf |Archive 2}} [[http://people.mpi-inf.mpg.de/~pettie/papers/focs05.pdf|Source 3]] {{ doc:donnees:stockage:focs05.pdf |Archive 3}} [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.8788&rep=rep1&type=pdf|Source 4]] {{ doc:donnees:stockage:10.1.1.93.8788.pdf |Archive 4}} [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.53.5960&rep=rep1&type=pdf|Source 5]] {{ doc:donnees:stockage:10.1.1.53.5960.pdf |Archive 5}} | Représentation \\ {{:doc:donnees:stockage:3-meldable_priority_queues-3-pairing_heap.png?200|}} |
| Binomial heap \\ Une donnée par nœud. \\ Une infinité d'enfants. Seul le nœud racine peut avoir une infinité de frères. | __Insertion__ : la valeur est insérée comme frère aux nœuds racine avec un rang de 0. \\ __Optimisation__ : Seuls les nœuds du niveau racine ont un rang. Il correspond au nombre de fusion. Tant que deux nœuds racine ont le même rang, le nœud avec la plus petite valeur devient l'enfant de l'autre et celui qui reste au même niveau que les nœuds racine voit son rang incrémenter. | __Avantage__ : moins d'enfants. \\ [[http://www.cl.cam.ac.uk/teaching/1011/AlgorithII/1978-Vuillemin-queues.pdf|Source]], {{ doc:donnees:stockage:1978-vuillemin-queues.pdf |Archive}} | Représentation \\ {{:doc:donnees:stockage:3-meldable_priority_queues-4-binomial_heap.png?200|}} |
| Lazy binomial heap \\ Identique à Binomial heap. | __Insertion__ : la valeur est insérée comme frère aux nœuds racine. | __Avantage__ : insertion instantanée. \\ __Inconvénient__ : la génération de l'arbre Binomial se fait lors du dépilage. [[http://web.stanford.edu/class/archive/cs/cs166/cs166.1146/lectures/06/Small06.pdf|Source 1]] {{ doc:donnees:stockage:small06.pdf |Archive 1}} [[http://www.cs.columbia.edu/~gskc/Code/AdvancedDataStructures/LazyBinomialHeaps/lazyBinomialHeaps.c|Source 2]] {{ doc:donnees:stockage:lazybinomialheaps.c |Archive 2}} | Représentation \\ {{:doc:donnees:stockage:3-meldable_priority_queues-5-lazy_binomial_heap.png?200|}} |
| Fibonacci heap \\ Identique à Lazy binomial heap. | __Insertion__ : identique à Lazy binomial heap. | [[https://www.cs.princeton.edu/~wayne/teaching/fibonacci-heap.pdf|Source]], {{ doc:donnees:stockage:fibonacci-heap.pdf |Archive}} | Représentation \\ {{:doc:donnees:stockage:3-meldable_priority_queues-6-fibonacci_heap.png?200|}} |