BHeap: (tas binomial) ----- Impl�mentation: ~~~~~~~~~~~~~~ Ce code utilisant les classes, il ne peut marcher qu'en C++. Le tas binomial est une classe d�riv�e de la classe 'PriorityList'. Toutes les m�thodes �tant virtuelles, vous pouvez sans probl�me assigner un BHeap � une PriorityList et appeler les m�thodes classiques de la liste de priorit�. Utilisation: ~~~~~~~~~~~ Pour creer un tas binomial vide, il suffit de faire: BHeap * Tas = new BHeap; Il n'y a aucune variable de la structure BHeap lisible directement. Tout s'effectue par des appels aux m�thodes de la classe. Les donn�es satellites sont dispos�es dans la structure sous la forme d'un pointeur du type void. Le type des donn�es est d�finit par le typedef 'Datas_t'. Le type des clefs est d�finit par le typedef 'Key_t'. Par d�faut, ceux-ci sont: typedef Datas_t void * typedef Key_t int Vous pouvez changer ces typedefs avant de faire un #include <PCommon.h>. Le type changera alors automatiquement dans la compilation de la librairie. Attention: cela ne marchera bien �videmment qu'en compilation statique (c'est � dire avec le package PriorityList dans votre arbre de d�veloppement) et le type Key_t doit �tre un type 'comparable' (afin de faire les tests sur les clefs). Il est n�anmoins vivement conseill� de conserver les types de bases. Il n'y a aucun moyen direct de 'renverser' l'ordre de la liste (c'est � dire faire du plus grand au plus petit). Il vous suffit de faire des insertions sur les valeurs n�gatives des clefs r�elles � ins�rer. Voici les m�thodes disponibles: BHeap::BHeap(void); BHeap::~BHeap(void); Key_t PriorityList::ReadKey(void); Datas_t PriorityList::ReadDatas(void); void BHeap::Dump(void); BHeap * BHeap::Min(void); BHeap * BHeap::Insert(Key_t IKey, Datas_t IDatas); Key_t BHeap::Extract_Min(Datas_t & Datas); BHeap * BHeap::Union(PriorityList * H); int BHeap::Lower_Key(Key_t NKey); Key_t BHeap::Delete(Datas_t & Datas, PriorityList * x); Le constructeur est le constructeur 'tas vide'. Le destructeur ne peut que servir a d�truire un tas complet. Les deux m�thodes PriorityList::ReadKey et PriorityList::ReadDatas servent a lire les donn�es de la structure. Elles sont directement d�riv�es de PriorityList. La m�thode BHeap::Min recherche la clef minimum de la structure et en renvoie le pointeur correspondant. Elle s'utilise sur le tas dans lequel on recherche. La m�thode BHeap::Insert va inserer une nouvelle clef dans le tas sur lequel on a appel� la m�thode. La m�thode BHeap:Extract_Min va rechercher et supprimer le minimum dans le tas sur lequel elle a �t� appel�e. Elle renvoie la clef minimum. Les donn�es satellite sont �crites dans la variable Datas pass�e en param�tre. La m�thode BHeap::Union va vider compl�tement le tas pass� en param�tre pour effectuer l'op�ration Union avec le tas sur lequel la m�thode a �t� appel�e. La m�thode BHeap::Lower_Key va diminuer la valeur de la clef de la cellule sur laquelle la m�thode a �t� appel�e. Enfin la m�thode BHeap::Delete va effacer la clef pass�e en param�tre depuis le tas sur lequel la m�thode a �t� appel�e. Elle va renvoyer la valeur de la clef supprim�e et les donn�es satellites sont �crites dans la variable Datas. Pr�cautions: ~~~~~~~~~~~ Il ne faut *jamais* supprimer une clef directement avec la fonction C++ delete. Il faut toujours utiliser la m�thode BHeap::Delete(). Par contre pour effacer l'int�gralit� d'un tas, il suffit de faire delete Tas, et l'ensemble des clefs seront effac�es tr�s rapidement.