Français
Menu

Qu'est-ce que Tas binaire (binary heap) ?

Arbre binaire complet dans lequel la valeur de chaque parent est supérieure ou égale (tas max) ou inférieure ou égale (tas min) à celles de ses enfants. Il peut être stocké dans un tableau : avec la racine en a[0], les enfants de a[i] sont a[2i+1] et a[2i+2]. La lecture du maximum (minimum) se fait en O(1), l'insertion et le retrait en O(log n) ; il sert aux files de priorité et au tri par tas.

Nom japonais: 二分ヒープ

« Tas binaire (binary heap) » apparaît dans 3 questions d'entraînement réparties sur 1 thèmes, dont Structures de données et algorithmes.

Domaine: Structures de données et algorithmes

S'entraîner : questions sur Tas binaire (binary heap)

Un tas binaire est stocké dans un tableau a[0], a[1], a[2], … avec la racine en a[0], en remplissant chaque niveau de gauche à droite à partir du haut. Quels sont les enfants et le parent de a[4] ?

  1. AEnfants a[9] et a[10] ; parent a[1]
  2. BEnfants a[8] et a[9] ; parent a[2]
  3. CEnfants a[9] et a[10] ; parent a[2]
Afficher la réponse et l'explication

Réponse : A. Enfants a[9] et a[10] ; parent a[1]

Avec la racine en a[0], les enfants de a[i] sont a[2i+1] et a[2i+2], et son parent est a[(i−1) ÷ 2, arrondi à l'entier inférieur]. Pour i = 4, les enfants sont a[9] et a[10], et le parent est a[(4−1) ÷ 2] = a[1]. Avec la racine en a[1], les enfants sont a[2i] et a[2i+1] et le parent est a[i ÷ 2] : il est donc important de vérifier quelle convention est utilisée. Comme un tas est un arbre binaire complet, il peut être stocké dans un tableau sans pointeurs, et les parents et les enfants se trouvent par simple calcul d'indices.

« Tas binaire (binary heap) » dans les explications

Questions mentionnant « Tas binaire (binary heap) » (3)

  1. Un tas binaire est stocké dans un tableau a[0], a[1], a[2], … avec la racine en a[0], en remplissant chaque niveau de gauche à droite à partir du haut. Quels sont les enfants et le parent de a[4] ?
  2. Quel algorithme de tri a une complexité temporelle en O(n log n) même dans le pire cas et trie presque sans mémoire supplémentaire, comme un tableau de travail ?
  3. Un tas max, dans lequel la valeur de chaque parent est supérieure ou égale à celles de ses enfants, est stocké dans un tableau avec la racine en a[0]. On ajoute 45 au tas 50, 30, 40, 10, 20, 35 en le plaçant à la fin, puis en l'échangeant avec son parent tant qu'il est plus grand que celui-ci. Quel est le tableau obtenu ?

Termes associés

Tableau Pointeur Complexité temporelle (notation grand O) File d'attente Algorithme de Dijkstra Algorithme glouton (greedy) Arbre binaire de recherche (binary search tree) Liste chaînée (linked list) Parcours en largeur (breadth-first search) Parcours en profondeur (depth-first search)

Retour au glossaire