Divide and Conquer Paradigm Explained

I. Paradigmes Algorithmiques

Un paradigme algorithmique est une approche ou un cadre général pour concevoir des algorithmes. Il ne s'agit pas d'un algorithme spécifique, mais plutôt d'une stratégie pour résoudre une classe de problèmes. Ces paradigmes fournissent des lignes directrices pour structurer la pensée et l'implémentation, mais leur pertinence dépend du problème à résoudre.

A. Objectifs des Paradigmes Algorithmiques

• Donner un cadre pour la conception d’algorithmes.
• Suggérer une approche pour résoudre un problème donné.
• Aider à choisir la méthode la plus adaptée.

B. Types de Paradigmes Courants

Plusieurs paradigmes algorithmiques existent, chacun adapté à différentes natures de problèmes :

• Dichotomie : Réduction de l'espace de recherche par division répétée.
• Diviser pour Régner (DPR) (Divide & Conquer) : Décomposition récursive d'un problème en sous-problèmes similaires.
• Rencontre au Milieu (Meet-in-the-Middle) : Divise le problème en deux, résout chaque moitié indépendamment, puis combine les résultats.
• Programmation Dynamique (ProgDyn) : Résolution de problèmes en décomposant en sous-problèmes se chevauchant et en mémorisant leurs solutions.
• Glouton (Greedy) : Fait le choix localement optimal à chaque étape dans l'espoir d'atteindre un optimum global.
• Retour sur Trace (Backtracking) : Exploration systématique de toutes les solutions possibles, en revenant sur les choix invalides.

C. Utilité et Limites

La connaissance de ces paradigmes permet de :

• Choisir une approche adaptée pour un cas « simple ».
• Mettre en œuvre efficacement la solution choisie.

Cependant, il n'y a pas toujours d'intérêt à définir formellement qu'un algorithme est "glouton" ou autre ; il s'agit avant tout d'outils conceptuels pour la conception.

II. Le Paradigme Diviser pour Régner (DPR)

Le paradigme "Diviser pour Régner" est une méthode de conception algorithmique puissante qui repose sur la décomposition récursive d'un problème complexe en sous-problèmes plus simples, de même nature, jusqu'à atteindre des cas de base triviaux. Les solutions de ces sous-problèmes sont ensuite combinées pour obtenir la solution du problème initial.

Le Diviser pour Régner résout un problème en trois étapes :

