+

+/* Define if using alloca.c. */

+#undef C_ALLOCA

+

+/* Define to empty if the keyword does not work. */

+#undef const

+

+/* Define to one of _getb67, GETB67, getb67 for Cray-2 and Cray-YMP systems.

+ This function is required for alloca.c support on those systems. */

+#undef CRAY_STACKSEG_END

+

+/* Define if you have alloca, as a function or macro. */

+#undef HAVE_ALLOCA

+

+/* Define if you have <alloca.h> and it should be used (not on Ultrix). */

+#undef HAVE_ALLOCA_H

+

+/* Define if you have a working `mmap' system call. */

+#undef HAVE_MMAP

+

+/* Define as __inline if that's what the C compiler calls it. */

+#undef inline

+

+/* Define to `long' if <sys/types.h> doesn't define. */

+#undef off_t

+

+/* Define if you need to in order for stat and other things to work. */

+#undef _POSIX_SOURCE

+

+/* Define to `unsigned' if <sys/types.h> doesn't define. */

+#undef size_t

+

+/* If using the C implementation of alloca, define if you know the

+ direction of stack growth for your system; otherwise it will be

+ automatically deduced at run-time.

+ STACK_DIRECTION > 0 => grows toward higher addresses

+ STACK_DIRECTION < 0 => grows toward lower addresses

+ STACK_DIRECTION = 0 => direction of growth unknown

+ */

+#undef STACK_DIRECTION

+

+/* Define if you have the ANSI C header files. */

+#undef STDC_HEADERS

+

+/* Define if your processor stores words with the most significant

+ byte first (like Motorola and SPARC, unlike Intel and VAX). */

+#undef WORDS_BIGENDIAN

+/* Define if you have the __argz_count function. */

+/* Define if you have the __argz_next function. */

+/* Define if you have the __argz_stringify function. */

+/* Define if you have the dcgettext function. */

+/* Define if you have the getcwd function. */

+/* Define if you have the getpagesize function. */

+/* Define if you have the getwd function. */

+/* Define if you have the munmap function. */

+/* Define if you have the putenv function. */

+/* Define if you have the setenv function. */

+/* Define if you have the setlocale function. */

+/* Define if you have the stpcpy function. */

+/* Define if you have the strcasecmp function. */

+/* Define if you have the strchr function. */

+/* Define if you have the strdup function. */

+/* Define if you have the <argz.h> header file. */

+#undef HAVE_ARGZ_H

+

+/* Define if you have the <fcntl.h> header file. */

+#undef HAVE_FCNTL_H

+

+/* Define if you have the <libintl.h> header file. */

+#undef HAVE_LIBINTL_H

+

+/* Define if you have the <limits.h> header file. */

+#undef HAVE_LIMITS_H

+

+/* Define if you have the <locale.h> header file. */

+#undef HAVE_LOCALE_H

+

+/* Define if you have the <malloc.h> header file. */

+#undef HAVE_MALLOC_H

+

+/* Define if you have the <nl_types.h> header file. */

+#undef HAVE_NL_TYPES_H

+

+/* Define if you have the <string.h> header file. */

+/* Define if you have the <strings.h> header file. */

+/* Define if you have the <sys/param.h> header file. */

+/* Define if you have the <unistd.h> header file. */

+/* Define if you have the i library (-li). */

+#undef HAVE_LIBI

+ps:

+ make -f Makefile.doc ps

+

+clean:

+ make -f Makefile.doc clean

+

+distclean:

+ make -f Makefile.doc clean

+

+EXTRA_DIST = algo.tex algorithmes.tex bib.tex conclusion.tex description.tex intro.tex manuel.tex outils.tex structures.tex temps.tex

+%initialisations----------------------------------------------------------------

+\documentclass[french,11pt,a4paper,twoside,openright]{report}

+\usepackage[T1]{fontenc}

+\usepackage[latin1]{inputenc}

+\usepackage[francais]{babel}

+\usepackage{a4}

+\usepackage{ulem}

+\usepackage{multirow}

+\usepackage[dvips]{graphics}

