Tas binaire

Résumé

En informatique, un tas binaire est une structure de données utilisée notamment pour implémenter une car elle permet de retirer l’élément de priorité maximale (resp. minimale) d'un ensemble ou d’insérer un élément dans l'ensemble en temps logarithmique tout en conservant la structure du tas binaire. On peut la représenter par un arbre binaire qui vérifie ces deux contraintes :

C'est un arbre binaire complet : tous les niveaux sauf le dernier doivent être totalement remplis et si le dernier ne l'est pas totalement, alors il doit être rempli de gauche à droite.
C'est un tas : l'étiquette (qu'on appelle aussi clé ou key) de chaque nœud doit être supérieure ou égale (resp. inférieure ou égale) aux étiquettes de chacun de ses fils (la signification de supérieur ou égal dépend de la relation d'ordre choisie).

Si la relation d'ordre choisie est "supérieure ou égale", on parle alors de tas-max (ou max-heap). Si la relation est "inférieure ou égale", on parle alors de tas-min (ou mi

Source officielle

https://fr.wikipedia.org/wiki/Tas_binaire

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (4)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (10)

Concepts associés

Chargement

Cours associés (2)

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, sorting and searching, and graph algorithms.

The aim of this course is to provide the background in scientific computing. The class includes a brief introduction to basic programming in c++, it then focus on object oriented programming and c++ specific programming techniques.

Cours associés

Chargement

Séances de cours associées (11)

Séances de cours associées

Chargement

Unsupervised Robust Nonparametric Learning Of Hidden Community Properties

Akhilesh Deepak Gotmare, Martin Jaggi, Mikhail Langovoy

We consider learning of fundamental properties of communities in large noisy networks, in the prototypical situation where the nodes or users are split into two classes according to a binary property, e.g., according to their opinions or preferences on a topic. For learning these properties, we propose a nonparametric, unsupervised, and scalable graph scan procedure that is, in addition, robust against a class of powerful adversaries. In our setup, one of the communities can fall under the influence of a knowledgeable adversarial leader, who knows the full network structure, has unlimited computational resources and can completely foresee our planned actions on the network. We prove strong consistency of our results in this setup with minimal assumptions. In particular, the learning procedure estimates the baseline activity of normal users asymptotically correctly with probability 1; the only assumption being the existence of a single implicit community of asymptotically negligible logarithmic size. We provide experiments on real and synthetic data to illustrate the performance of our method, including examples with adversaries.

2019

Chargement

Heterogeneous Gossip

Davide Frey, Rachid Guerraoui, Anne-Marie Kermarrec, Maxime Monod

Gossip-based information dissemination protocols are considered easy to deploy, scalable and resilient to network dynamics. Load-balancing is inherent in these protocols as the dissemination work is evenly spread among all nodes. Yet, large-scale distributed systems are usually heterogeneous with respect to network capabilities such as bandwidth. In practice, a blind load-balancing strategy might significantly hamper the performance of the gossip dissemination. This paper presents HEAP, HEterogeneity-Aware gossip Protocol, where nodes dynamically adapt their contribution to the gossip dissemination according to their bandwidth capabilities. Using a continuous, itself gossip-based, approximation of relative bandwidth capabilities, HEAP dynamically leverages the most capable nodes by increasing their fanout, while decreasing by the same proportion that of less capable nodes. HEAP preserves the simple and proactive (churn adaptation) nature of gossip, while significantly improving its effectiveness. We extensively evaluate HEAP in the context of a video streaming application on a testbed of 270 PlanetLab nodes. Our results show that HEAP significantly improves the quality of the streaming over standard homogeneous gossip protocols, especially when the stream rate is close to the average available bandwidth.

2009

Chargement

Gossiping Capabilities

Davide Frey, Rachid Guerraoui, Anne-Marie Kermarrec, Maxime Monod

Gossip-based protocols are now acknowledged as a sound basis to implement collaborative high-bandwidth content dissemination: content location is disseminated through gossip, the actual contents being subsequently pulled. In this paper, we present HEAP, HEterogeneity-Aware Gossip Protocol, where nodes dynamically adjust their contribution to gossip dissemination according to their capabilities. Using a continuous, itself gossip-based, approximation of relative capabilities, HEAP dynamically leverages the most capable nodes by (a) increasing their fanouts (while decreasing by the same proportion those of less capable nodes) and (b) employing them early in the dissemination chain. These, on the other hand, have an incentive to take on additional load as being first in the chain improves their perceived quality. A lightweight accountability mechanism is used to track selfish nodes that might declare a high capability in order to augment their perceived quality without contributing accordingly. We evaluate HEAP in the context of a video streaming application on a 236 PlanetLab nodes testbed. Our results shows that HEAP improves the quality of the streaming by 25% over a standard gossip protocol without impacting the average load or availability of the system.

2008

Chargement