1. Diviser : Le problème est divisé en plusieurs sous-instances du même problème, généralement en un nombre constant de sous-instances (indépendant de la taille de l'entrée). Cette division doit être possible et efficace.
2. Régner : Chacune des sous-instances est résolue récursivement. Les cas de base de la récursion sont généralement des instances assez petites pour être résolues directement.
3. Combiner : Les solutions des sous-instances sont combinées pour former la solution du problème original. Cette étape peut varier de triviale à complexe.

A. Exemples Prototypiques de DPR

1. Tri Fusion (Merge Sort)

Le Tri Fusion est un exemple "paradigmatique" du Divide & Conquer appliqué au tri d'une collection d'éléments.

• Diviser : Un tableau (ou une liste) de éléments est divisé en deux sous-listes (ou sous-tableaux) de tailles approximativement .
• Régner : Ces deux sous-listes sont triées récursivement.
• Combiner : Les deux sous-listes triées sont fusionnées pour produire la liste triée finale. Cette étape de fusion prend un temps linéaire .

Coût : L'équation de récurrence pour le Tri Fusion est , ce qui donne une complexité temporelle de .

2. Tri Rapide (Quicksort)

Le Tri Rapide utilise également une stratégie de "Diviser pour Régner", mais la phase de division est différente.

• Diviser : Le tableau est divisé en deux sous-listes. Tous les éléments d'une sous-liste sont inférieurs (ou égaux) à un élément appelé pivot , et tous les éléments de l'autre sous-liste sont supérieurs (ou égaux) au pivot. Cette partition peut être faite "en place" pour un tableau.
• Régner : Les deux sous-listes sont triées récursivement.
• Combiner : Une fois les sous-listes triées, la combinaison est triviale : il suffit de les concaténer (ou elles sont déjà correctement positionnées si le tri est "en place").

Coût :

• Pire cas : Si le pivot choisi est toujours le plus petit ou le plus grand élément, l'équation de récurrence est , menant à une complexité de .
• Cas espéré (probabilistique) : Avec un bon choix de pivot (par exemple, un pivot aléatoire ou médiane de trois), la complexité moyenne est de .

3. Exponentiation Rapide (Calcul de )

Cet algorithme permet de calculer de manière efficace.

• Diviser : Pour calculer , on calcule .
• Régner : On résout récursivement .
• Combiner :
  • Si est pair, .
  • Si est impair, .

  Les deux sous-instances (pour ) sont identiques par symétrie, et la recombinaison est simple (un carré, éventuellement une multiplication). Ce n'est pas l'exemple le plus "riche" en termes de combinatoire, mais il illustre la puissance du DPR pour réduire le nombre d'opérations.

Coût : ou en fonction de la taille des nombres en jeu, résultant en pour les opérations de base.

4. Multiplication de Matrices (Algorithme de Strassen)

Pour multiplier deux matrices $n \times n$ (ex: Strassen).

• Diviser : Chaque matrice est découpée en quatre matrices blocs de tailles .
• Régner : Au lieu des 8 multiplications de matrices blocs demandées par l'algorithme naïf, on calcule récursivement 7 produits de matrices sur les matrices blocs. Cette réduction est l'idée clé, similaire à l'algorithme de Karatsuba pour la multiplication rapide de grands nombres.
• Combiner : Le résultat est construit en sommant les résultats des matrices blocs.

Coût : L'équation de récurrence est . Cela donne une complexité de .

Avantage : Puisque , c'est asymptotiquement plus rapide que l'algorithme naïf de multiplication de matrices qui est en .

5. Distance Minimale entre Deux Points dans le Plan

Ce problème en géométrie algorithmique peut également être résolu par DPR.

• Diviser : Trier les points selon les coordonnées , puis diviser l'ensemble en deux moitiés par une ligne verticale.
• Régner : Trouver récursivement la distance minimale dans chaque moitié.
• Combiner : La phase critique consiste à trouver si la distance minimale globale se trouve entre un point de la moitié gauche et un point de la moitié droite. Cela se fait en ne considérant que les points situés dans une bande étroite autour de la ligne de division, et en les triant par coordonnées .

B. Caractéristiques Générales du DPR

• Une approche possible lorsque un problème se découpe « bien » en sous-problèmes de même type.
• Souvent appliqué à des structures telles que les listes, tableaux, graphes, arbres ; en présence d'objets de grande dimension (polynômes, matrices) ; ou en géométrie algorithmique.
• Il n'est pas garanti d'améliorer un algorithme naïf (ex: pire cas du Quicksort).
• L'analyse de coût implique d'établir puis de résoudre l'équation de récurrence associée.

III. Structures de Données : Arbres Binaires et Tas

Le paradigme Diviser pour Régner est souvent intrinsèquement lié aux structures de données récursives comme les arbres, où la récursion est un moyen naturel de les parcourir et de les manipuler.

A. Définitions Fondamentales des Arbres

Un arbre binaire est une structure de données récursive fondamentale.

• Cas de base : Un arbre vide (E en OCaml) est un arbre sur n'importe quel type .
• Cas inductif : Si et sont des arbres sur un même type , et est une valeur de type , alors l'arbre formé par le nœud et les enfants (gauche) et (droit) est un arbre sur (N of 'a * 'a tree * 'a tree en OCaml).

1. Glossaire des Termes

• Nœud : Une instance du constructeur N.
• Racine : Le nœud "initial" d'un arbre, sans parent.
• Feuille : Un nœud sans enfant (N (_, E, E)).
• Nœud interne : Tout nœud qui n'est pas une feuille.
• Enfant gauche/droit (ou fils gauche/droit) : Les sous-arbres lc et rc d'un nœud N(x, lc, rc).
• Parent (ou père) : Le nœud au-dessus des enfants.
• Taille : Nombre total de nœuds dans l'arbre.
• Degré : Nombre d'enfants non vides d'un nœud. Le degré d'un arbre est le degré maximum de ses nœuds. (Un arbre de degré 1 signifie qu'au moins un nœud n'a qu'un seul enfant non vide).

2. Hauteur et Profondeur

• Profondeur d'un nœud : Longueur du chemin de la racine au nœud.
• Niveau de profondeur : L'ensemble de tous les nœuds de profondeur .
• Hauteur d'un arbre : La profondeur maximale de ses nœuds. (Par convention, la hauteur d'un arbre vide est -1).

Pour un arbre binaire de hauteur , le nombre total de nœuds est au maximum .

