Tas binomiaux
par Samuel Mimram

Votre opinion sur le cours de ce matin : Votre opinion sur le TD de la semaine dernière :

On rappelle qu'une file est une structure de données dans laquelle on peut mettre des éléments et en prendre, de sorte que les éléments pris le sont dans l'ordre dans lequel ils ont été mis (premier entré premier sorti). On rappelle aussi qu'un tas est un arbre dans lequel les clefs croissent le long des branches, c'est-à-dire que la clef d'un nœud est toujours inférieure ou égale à la clef de chacun de ses fils. Ici, une clef est un entier, qui représente une priorité.

L'objectif de ce TD est d'implémenter les tas binomiaux qui sont une structure particulière permettant de programmer efficacement des files de priorité. Celles-ci sont une variante des files dans lesquelles les éléments sont entrés avec une priorité (qui est un entier) et sortent par ordre de priorité : les éléments de plus petite priorité sortent en premier, et dans le cas où la file contient plusieurs éléments de priorité minimale, l'élément entré en premier sort en premier.

Le TD devra être réalisé en OCaml. On pourra utiliser soit utiliser Eclipse, soit un éditeur de texte classique (par exemple Emacs).

Arbres binomiaux

Nous allons commencer par définir un module BinomialTree permettant de définir des tas fondés sur des arbres particuliers, appelés arbres binomiaux. Dans ces arbres un nœud peut avoir un nombre quelconque de fils, et l'ordre des fils importe.

L'ensemble des arbres binomiaux de rang k est défini inductivement par :

Ainsi, les arbres de rang 0, 1, 2, 3 et 4 sont respectivement des formes suivantes :

                                   

Nous allons implémenter quelques fonctions permettant de les manipuler.

Déposer les fichier BinomialTree.ml et BinomialTree.mli :

Addition d'entiers binaires

Afin de s'exercer pour la partie suivante, nous allons implémenter dans un autre module Binary quelques manipulations simples d'entiers binaires codés comme des listes d'entiers : un entier binaire sera codé par la liste croissante des indices des bits à 1 dans son écriture binaire. Par exemple, l'entier 19, dont l'écriture binaire est 10011, sera codé par la liste [0;1;4]. On notera binary = int list le type des entiers binaires codés de cette façon. Le module aura l'interface Binary.mli suivante :

type binary

val to_int : binary -> int

val of_int : int -> binary

val add_bit : binary -> int -> binary

val add : binary -> binary -> binary
      
On pourra partir du fichier Binary.ml suivant :
type binary = int list

let to_int b =
  (* à compléter *)
  assert false

let of_int n =
  (* à compléter *)
  assert false

let add_bit b k =
  (* à compléter *)
  assert false

let add b1 b2 =
  (* à compléter *)
  assert false
      

Déposer le fichier Binary.ml :

Tas binomiaux

Nous allons maintenant implémenter, dans un nouveau module BinomialHeap, les tas binomiaux. Ce sont des files permettant de stocker efficacement des (multi)ensembles de paires priorité / valeur, d'en ajouter de nouvelles, et d'extraire une valeur de priorité minimale rapidement. L'idée pour stocker n valeurs va être la suivante. Supposons que les indices de bits à 1 dans l'écriture binaire de n soient i1, i2, ..., ik, c'est-à-dire que n = ∑p=1k2ip. Nous allons découper l'ensemble des valeurs en sous-ensembles de taille 2ip, chacun de ces ensembles étant stocké dans les nœuds d'un arbre binomial de rang ip. Ainsi, un tas binomial sera une liste d'arbres binomiaux de rangs respectifs i1, i2, ..., ik avec i1 < i2 < ... < ip. Autrement dit, un tas binomial est une liste d'arbres binomiaux tels que

  1. les arbres de la liste sont des tas (les étiquettes croissent le long des branches),
  2. le rang des arbres est strictement croissant dans la liste.
Nous allons implémenter quelques fonctions permettant de les manipuler.

Déposer les fichier BinomialHeap.ml et BinomialHeap.mli :

BONUS : questions subsidiaires

Les questions suivantes sont optionnelles. Elles permettent de voir l'utilisation que l'on peut faire des files de priorité.

Fonctions auxiliaires sur les files binomiales

Nous allons commencer par implémenter quelques autres fonctions utiles sur les files binomiales.

Déposer le fichier BinomialHeap.ml :

Files de priorité

Nous allons finalement utiliser le module des files binomiales pour créer un module PriorityQueue implémentant les files de priorité (de type 'a heap).

Déposer le fichier PriorityQueue.ml :

Algorithme de Dijkstra

Le module des files de priorité peut être utilisé pour implémenter l'algorithme de Dijkstra qui permet de trouver le plus court chemin dans un graphe dirigé pondéré (chaque arrête est étiquetée par un entier indiquant sa longueur). On trouvera les fonctions de test mentionnées ci-dessous dans le fichier Graph.ml.


Une solution vous est proposée.