11
Revisions sur les (min) Heaps (voir livre pp.312-318)
nRevisions: Un heap est un arbre binaire aux 3 proprietes suivantes:
nChaque noeud a une seule cle, et cette cle est plus large ou egale a la cle de son parent.
nL’arbre est complet, ce qui veut dire que toutes ses feuilles se trouvent sur deux niveaux au plus et que toutes les cles du niveau inferieur sont sur la gauche.
nLe heap peut etre mis en storage dans un tableau de facon a ce que la racine soit sauvegarde a la position 1 et que les enfants du noeud a la position i soient sauvegardes aux positions 2i et 2i+1. Inversement, l’index du parent du noeud j est floor(j/2).
n