Arbre enracinéEn théorie des graphes, un arbre enraciné ou une arborescence est un graphe acyclique orienté possédant une unique racine, et tel que tous les nœuds sauf la racine ont un unique parent. En informatique, c'est également une structure de données récursive utilisée pour représenter ce type de graphes. Dans un arbre, on distingue deux catégories d'éléments : les feuilles (ou nœuds externes), éléments ne possédant pas de fils dans l'arbre ; les nœuds internes, éléments possédant des fils (sous-branches).
Implicit data structureIn computer science, an implicit data structure or space-efficient data structure is a data structure that stores very little information other than the main or required data: a data structure that requires low overhead. They are called "implicit" because the position of the elements carries meaning and relationship between elements; this is contrasted with the use of pointers to give an explicit relationship between elements. Definitions of "low overhead" vary, but generally means constant overhead; in big O notation, O(1) overhead.
D-ary heapThe d-ary heap or d-heap is a priority queue data structure, a generalization of the binary heap in which the nodes have d children instead of 2. Thus, a binary heap is a 2-heap, and a ternary heap is a 3-heap. According to Tarjan and Jensen et al., d-ary heaps were invented by Donald B. Johnson in 1975. This data structure allows decrease priority operations to be performed more quickly than binary heaps, at the expense of slower delete minimum operations.
Standard Template LibraryLa Standard Template Library (STL) est une bibliothèque C++, normalisée par l'ISO (document ISO/CEI 14882) et mise en œuvre à l'aide des templates. Cette bibliothèque fournit : un ensemble de classes conteneurs, telles que les vecteurs (vector), les tableaux associatifs (map), les listes chaînées (list), qui peuvent être utilisées pour contenir n'importe quel type de données à condition qu'il supporte certaines opérations comme la copie et l'assignation. une abstraction des pointeurs : les itérateurs.
Tas binomialEn informatique, un tas binomial est une structure de données assez proche du tas binaire, mais qui permet aussi de fusionner deux tas rapidement. Ainsi, il supporte les opérations suivantes, toutes en O(log n) : insérer un nouvel élément au tas ; trouver l'élément de plus petite clé ; effacer du tas l'élément de plus petite clé ; diminuer la clé d'un élément donné ; effacer un élément donné du tas ; fusionner deux tas en un seul. Le tas binomial est donc une implémentation du type abstrait tas fusionnable, c'est-à-dire une permettant des opérations de fusion.
Rust (langage)Rust est un langage de programmation compilé multi-paradigme conçu et développé par Mozilla Research depuis 2010. Il a été conçu pour être « un langage fiable, concurrent, pratique », supportant les styles de programmation purement fonctionnel, modèle d'acteur, procédural, ainsi qu'orienté objet sous certains aspects. En 2020, ses domaines de prédilection sont la programmation système, les applications en ligne de commande, les applications Web via WebAssembly, les services réseaux et les systèmes embarqués.
Pairing heapA pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986. Pairing heaps are heap-ordered multiway tree structures, and can be considered simplified Fibonacci heaps. They are considered a "robust choice" for implementing such algorithms as Prim's MST algorithm, and support the following operations (assuming a min-heap): find-min: simply return the top element of the heap.
Algorithme de DijkstraEn théorie des graphes, l'algorithme de Dijkstra (prononcé ) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source vers tous les autres sommets dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre un sommet de départ et un sommet d'arrivée.
Algorithme de Primthumb|right|Arbre couvrant de poids minimum L'algorithme de Prim est un algorithme glouton qui calcule un arbre couvrant minimal dans un graphe connexe pondéré et non orienté. En d'autres termes, cet algorithme trouve un sous-ensemble d'arêtes formant un arbre sur l'ensemble des sommets du graphe initial et tel que la somme des poids de ces arêtes soit minimale. Si le graphe n'est pas connexe, alors l'algorithme détermine un arbre couvrant minimal d'une composante connexe du graphe.
Algorithme de sélectionEn algorithmique, un algorithme de sélection est une méthode ayant pour but de trouver le k-ième plus petit élément d'un ensemble d'objets (étant donné un ordre et un entier k). La question de la sélection est un problème essentiel en algorithmique, notamment dans la recherche du maximum, du minimum et de la médiane. Plusieurs algorithmes ont été proposés et plusieurs contextes ont été étudiés : algorithmes en ligne, complexité amortie, complexité en moyenne, ensemble d'objet particuliers etc.