3. Types Spécifiques d'Arbres Binaires

• Arbre binaire strict : Tous les nœuds ont degré 0 ou 2 (soit une feuille, soit deux enfants). Formellement, où est le nombre de feuilles et le nombre de nœuds internes, avec égalité si et seulement si l'arbre est strict.
• Arbre binaire complet : Un arbre binaire strict dont toutes les feuilles sont à la même profondeur. Parfois appelé "arbre parfait". Le nombre de nœuds d'un arbre binaire complet de hauteur est .
• Arbre binaire quasi-complet (ABQC) : Un arbre binaire de taille est quasi-complet s'il ne présente pas de "trous" dans sa représentation en tableau. C'est-à-dire, tous les indices correspondent à un nœud.

Un ABQC de taille a une hauteur de . Ils sont "équilibrés".

Propriétés équivalentes d'un ABQC :

• Il a uniquement des feuilles en profondeur ou .
• Les feuilles à profondeur sont visitées avant celles de profondeur dans un parcours en profondeur gauche ("le plus à gauche").
• Si un nœud de profondeur a un unique enfant, celui-ci est nécessairement à gauche et est le dernier nœud de profondeur à être visité dans un parcours en profondeur gauche.

B. Numérotation et Parcours des Nœuds

La numérotation et le parcours des nœuds sont essentiels pour la manipulation et l'analyse des arbres binaires.

1. Numérotation par Mots Binaires

Les nœuds peuvent être indexés par des mots binaires, représentant le chemin depuis la racine.

• La racine a l'index (le mot vide).
• Pour un nœud d'index , l'enfant gauche a l'index et l'enfant droit (ou et selon la convention).

L'index donne le chemin à suivre depuis la racine (0 : gauche, 1 : droite).

2. Numérotation par Entiers Naturels

Une autre numérotation inductive, très utile pour le stockage en tableau :

• La racine a le numéro 0.
• Pour un nœud de numéro :
  • L'enfant gauche a le numéro .
  • L'enfant droit a le numéro .

Cette numérotation est cruciale pour représenter un arbre binaire quasi-complet dans un tableau, où A[i] stocke le nœud de numéro i.

let _parent i = (i - 1)/2
let _left_kid i = 2*i + 1
let _right_kid i = 2*i + 2

3. Parcours d'Arbres

Un parcours d'arbre est un algorithme visitant les nœuds d'un arbre, généralement une unique fois, dans un ordre précis, pour leur appliquer un traitement.

• Parcours en profondeur (DFS - Depth-First Search) : Basé sur la définition inductive des arbres, avec des variantes selon l'ordre de traitement de la racine et des sous-arbres.
  • Préfixe (Racine -> Gauche -> Droite) : La racine est traitée avant ses enfants.

    let rec iter_dfsa (f : 'a -> unit) = function
    | E -> ()
    | N (x, lc, rc) -> f x ; iter_dfsa f lc ; iter_dfsa f rc
    

    Lorsque des appels récursifs multiples sont représentés par un arbre, l'ordre d'appel (empilement) est un parcours préfixe.
  • Infixe (Gauche -> Racine -> Droite) : La racine est traitée entre ses enfants. Utile pour les arbres binaires de recherche (ABR) pour énumérer les nœuds dans l'ordre croissant.
  • Postfixe (Gauche -> Droite -> Racine) : La racine est traitée après ses enfants. Utile pour l'évaluation d'expressions arithmétiques stockées dans un arbre. L'ordre de retour des appels récursifs (dépilement) est un parcours postfixe.
• Parcours en largeur (BFS - Breadth-First Search) : Parcourt les nœuds niveau par niveau (par ordre de profondeur croissante). Typiquement implémenté avec une file (queue).

4. Efficacité des Algorithmes sur les Arbres

Beaucoup d'algorithmes sur les arbres ont un coût proportionnel à la hauteur de l'arbre.

• Un arbre équilibré (, comme un ABQC) permet des opérations exponentiellement plus efficaces qu'un arbre peigne (, un arbre déséquilibré où chaque nœud n'a qu'un enfant).
• En pratique, les choses se passent bien en moyenne et il est souvent possible de garantir (éventuellement probabilistiquement) que les arbres manipulés restent équilibrés.

C. Preuves sur les Arbres

Les propriétés des arbres sont souvent prouvées par :

• Récurrence : Généralement une récurrence forte sur la hauteur de l'arbre.
• Induction structurelle : Démontrer que la propriété est vraie pour les cas de base (l'arbre vide, les feuilles) et qu'elle est préservée par les constructeurs inductifs (ajout d'un nœud avec enfants). Cette méthode est souvent similaire à un filtrage de motif exhaustif.

D. Représentation en Langage C

En C, un arbre binaire peut être représenté par une structure chaînée de nœuds :

struct btree
{
    struct btree *parent; // optionnel
    struct btree *left;
    struct btree *right;
    int data; // ou void* pour être générique
};

• L'absence d'un parent ou d'un enfant est gérée par des pointeurs nuls (NULL).
• C'est une généralisation arborescente des listes chaînées.

IV. Les Files de Priorité et les Tas

Une file de priorité (Priority Queue) est une structure de données abstraite qui gère une collection d'éléments, chacun ayant une "priorité" associée. Les opérations principales incluent l'ajout d'un élément et l'extraction de l'élément avec la priorité la plus élevée (max-first) ou la plus basse (min-first).

A. Opérations Essentielles d'une File de Priorité

• create() : Crée une file de priorité vide.
• isEmpty() : Vérifie si la file est vide.
• size() : Retourne le nombre d'éléments.
• push(e) / insert(e) : Ajoute un élément e avec sa priorité.
• peek() : Inspecte l'élément de priorité maximale sans le supprimer.
• pop() / extract() : Supprime et retourne l'élément de priorité maximale.
• (Optionnel) : modify_priority(e, new_priority) : Modifie la priorité d'un élément existant.

La relation d'ordre (max ou min) est paramétrable. Les éléments sont souvent des couples (priorité, valeur), mais peuvent être simplement des valeurs si la valeur elle-même sert de priorité.

B. Applications des Files de Priorité

• Ordonnancement des processus dans un système d'exploitation.
• Algorithmes de tri (ex: Tri par Tas).
• Recherche de plus courts chemins (ex: algorithme de Dijkstra).
• Arbres couvrants de poids extrémal (ex: algorithme de Kruskal).
• Compression de données (ex: code de Huffman).
• Algorithmes "gloutons" en général.

C. Implémentations Possibles

• Liste triée : Coût d'insertion , Coût d'extraction .
• Arbre binaire de recherche (équilibré) : Coût des opérations .
• Tas (Heap) : Implémentation la plus courante et efficace, avec des coûts logarithmiques.

V. Les Tas (Heaps)

Un tas binaire est une structure de données qui implémente efficacement une file de priorité. Il s'agit généralement d'un arbre binaire quasi-complet qui satisfait la condition de tas.

A. Condition de Tas

Un arbre satisfait la condition de tas si l'étiquette de tout nœud est plus grande (ou plus petite) que celle de ses enfants, selon une relation d'ordre donnée (propriété globale). Cela implique que l'élément maximum (pour un tas-max) est toujours à la racine de l'arbre.

• Tas-max : Chaque nœud est plus grand que ses enfants.
• Tas-min : Chaque nœud est plus petit que ses enfants.

B. Représentation d'un Tas dans un Tableau

Grâce à la propriété d'être un arbre binaire quasi-complet, un tas peut être stocké efficacement dans un tableau, sans avoir besoin de pointeurs explicites.

• L'élément à l'indice i a ses enfants aux indices 2i + 1 (gauche) et 2i + 2 (droit).
• Son parent est à l'indice (i - 1) / 2.
• On stocke le tableau dat et le nombre courant d'éléments cnt (la taille logique du tas).

type 'a heap = {
    dat : 'a array; // ou int* dat; en C
    gt : ('a -> 'a -> bool); // fonction de comparaison
    mutable cnt : int; // taille actuelle du tas
}

C. Opérations Internes du Tas (Primitives)

Ces opérations maintiennent la propriété de tas après une modification.

1. _siftDown(i) (ou Heapify-Down / Percolate-Down)

Entrée : Un indice i et un (sous-)arbre qui est un tas, sauf éventuellement pour le fait que le nœud d'indice i peut être plus petit que ses enfants (pour un tas-max).

Algorithme :

1. Si le nœud à i est plus grand que ses enfants (condition de tas satisfaite) : Terminer.
2. Sinon : Échanger le nœud à i avec le plus grand de ses enfants.
3. Récurser sur le sous-arbre modifié à la nouvelle position de l'élément échangé.

Terminaison : On récurse sur un arbre de hauteur strictement moins élevée. La hauteur est un variant décroissant.

Correction : Par récurrence forte sur la hauteur. Un arbre sans enfants est un tas. L'échange préserve la condition de tas pour les autres nœuds, et l'appel récursif corrige la sous-arborescence. Les éléments restent les mêmes.

Coût : Dans le pire cas, il est proportionnel à la hauteur de l'arbre dont la racine est le nœud d'indice i. Comme le tas est quasi-complet, la hauteur est en , donc _siftDown est aussi en .

2. _siftUp(i) (ou Heapify-Up / Percolate-Up)

Entrée : Un arbre h et un indice de nœud i tel que h est un tas, sauf pour le fait que le nœud en i peut être plus grand que son parent (pour un tas-max).

Algorithme :

1. Si le nœud à i est plus petit que son parent (condition de tas satisfaite) : Terminer.
2. Sinon : Échanger le nœud à i avec son parent.
3. Récurser en son nouvel indice (le parent).

Terminaison : On remonte dans l'arbre, la profondeur du nœud diminue. La profondeur (ou la distance à la racine) est un variant décroissant.

Correction : Par récurrence forte sur la profondeur. Si i est la racine, la propriété est vérifiée. L'échange préserve la condition de tas pour le reste de l'arbre, et on corrige vers le haut.

Coût : Dans le pire cas, proportionnel à la profondeur du nœud en i. Garanti .

Exemple OCaml de _siftUp :

let _swap d i j =
    let ti = d.(i) in
    d.(i) <- d.(j) ;
    d.(j) <- ti

let rec _siftUp ({dat ; gt} as h) (i:int) : unit =
    if i = 0 then () else (* Si on est à la racine, on ne peut pas remonter *)
    let i_par = _parent i in
    if gt dat.(i) dat.(i_par) then (* Si l'enfant est plus grand que le parent *)
        ( _swap dat i i_par ; _siftUp h i_par ) (* On échange et on continue de remonter *)

3. _increase(i, new_val) / _decrease(i, new_val)

Ces opérations modifient la priorité d'un élément à un indice i donné. Si la nouvelle valeur est plus grande, on appelle _siftUp. Si la nouvelle valeur est plus petite, on appelle _siftDown. Leur coût est donc également .

D. Opérations Publiques de la File de Priorité avec un Tas

1. push(e) (Ajouter un élément)

Algorithme :

1. Ajouter l'élément e à la fin du tableau (au premier indice libre).
2. Appeler _siftUp sur cet élément nouvellement ajouté pour restaurer la propriété de tas.

Coût : La complexité est dominée par _siftUp, soit .

Exemple OCaml de push :

let push ({dat; gt; cnt} as h) (e:'a) : unit =
    let heap_size = Array.length dat in
    if cnt = heap_size then failwith "heap is full" ; (* Vérifier l'espace disponible *)
    dat.(cnt) <- e; (* Ajout à la fin *)
    _siftUp h cnt ; (* Remontée de l'élément *)
    h.cnt <- cnt + 1 (* Incrémenter la taille du tas *)

2. peek() (Consulter l'élément maximum)

Algorithme : Retourne simplement l'élément à l'indice 0 du tableau.

Correction : Par la propriété de tas, la racine contient toujours l'élément de priorité maximale.

Coût : (constant).

let peek_opt (h:'a heap) : 'a option =
    if h.cnt = 0 then None else Some h.dat.(0)

3. pop() (Supprimer et retourner l'élément maximum)

Algorithme :

1. Récupérer l'élément à l'indice 0 (le maximum).
2. Remplacer cet élément par le dernier élément du tas (à l'indice cnt-1).
3. Diminuer la taille logique du tas (cnt) de 1.
4. Appeler _siftDown sur l'élément à l'indice 0 pour restaurer la propriété de tas.

Coût : Dominé par _siftDown, soit .

4. heapify() (Construire un tas à partir d'un tableau non ordonné)

Entrée : Un tableau dat (un tas "cassé") qui ne satisfait pas forcément la condition de tas.

Algorithme (Bottom-Up) :

1. Parcourir le tableau à partir du dernier nœud qui n'est pas une feuille (indice h.cnt/2 - 1) jusqu'à la racine (indice 0).
2. Pour chaque nœud i, appeler _siftDown(i).

let heapify (h:'a heap) : unit =
    let ni = h.cnt/2 - 1 in (* Premier nœud non-feuille *)
    for i = ni downto 0 do _siftDown h i done

Invariant : Après chaque itération, l'arbre enraciné en i et tous les arbres enracinés en j > i sont des tas.

Coût : Bien qu'il y ait appels à _siftDown qui sont chacun en , l'analyse plus fine de cette approche bottom-up montre que le coût total est en fait (voir TD pour les détails). Ceci est très efficace.

E. Extensions des Tas

• Tas de capacité variable : Utiliser un tableau dynamique pour que le tas puisse grandir.
• Modification des priorités d'éléments arbitraires : Nécessite de pouvoir retrouver l'indice d'un élément dans le tableau, souvent en utilisant un dictionnaire ou une table de hachage associant l'élément à son indice.
• Autres types de tas :
  • Tas fonctionnels (implémentations immuables).
  • Tas binomiaux, tas de Fibonacci (offrent des complexités amorties meilleures pour certaines opérations, notamment la fusion de tas).
  • Tas min-max, intervalle (pour gérer simultanément les priorités min et max).

VI. Le Tri par Tas (Heapsort)

Le Tri par Tas est un algorithme de tri par comparaison qui utilise un tas binaire pour ordonner les éléments.

A. Principe Général

On peut trier un tableau via une file de priorité en :

1. Créant une file de priorité avec tous les éléments du tableau.
2. Retirant l'élément maximum (ou minimum) de la file un par un jusqu'à ce qu'elle soit vide. Les éléments extraits sont placés dans l'ordre inverse du tri souhaité.

Cette approche est similaire au tri par arbre binaire de recherche (ABR).

B. Tri par Tas In-Place

L'avantage du Tri par Tas est qu'il peut être réalisé en place (sans nécessiter de mémoire supplémentaire significative) en utilisant la propriété de représentation du tas dans un tableau.

1. Construction du tas (heapify) :
   • Transformer le tableau d'entrée non trié en un tas-max.
   • Cette étape est réalisée en place, en , en appliquant _siftDown de bas en haut (comme décrit précédemment). La structure du tas est "superposée" au tableau existant.
2. Extraction des éléments triés :
   • Itérer de jusqu'à 1 (où est la taille du tableau).
   • À chaque étape, l'élément maximum (racine du tas à l'indice 0) est échangé avec le dernier élément actuel du tas (à l'indice ).
   • L'élément échangé (ancien maximum) est maintenant à sa position finale triée. Le tas logique est réduit de 1 élément (sa taille passe de à ).
   • Appeler _siftDown(0) sur le nouvel élément à la racine (l'ancien dernier élément) pour restaurer la propriété de tas sur les éléments restants.

Coût :

• Construction du tas : .
• extractions : Chaque extraction coûte car elle implique un _siftDown. Donc, extractions coûtent .
• Complexité totale : .

Propriétés :

• En place : Oui, utilise un espace constant en plus du tableau à trier. Il n'y a pas d'espoir de faire mieux.
• Asymptotiquement optimal : Il est optimal pour un tri par comparaison, dans le pire des cas, tout comme le tri fusion.
• Performance pratique : Bien qu'asymptotiquement optimal, il peut être plus lent que des algorithmes comme Quicksort en pratique, à cause d'un moins bon cache-hit ratio ou de constantes implicites plus élevées.

C. Exemple de mise en œuvre OCaml pour heapSort

let heapSort (dat:'a array) (gt:'a -> 'a -> bool) : unit =
    let cnt = Array.length dat in (* Taille du tableau *)
    let h = {dat ; gt ; cnt} in (* Création d'une structure de tas temporaire *)
    begin
        heapify h; (* Construction du tas initial (en place, O(N)) *)
        for i = cnt - 1 downto 1 do (* Parcours de la fin vers le début *)
            (* Échanger le max (dat.(0)) avec le dernier élément non trié (dat.(i)) *)
            _swap dat 0 i;
            (* Réduire la taille logique du tas pour l'appel de _siftDown *)
            h.cnt <- i;
            (* Restaurer la propriété de tas pour les éléments restants *)
            _siftDown h 0;
        done;
    end

Note: La variable top dans le pseudo-code original semble être utilisée pour récupérer l'élément maximum sans l'assigner à dat.(i), ce qui est une erreur logique si le tri est réellement fait en place. La version OCaml corrigée ci-dessus (et conventionnelle) effectue l'échange et un _siftDown.

Récapitulatif des Paradigmes et Structures Associées