+\usepackage{vmargin}

+\usepackage{fancyhdr}

+\usepackage{oldstyle}

+\usepackage{listings}

+\usepackage{verbatim}

+%fin des initialisations--------------------------------------------------------

+

+\pagestyle{fancyplain}

+\addtolength{\headwidth}{\marginparsep}

+\addtolength{\headwidth}{\marginparwidth}

+% titre de chapitre

+\renewcommand{\chaptermark}[1]{\markboth{#1} {}}

+% titre de section

+\renewcommand{\sectionmark}[1]{\markright{\thesection\ #1}}

+

+\lhead[\fancyplain{}{\bfseries\textos{\thepage}}]{\fancyplain{}{\bfseries\rightmark}}

+\rhead[\fancyplain{}{\bfseries\leftmark}]{\fancyplain{}{\bfseries\textos{\thepage}}}

+\cfoot{\fancyplain{\textos{\thepage}}{}}

+

+\newcommand{\clearemptydoublepage}{\newpage{\pagestyle{empty}\cleardoublepage}}

+

+\def\addcontentsline#1#2#3{%

+ \addtocontents{#1}{\protect\contentsline{#2}{#3}{\textos{\thepage}}}}

+% \setmargrb{leftmargin}{topmargin}{rightmargin}{bottommargin}

+\setmargrb{1.5cm}{2cm}{1.5cm}{4cm}

+

+\begin{document}

+\renewcommand{\chaptername}{Section}

+\newcommand{\bracebits}{$\underbrace{\hspace{2cm}}$}

+

+%page de garde

+\title{Projet d'Algorithmique\\

+ Rapport \vspace{1.0cm}}

+\author{Barr�re Jordi, Noble Nicolas\vspace{2.0cm}}

+\date{\textit{derni�re r�vision: \today}}

+\maketitle

+\strut\thispagestyle{empty}

+\vfill

+\pagebreak

+\setcounter{page}{1}

+

+

+

+\tableofcontents

+

+\clearemptydoublepage

+

+\input{intro}

+\clearemptydoublepage

+\part{Analyse}

+\input{description}

+\clearemptydoublepage

+\input{structures}

+\clearemptydoublepage

+\input{algorithmes}

+\clearemptydoublepage

+\input{temps}

+\clearemptydoublepage

+\part{Synth�se}

+\input{manuel}

+\clearemptydoublepage

+\input{outils}

+\clearemptydoublepage

+

+\chapter{Code source}

+\lstset{language=C++,basicstyle=\scriptsize,stringspaces=false}

+\input{source}

+

+\clearemptydoublepage

+\input{conclusion}

+\clearemptydoublepage

+\input{bib}

+\clearpage

+\strut\thispagestyle{plain}

+\begin{tiny}

+\begin{center}

+Cette documentation a �t� r�alis�e sous Linux Slackware 7.1 � l'aide de \LaTeX\ et cvs.

+\end{center}

+\end{tiny}

+\end{document}

+\chapter{Algorithmes}

+\section{Tas Binomial}

+\paragraph{}

+L'impl�mentation de certaines parties des algorithmes sur les tas binomiaux ont n�cessit� quelques changements, notemment

+en ce qui concerne la gestion des cellules. En effet, il se pose un grave probl�me lors de l'impl�mentation de "DIMINUER-CL�",

+car nous effectuons des changements dans les cellules. Et si l'appelant a gard� des pointeurs sur les cellules elles-m�mes, alors

+leur contenu ne correspondra plus � la valeur d'insertion. Il faudrait pouvoir modifier aussi les pointeurs sur les cellules

+qui ont �t� renvoy�s � l'appelant, ce qui est impossible, vu que ces variables ne font pas partie de l'espace de donn�es de notre

+structure.

+\paragraph{}

+Pour r�soudre ce probl�me, nous avons une table de pointeurs "tampon" qui vont stoquer les vrais pointeurs sur

+les cellules du tas binomial. Comme ces pointeurs sont conserv�s dans la structure

+de donn�es, nous pouvons les modifier � loisir, lors d'une op�ration diminuer clef. Ainsi les pointeurs renvoy�s � l'appelant

+ne sont pas les pointeurs sur le tas directement, mais des pointeurs sur cette structure tampon, qui joue le role d'interm�diaire.

+\paragraph{}

+Cette structure est une liste doublement cha�n�e non tri�e (afin de pouvoir lib�rer la m�moire correctement

+� la fin du programme), et vu que les deux seules op�rations que nous effectuons dessus sont "INSERER" et "SUPPRIMER", nous ne

+faisons que des op�rations en $O(1)$ ce qui n'aura aucune influence sur le d�roulement des algorithmes eux-m�mes.

+\paragraph{}

+L'impl�mentation de l'algorithme "FUSIONNER-TAS-BINOMIAUX" a �t� r�alis� diff�remment de l'id�e du cormen. En effet, le livre

+sugg�rait de cr�er un troisi�me tas, et d'y placer les �l�ments de T1 et de T2 pour effacer T1 et T2 ensuite. Nous nous contentons

+d'effectuer une fusion "sur place". C'est � dire nous vidons le tas T2 et nous ins�rons ses �l�ments � la bonne place dans le tas

+T1. Ceci a pour but d'�viter la copie des cellules, pour la m�me raison que ci-dessus. Autant limiter les op�rations et nous

+contenter d'utiliser les blocs m�moires d�j� allou�s.

+\paragraph{}

+L'impl�mentation de l'algorithme "UNION" ne diff�re que tr�s l�g�rement de l'algorithme propos�, et nous obtenons un algorithme

+l�g�rement plus simple. En effet, dans l'algorithme propos�, nous avons un cas particulier dans le cas o� nos pointeurs se

+trouvent en d�but de liste. Nous r�solvons le probl�me directement car notre structure de donn�es est r�cursive et le tas est

+aussi une cellule de tas binomial. Ainsi, physiquement, nous ne commen�ons pas � la premi�re, mais � la deuxi�me cellule du tas.

+Le probl�me du cas particulier est donc r�gl�.

+\section{Tas de Fibonacci}

+\paragraph{}

+Le tas de Fibonacci, quique d'allure complexe, n'a pas pos� de probl�mes d'impl�mentations particuliers. La seule particularit�

+fut d'impl�menter certaines des phrases "en fran�ais dans le texte" telles que "parcourir la liste des pointeurs de base". Nous avons

+aussi invers� en g�n�ral l'ordre des choses lors de l'impl�mentation, ceci afin d'eviter de complexifier le code C++. En effet,

+deux op�rations cons�cutives peuvent influencer l'une sur l'autre, et mener � des situations de programmation d�licates. Les

+inverser peut pr�senter un aventage d'un point de vue conception, et n'influencer en rien le d�roulement de l'algorithme. Le code

+source des tas de Fibonacci est comment� de mani�re � pouvoir suivre les changements effectu�s lors de l'impl�mentation.

+\paragraph{}

+La seule restriction que nous avons pos� fut sur l'algorithme "CONSOLIDER" pour lequel le tableau A poss�de une taille fixe.

+En effet, nous ne pouvons �valuer � l'avance le nombre de case dont nous aurons besoin, sachant que certaines branches du

+tas peuvent �tre d�g�n�r�es.

+\section{Liste cha�n�e tri�e}

+\paragraph{}

+Cette impl�mentation n'a pos� aucun probl�mes particuliers, la structure �tant extr�mement simple. La seule particularit� qu'il

+peut �tre amusant de souligner, est que l'algorithme "UNION" est en fait la partie "FUSION" de l'algorithme de tri fusion.

+\section{Tas Binaire}

+\paragraph{}

+Comme pour le tas binomial, les cellules pouvant �tre �chang�es, nous ne pouvons renvoyer directement de pointeur sur le

+tableau lui-m�me. De ce fait, nous avons utilis� exactement la m�me structure "tampon" que pour le tas binomial.

+\paragraph{}

+Le tableau dans lequel nous stoquons les valeurs n'est en aucun cas limit� en revanche. Nous avons inclus un m�canisme qui

+va redimentionner le tableau automatiquement en fonction des indices demand�s, ce qui nous permet d'effectuer des tests

+comme si la structure avait une dimension infinie.

+\paragraph{}

+Le reste de l'impl�mentation n'a pos� aucun probl�me. Il est � noter en revanche qu'il a fallu inverser les conditions par rapport

+� ce qui est d�crit dans le livre. En effet, le tas binaire du livre nous donne une structure permettant d'effectuer "EXTRAIRE-MAX".

+\begin{thebibliography}{WWW99}

+% pour citer le Tanenbaum : \cite{Tanenbaum}

+% pour citer le Tanenbaum page 238 : \cite[page 238]{Tanenbaum}

+

+\bibitem[COR]{Cormen} T. Cormen, C. Leiserson, R. Rivest \textit{Introduction � l'algorithmique}, Dunod.

+

+\end{thebibliography}

+\chapter*{Conclusion}

+\addcontentsline{toc}{chapter}{Conclusion}

+\markboth{CONCLUSION}{CONCLUSION}

+

+Ce projet a �t� men� � terme, et l'ensemble des conditions du sujet ont �t� respect�es.

+L'effort de recherche men� sur la mani�re d'impl�menter les algorithmes en C++ a

+sans aucun doute �t� profitable pour notre connaissance personnelle. De plus, les algorithmes

+impl�ment�s sont "durables": ils peuvent nous resservir dans n'importe quel autre projet n�cessitant

+des structures de files de priorit�s, ce qui porte un int�r�t quant au d�veloppement de ce projet.

+\chapter{Description}

+\paragraph{}

+Nous allons d�crire dans cette premi�re partie tous ce que nous avons effectu� comme travail de r�flexion afin de

+programme ce projet. Il y a beaucoup de d�tails relatifs � l'impl�mentation dont nous ne parlerons pas, comme les structures

+sur les listes cha�n�es, ou l'initialisation du terminal pour g�rer le menu du programme de test. En revanche, nous appuyerons

+sur les d�tails d'impl�mentation purement algorithmiques qui nous ont pos� probl�me.

+\paragraph{}

+En ce qui concerne le langage de programmation, nous avons choisi le C++, car c'est le langage qui nous semblait le plus

+adapt� pour cr�er les structures de donn�es n�cessaire � la programmation de ce projet.

+\paragraph{}

+Nous avons impl�ment� les algorithmes de files de priorit�s suivants:

+\begin{itemize}

+\item Tas Binaire

+\item Tas Binomial

+\item Tas de Fibonacci

+\item Liste cha�n�e tri�e

+\end{itemize}

+\paragraph{}

+L'algorithme utilisant les files de priorit� impl�ment� est l'algorithme de compression de dictionnaire Huffman.

+\chapter*{Introduction}

+\addcontentsline{toc}{chapter}{Introduction}

+\markboth{INTRODUCTION}{INTRODUCTION}

+

+\paragraph{}

+Ce projet a pour but d'une part l'impl�mentation d'algorithmes de files de priorit�s et l'impl�mentation d'un algorithme

+utilisant ces files de priorit�s d'autre part.

+

+\paragraph{}

+Ce pr�sent document va tenter de d�crire en totalit� la progression de la

+mise en forme de ce projet. Nous vous souhaitons bonne lecture.

+\chapter{Manuel d'utilisation}

+\paragraph{}

+Ce projet g�n�re deux binaire. Le premier appel� testTas n'est qu'une petite application nous permettant d'utiliser l'API

+C++ g�n�r�e par notre classe de file de priorit�s. Voici un exemple d'ex�cution:

+\begin{verbatim}

+Priority list type: 0 - Binary Heap

+Choice: Please select an action

+a - Add a key into the priority list

+c - Change priority list type

+d - Delete a Key from the priority list

+e - Extract Min onto the priority list

+l - Lower Key onto a key of the priority list

+p - Print the current priority list on the screen

+r - Remove the whole priority list

+t - Test the priority list algorithms

+q - Quit

+\end{verbatim}

+

+A partir de cet instant, le programme nous propose un menu nous permettant d'effectuer plusieurs actions sur le tas. La

+fonction 'a' permet d'ajouter une clef dans le tas en cours. Comme il est impossible d'effectuer une recherche sur un tas

+pour y retrouver le pointeur d'un �l�ment, le programme nous propose de sauvegarder le pointeur r�sultat dans un tableau:

+

+\begin{verbatim}

+Choice: Please select a slot to save the cell

+0 - Empty slot

+1 - Empty slot

+2 - Empty slot

+3 - Empty slot

+4 - Empty slot

+5 - Empty slot

+6 - Empty slot

+7 - Empty slot

+8 - Empty slot

+9 - Empty slot

+n - Don't store

+c - Cancel

+\end{verbatim}

+

+Ce tableau apparaitra r�guli�rement dans toutes les fonctions du menu afin de choisir une cellule sur laquelle agir. Toutes

+les fonctions du menu parlent d'elles m�mes. La fonction 't' va lancer une batterie de tests sur les algorithmes de la

+file de priorit� s�lectionn�e.

+

+\paragraph{}

+Le deuxi�me binaire g�n�r� est 'Huffman'. Il sert � utiliser l'algorithme d'huffman impl�ment�. Voici sa ligne d'aide:

+\begin{verbatim}

+$ ./Huffman -h

+Huffman [{-f|-i} file] {type}

+Huffman -h

+This will encode the input file with the Huffman code

+using the priority list defined by type.

+Type is a number taken from this list:

+ 0 : Binary Heap (default)

+ 1 : Binomial Heap

+ 2 : Fibonacci Heap

+ 3 : Sorted chained list

+-f file means that you specify a dictionnary file which is

+ structured as described into the README file.

+-i file means that you specify a file to encode. It will

+ built a quiet dumb dictionnary.

+By default, a dictionnary will be built from stdin.

+-h prints this help and exit.

+\end{verbatim}

+

+La structure d'un dictionnaire est la suivante:

+\begin{verbatim}

+Mot1 : Fr�quence1

+Mot2 : Fr�quence2

+...

+\end{verbatim}

+

+Chaque mot est une cha�ne de caract�res servant � identifier la fr�quence associ�e. Voici un exemple complet de dictionnaire

+et d'utilisation du programme avec ce dictionnaire:

+

+\begin{verbatim}

+Pixel@the-babel-tower:~/Projets_LI/Semestre1/Projet-Algo/src$ cat dict.sample

+MOT1 : 2000

+MOT2 : 1234

+MOT3 : 15987

+MOT4 : 1203

+MOT5 : 192837

+MOT6 : 12987

+Pixel@the-babel-tower:~/Projets_LI/Semestre1/Projet-Algo/src$ ./Huffman -f dict.sample

+MOT3 (15987) = 00

+MOT1 (2000) = 0100

+MOT4 (1203) = 01010

+MOT2 (1234) = 01011

+MOT6 (12987) = 011

+MOT5 (192837) = 1

+Bitstream length : 283957 bits (= 35495 bytes)

+Real size input : 7239936 bits (= 904992 bytes)

+Size squeezed by : 96.0779 percents

+Dictionnary size : 336 bits (= 42 bytes)

+Total bitstream length : 284293 bits (= 35537 bytes)

+Real gain (4 bytes header) : 96.0728 percents

+\end{verbatim}

+

+Il est indiqu� que le programme est capable de g�n�rer un dictionnaire � partir d'un fichier. Il s'agit simplement de compter

+les caract�res provenant de l'entr�e et d'en g�n�rer un dictionnaire. Exemple:

+

+\begin{verbatim}

+$ cat dict.sample | Huffman

+\32 (12) = 00

+6 (1) = 01000

+4 (2) = 01001

+3 (4) = 0101

+0 (4) = 0110

+5 (2) = 01110

+7 (3) = 01111

+1 (6) = 1000

+M (6) = 1001

+: (6) = 1010

+\10 (6) = 1011

+O (6) = 1100

+8 (3) = 11010

+9 (3) = 11011

+2 (6) = 1110

+T (6) = 1111

+Bitstream length : 294 bits (= 37 bytes)

+Real size input : 608 bits (= 76 bytes)

+Size squeezed by : 51.6447 percents

+Dictionnary size : 512 bits (= 64 bytes)

+Total bitstream length : 806 bits (= 101 bytes)

+Real gain (4 bytes header) : -38.1579 percents

+\end{verbatim}

+\chapter{Outils utilis�s}

+\paragraph{}

+Pour d�velopper ce projet, nous avons choisi d'utiliser une s�rie d'outils GNU pour nous simplifier la t�che.

+Nous utilisons entre-autres, GNU autoconf \& automake pour g�rer notre arborescence de d�veloppement. Ainsi le

+pr�sent projet est d�coup� en ces r�pertoires:

+\begin{itemize}

+\item src contenant les sources des programmes ex�cutables. C'est notemment dans ce r�pertoire que seront stoqu�s

+les binaires des ex�cutables produit par la compilation du projet.

+\item lib contenant tous les sources purement algorithmiques, dont ne d�pend pas l'impl�mentation finale.

+\item include contenant tous les fichiers .h

+\item doc contenant le source \LaTeX\ de cette pr�sente documentation

+\item po contenant les fichiers d'internationalisation (traduction fran�aise)

+\item intl contenant le code source n�cessaire au support de l'internationalisation.

+\end{itemize}

+En dehors de autoconf \& automake, nous avons utilis� un serveur CVS (Concurrent Version System) qui nous a permis

+de travailler � plusieurs sur ce projet, sans avoir � nous soucier de rapatrier et de fusionner les codes sources

+de tout le monde.

+\paragraph{}

+Enfin, pour pouvoir compiler ce projet, il suffit de taper la commande './configure' au shell et de suivre les instructions.

+Les binaires seront plac�s dans le r�pertoire src. Pour g�n�rer cette documentation, il suffit d'aller dans le r�pertoire doc

+et de taper 'make ps'.

+\chapter{Structures de donn�es}

+\section{Files de priorit�s}

+Pour l'impl�mentation des files de priorit�s, nous avons remarqu� que, comme pour des arbres ou des listes

+cha�n�es, la structure est (dans le cas des tas Binomiaux et des tas de Fibonacci) r�cursive. Nous avons donc

+choisi comme structure de donn�es de base C++ une classe r�cursive. Qu'importe si les informations de r�cursivit�s

+ne sont pas utilis�s dans les autres d�riv�s de file de priorit�. La classe impl�ment�e est la suivante:

+

+\begin{lstlisting}{}

+class PriorityList {

+ protected:

+ class GeneralException;

+ int type;

+ Key_t Key;

+ Datas_t Datas;

+ PriorityList(Key_t IKey, Datas_t const &IDatas);

+

+ public:

+ PriorityList(void);

+ virtual ~ PriorityList(void);

+

+ virtual Key_t ReadKey(Cell C);

+ virtual Datas_t ReadDatas(Cell C);

+ virtual int n(void);

+ virtual int rn(void) = 0;

+

+ virtual void Dump(ostream & os) = 0;

+ virtual bool IsEmpty(void) = 0;

+

+ virtual Cell Min(void) = 0;

+ virtual Cell Insert(Key_t IKey, Datas_t const &IDatas) = 0;

+ virtual Key_t Extract_Min(Datas_t & Datas) = 0;

+ virtual PriorityList *Union(PriorityList * P) = 0;

+ virtual bool Lower_Key(Cell x, Key_t NKey) = 0;

+ virtual Key_t Delete(Datas_t & Datas, Cell x) = 0;

+ PriorityList *GenericUnion(PriorityList * P);

+ int GetType(void);

+};

+\end{lstlisting}

+

+Les types Key\_t, Datas\_t et Cell sont d�finis dans un include, et n'influencent en rien le comportement des algorithmes.

+Il suffit que Key\_t soit un type "comparable" (nous avons mis int), et que Datas\_t et Cell soient capables de v�hiculer

+des informations. Pour ces deux derniers types, nous avons mis void *. A partir de cette classe de base, nous allons

+d�river toutes les classes suivantes pour permettre l'impl�mentation des files de priorit�s.

+

+\section{Huffman}

+Pour l'impl�mentation de l'algorithme de Huffman, nous avons eu besoin d'�crire une petite structure d'arbre toute simple:

+

+\begin{lstlisting}{}

+class HTree {

+ private:

+ HTree * left, *right;

+ int freq;

+ char *objet;

+ public:

+ HTree(int n_freq, char *n_objet);

+ HTree(HTree * n_left, HTree * n_right);

+ ~HTree();

+ ostream & Trace(ostream & os, int d = 0);

+ int ReadFreq(void);

+ char *ReadObj(void);

+};

+\end{lstlisting}

+

+Notez au passage que la sturcture de donn�es poss�de une fonction "trace" qui nous sert � g�n�rer visuellement le r�sultat de la compression.

+\chapter{Analyse de temps}

+\paragraph{}

+L'analyse de temps n'est pas tr�s difficile. En effet les diff�rents temps sont d�j� calcul�s pour ce qui est des

+tas Binomiaux, des tas de Fibonacci et des tas binaires. Nous pr�senterons aussi les temps pour les files de priorit�s.

+Voici donc les diff�rents temps n�cessaires pour les op�rations de bases pour tous les algorithmes:

+\paragraph{}

+\begin{center}

+\begin{tabular}{lcccc}

+Proc�dure & Tas binaire & Tas binomial & Tas de Fibonacci & Liste cha�n�e tri�e\\

+\hline\\

+\textsc{Cr�er-Tas} & $\Theta(1)$ & $\Theta(1)$ & $\Theta(1)$ & $\Theta(1)$\\

+\textsc{Ins�rer} & $\Theta(\lg n)$ & $O(\lg n)$ & $\Theta(1)$ & $O(n)$\\

+\textsc{Minimum} & $\Theta(1)$ & $O(\lg n)$ & $\Theta(1)$ & $\Theta(1)$\\

+\textsc{Extraire-Min} & $\Theta(\lg n)$ & $\Theta(\lg n)$ & $O(\lg n)$ & $\Theta(1)$\\

+\textsc{Union} & $\Theta(n)$ & $O(\lg n)$ & $\Theta(1)$ & $O(n)$\\

+\textsc{Diminuer-Cl�} & $\Theta(\lg n)$ & $\Theta(\lg n)$ & $\Theta(1)$ & $O(n)$\\

+\textsc{Supprimer} & $\Theta(\lg n)$ & $\Theta(\lg n)$ & $O(\lg n)$ & $\Theta(1)$\\

+\end{tabular}

+\end{center}

+\paragraph{}

+Les temps de la liste cha�n�e tri�e sont simples � analyser et � expliquer. La liste �tant tri�e et doublement cha�n�e,

+les op�rations MINIMUM, EXTRAIRE-MIN, et SUPPRIMER sont directes, donc en $\Theta(1)$. Ensuite, l'insertion doit trouver

+le bon emplacement, donc parcourir au pire toute la liste cha�n�e afin d'effectuer l'insertion. C'est pourquoi l'op�ration

+UNION est en $O(n)$. De m�me, l'op�ration DIMINUER-CLE va effectuer l'op�ration inverser, et d�placer l'�l�ment vers la

+gauche jusqu'� trouver sa nouvelle place, donc au pire va parcourir toute la liste. Ce qui nous fait des op�rations en $O(n)$.

+Enfin, l'op�ration UNION est l'impl�mentation de l'algorithme FUSIONNER du tri fusion. Nous avons donc un temps en $O(n)$ aussi.

+ * r�cursivement.

+"POT-Creation-Date: 2001-04-17 23:50+0200\n"

+"POT-Creation-Date: 2001-03-22 13:52+0100\n"

+#: lib/BinHeap.cc:133

+#: lib/BinHeap.cc:163

+"POT-Creation-Date: 2001-03-22 13:52+0100\n"

+#: lib/BinHeap.cc:133

+#: lib/BinHeap.cc:163