File de priorité et structure de tas

Considérons le tableau suivant, formé de {n=12} entiers :

v = [|6; 12; 8; 5; 13; 4; 9; 3; 14; 1; 15; 17|]

On le représente comme un « arbre binaire » : les éléments du tableau viennent occuper les différents noeuds de l’arbre (suivant les profondeurs croissantes, et de gauche à droite sur une profondeur donnée).

Le dernier niveau de profondeur est rempli partiellement (et les éléments qui y figurent occupent les noeuds les plus à gauche).

Figure du chapitre 5, page 4
  • Chaque noeud (sauf la racine de l’arbre) possède un unique parent, et chaque noeud possède 0, ou 1 ou 2 enfants. {|} {|}
  • Les enfants de {v_{i}} sont {v_{2i+1}} et {v_{2j+2}\quad ;} le parent de {v_{i}} est {v_{j}} avec {j=\frac{i-1}{2}.}
  • Si {n\ge1} est le nombre d’éléments du tableau et si {h} est la hauteur en arêtes de l’arbre associé au tas, alors {2^h\le n\lt 2^{h+1}}. Le nombre d’étages est {h+1}.
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :