Aller au contenu

Classe TasMin⚓︎

Un Tas-Min est un arbre binaire vérifiant les propriétés suivantes :

  • c'est un arbre binaire parfait tassé à gauche (tous ses niveaux sont complets sauf éventuellement le dernier qui, dans ce cas, est rempli de gauche à droite) ;
  • chaque nœud possède une étiquette. Toutes les étiquettes sont comparables entre elles ;
  • chaque nœud a une étiquette strictement inférieure à celle de ses éventuels enfants.

Cette dernière propriété assure que la racine d'un Tas-Min est le nœud dont l'étiquette est minimale.

graph TD
    R{12} --> N1{13}
    R     --> N2{53}
    N1    --> N3{65}
    N1    --> N4{20}
    N2    --> N5{61}
    N2    -.-> N6( )

L'objectif de cet exercice est la création d'une classe TasMin. On utilisera la modélisation sous forme d'un tableau redimensionnable. Dans cette modélisation, avec Python :

  • le données sont stockées dans un tableau dont la première valeur (à l'indice 0) est None,
  • l'étiquette de la racine est stockée à l'indice 1,
  • si l'étiquette d'un nœud est stockée à l'indice i :
    • celle de son enfant gauche, s'il existe, est à l'indice 2 * i,
    • celle de son enfant droit, s'il existe, est à l'indice 2 * i + 1.
Tableau redimensionnable

Pour cet exercice, on utilisera le type list de Python, et les méthodes primitives suivantes :

  • création d'une liste,
  • ajout d'un élément à la fin de la liste,
  • suppression et récupération du dernier élément,
  • accès en lecture et écriture aux éléments avec l'indice donné.

On n'utilisera pas les tranches, ni aucune fonction native de tri.

On attend une classe TasMin avec les méthodes suivantes :

  • Initialisation : on crée un tableau redimensionnable donnees qui contient None en unique élément, on crée un attribut effectif égal à zéro ;
  • est_vide() : détermine si le Tas-Min est vide en renvoyant un booléen ;
  • echange(i, j) : échange les valeur d'indices i et j dans le tableau donnees ;
  • ajoute(element) :
    • on augmente effectif de 1,
    • on ajoute element en fin de donnees,
    • on échange les éléments nécessaires pour garder une structure de Tas-Min. element remonte la structure arborescente, en échangeant avec son ancêtre, jusqu'à que la structure soit correcte ;
  • extrait_min() :
    • on enregistre la valeur minimale des données, à l'indice 1, pour la renvoyer en fin de traitement,
    • on diminue effectif de 1,
    • on extrait le dernier élément de donnees pour le placer à l'indice 1,
    • on échange les éléments nécessaires pour garder une structure de Tas-Min. On commence par échanger l'élément remonté avec le plus petit de ses enfants et l'on poursuit le procédé dans la branche.

Il n'est pas demandé, ni nécessaire dans cet exercice, d'écrire les tests permettant de vérifier que les paramètres des différentes méthodes sont valides.

On donne un exemple commenté pour chacune des deux dernières méthodes.

Ajouter un élément - exemple

On suppose qu'on dispose d'un Tas-Min, et que l'on souhaite y ajouter l'élément \(17\).

graph TD
    R{10} --> N1{42}
    R     --> N2{23}
    N1    --> N3{55}
    N1    --> N4{67}
    N2    --> N5{31}
    N2    --> N6{26}
    N3    --> N7{60}
    N3    --> N8{59}
    N4    --> N9{88}
    N4    --> N10{83}
    N5    -.-> N11( )
    N5    -.-> N12( )
    N6    -.-> N13( )
    N6    -.-> N14( )

Modélisation : [None, 10, 42, 23, 55, 67, 31, 26, 60, 59, 88, 83]

graph TD
    R{10} --> N1{42}
    R     --> N2{23}
    N1    --> N3{55}
    N1    --> N4{67}
    N2    --> N5{31}
    N2    --> N6{26}
    N3    --> N7{60}
    N3    --> N8{59}
    N4    --> N9{88}
    N4    --> N10{83}
    N5    --> N11{17}
    N5    -.-> N12( )
    N6    -.-> N13( )
    N6    -.-> N14( )

    classDef marque fill:#f77,stroke:#333,stroke-width:4px;
    class N11 marque;

Modélisation : [None, 10, 42, 23, 55, 67, 31, 26, 60, 59, 88, 83, 17]

L'effectif a augmenté de 1.

graph TD
    R{10} --> N1{42}
    R     --> N2{23}
    N1    --> N3{55}
    N1    --> N4{67}
    N2    --> N5{17}
    N2    --> N6{26}
    N3    --> N7{60}
    N3    --> N8{59}
    N4    --> N9{88}
    N4    --> N10{83}
    N5    --> N11{31}
    N5    -.-> N12( )
    N6    -.-> N13( )
    N6    -.-> N14( )

    classDef marque fill:#f77,stroke:#333,stroke-width:4px;
    class N5,N11 marque;

Modélisation : [None, 10, 42, 23, 55, 67, 17, 26, 60, 59, 88, 83, 31]

graph TD
    R{10} --> N1{42}
    R     --> N2{17}
    N1    --> N3{55}
    N1    --> N4{67}
    N2    --> N5{23}
    N2    --> N6{26}
    N3    --> N7{60}
    N3    --> N8{59}
    N4    --> N9{88}
    N4    --> N10{83}
    N5    --> N11{31}
    N5    -.-> N12( )
    N6    -.-> N13( )
    N6    -.-> N14( )

    classDef marque fill:#f77,stroke:#333,stroke-width:4px;
    class N5,N2 marque;

Modélisation : [None, 10, 42, 17, 55, 67, 23, 26, 60, 59, 88, 83, 31]

On obtient un Tas-Min.

Extraire le minimum - exemple

On suppose qu'on dispose d'un Tas-Min, et que l'on souhaite extraire le minimum.

graph TD
    R{10} --> N1{42}
    R     --> N2{23}
    N1    --> N3{55}
    N1    --> N4{67}
    N2    --> N5{31}
    N2    --> N6{26}
    N3    --> N7{60}
    N3    --> N8{59}
    N4    --> N9{88}
    N4    --> N10{83}
    N5    -.-> N11( )
    N5    -.-> N12( )
    N6    -.-> N13( )
    N6    -.-> N14( )

Modélisation : [None, 10, 42, 23, 55, 67, 31, 26, 60, 59, 88, 83]

graph TD
    R{83} --> N1{42}
    R     --> N2{23}
    N1    --> N3{55}
    N1    --> N4{67}
    N2    --> N5{31}
    N2    --> N6{26}
    N3    --> N7{60}
    N3    --> N8{59}
    N4    --> N9{88}
    N4    -.-> N10( )
    N5    -.-> N11( )
    N5    -.-> N12( )
    N6    -.-> N13( )
    N6    -.-> N14( )

    classDef marque fill:#f77,stroke:#333,stroke-width:4px;
    class R,N10 marque;

Modélisation : [None, 83, 42, 23, 55, 67, 31, 26, 60, 59, 88]

L'effectif diminue de 1.

On a pris soin de sauvegarder \(10\) dans une variable.

graph TD
    R{23} --> N1{42}
    R     --> N2{83}
    N1    --> N3{55}
    N1    --> N4{67}
    N2    --> N5{31}
    N2    --> N6{26}
    N3    --> N7{60}
    N3    --> N8{59}
    N4    --> N9{88}
    N4    -.-> N10( )
    N5    -.-> N11( )
    N5    -.-> N12( )
    N6    -.-> N13( )
    N6    -.-> N14( )

    classDef marque fill:#f77,stroke:#333,stroke-width:4px;
    class R,N2 marque;

Modélisation : [None, 23, 42, 83, 55, 67, 31, 26, 60, 59, 88]

graph TD
    R{23} --> N1{42}
    R     --> N2{26}
    N1    --> N3{55}
    N1    --> N4{67}
    N2    --> N5{31}
    N2    --> N6{83}
    N3    --> N7{60}
    N3    --> N8{59}
    N4    --> N9{88}
    N4    -.-> N10( )
    N5    -.-> N11( )
    N5    -.-> N12( )
    N6    -.-> N13( )
    N6    -.-> N14( )

    classDef marque fill:#f77,stroke:#333,stroke-width:4px;
    class N6,N2 marque;

Modélisation : [None, 23, 42, 26, 55, 67, 31, 83, 60, 59, 88]

On obtient un Tas-Min. On peut renvoyer la valeur sauvegardée : \(10\).

Difficultés principales

Quand on cherche à extraire le minimum, on passe le dernier en premier, puis on le fait redescendre (de manière répétitive) à la place de son plus petit enfant.

Trois cas peuvent se produire :

  • il n'y a pas d'enfants : l'élément est à la bonne position ;
  • il y a un enfant à gauche ;
  • il y a aussi un enfant à droite ;

Il existe une condition simple entre l'indice d'un nœud et effectif pour savoir si ce nœud a un, deux ou aucun enfant.

On traitera le cas d'effectif 1 à part.

Compléter le code :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10
.128013s3_8èufvIy n7aS1me(P2C4:jtwi][hE*)6Oo;bcdgM/T0làqAp!.rL-,=+Nzk95Rxé050P0s0A0o0C0V0b0l0O0V0o0b0b0*010A0C0Z010406050b0g0r0r0o0$0k040p0L0V0g170L0m0l020o0r0Z0M0l0;0s1h0$0X0g0s0b050S1e1g1i1k1c0Z041I1P051S0S1S1U1P1c0P0C0i0 1113150F0C0Q0F0V1,0F0A1a050`0N0V0s1%1214011+1-1/1-0A1^1`1?0A0N0L0P1k1@0$1Q0A0F0 1n0b0Z0o0m150v011|1)010h0|0s0m1v0s1?2k2m2r1~2u1`2x0r2z040a0l0u0$0L0Z0L0b0C1q1s0^2i0$0$0s0O2U1I2B0m1Q0S2g2*0A2e2d2f0P2D151/0m2w2R1?1!1$101}2@0C2_0m2a1#1?0Z2Z1Q2(2*3b1d2l1s2 2s340$1h0V1a0l0q2%3f1b3e2C3h1~3j3l3n0v3q2m3s2(2?013x0o3m040l0c3B2)1c3E3v153H3J0l0x3N3D3f3F3T3n0:3X3P3Z3R3G0L3k3I3n0J3(3t3g1(3w3-3y3K0n3=3Q3^3S3`3/3K0e3~3*403,3.3U0/463u483#040q0U4d3@30493{0q3p1J3r3)4e4m4g0q3A4r3C4t4l3i423J0q3M4z3O3?3!4E1a0q3W4I3Y4u4D4a4N3%4Q4B4L4U4h3;4X4K3+4w3}4%3 4v4M4h454,474.4!0q4c4=4S3_4!0v4j4{4C4}3{0v4q3b4Y4)4/0v4y574(4f5a4H5d4-4T544P5i4?5k430v4W5n4|414~4$5t525v544+5y4Z544;5D594~4`5H5f4!0c505L4@3{0c564s5e5R430c5c5V5j535Y5h5#5o5%3J0c5m5*5u4n5Y5s5:5z5=5-5x5^5E5Y5C5}5I5S5G615M5S5K655X3J0x5P695p6b5U4A5W6f1a0x5!6i5$5A430x5)6o5+6q6b5/6u5;4g0x5@6z5_6B5|6E5~6b606I626r646M666r686Q6a1a0:6d6U6k040:6h4J6p5`6W6n6(6v6*6#6t6-6A4/0:6y2)1R391I2}2-0P2;3F0O2a2J0@1#1Q380s3a3r3X05730^7b5;0.1a3v7d6)0B3n7m6.0m0O1a0T120R327q5;19040y3(0l7F0l6j1~7j040^0h7z5_7o3K7O3F0h0r1a0d0d322T7X7S3+7B0t7$480N7B0b0s0V7N4Q7I157B0I7D4X7G7|7H6)7,1a7.7:7*4m0L1a0#843i1a0P1r2_1G3X7~6.86040*8g7?017B0E897J7t040,1r0s8r7@1a0D7E7}7F8n8004827;3d6)8j887=6)0m1a0s0h0h2!178J3r8h5;8j8l4Q8Z5_0r0C1a6Y3O067|8n7K7M8y017Q7H8O7r0h8R0b0A0d0i0C0^8@7(8@8G8I951a7_8C8D8;1a2Z0A0g0$0m8m7 7-7/8X3C8n8M8@8Q048S8U2#0C9q2)8(3F8#8$3b9D3+8*8,3(8/7G9f7L8S8@8_9u8}9w0O0F2m0Q8x8{7A1a7)9$5_989p9a040)9m7r1a0C9.9:8%8n9v0z9.9c7{8D9I4f1a0A1B0Z9;8!1a9G8Y8F9o839*9E879u8b8d0s8fag7%1a8qaoa3049@as4m7B8Ba09e9n819-aw2s9taF3wak0m8e1HaI8z04ar8K9=au9.az9H9saaa89+ae9B7h5_aHaS6AaKaM9.aR7c8P1a9}aO8o8A9d7}adaDafa+a)aia^9v8caLamaNb03F8paj04a@b9ap04aWac8LaZ9`a=04a51w9M8:6)8=9Ra^9Tb39V0o0z0L1p9#bf4896a^9,a a;6.7B9_aXbn7/1B2w0A9~7`57a1a24mbJa%aY048NbF4va-b78@a*bLa,040o0Z0Z2w0P9.9)b*8a9w1`2I0mbUa^7^a{bs6.b#b.b2b}aJ9w8T8V9Aa!ah040+ab3CbZ2s9K4hc69ObnavbP8iblcw5;c9a^b/9rbQcf9za%9NaBaT0C0d2l2Zc2ci3+8#cRatcvbjcx040S0ScU4mcq6,1bbY9P0B1+1`c$2sbHcc3S9?c:1~8j020Q0A0Mc_15cq6%a(ba9bd0010L7Q2mb`bmbM9(97a$cab(bcb5a.c4aqbccMcObTaVd7c{c}c ddcAdhcCcbb:6Fb,anc?a_aQdpaV9 bXbYctc8dAdHcD6`bQ9X9ZbEdDd504b|dZ4)9?cN1idsdn9/d79vcWcEde040IcscKb;d;9Cb%cmd}cud*cPc3dNdOcocddqd+cQdyb18kd/c^eccjc!d7c(brdP7i8bbvdHbxdH0m9V0s0=2.0{908*9ld-d$d=dza~b$6)7^bW4sc+bt9?a%e715cBdSdCeFdE9w8 9193dYeWd!0tdMeMe6eR017K0$0{7.d/2J0j0m0^0=0G2Y3-b{8@0b2p04017v0~922W1y0C1w2R2S1_1{0P00ewey0C2Z0l1`0leBfa1f019~emd`5_7Kcheh3+eTd%48dTd4d(ce9y8Wduaad 7R6)d29.eL4Ae,e-fBe%cSeVdUaT9xcgeQd~ek8+048-c*e,9P9h9jeCcza#eHdib)fCb+7LaldGf{aGfYfFat2Qa7eDd^4XcJa|bnfpfKeefz7+dRg0c`g29{dFb8gjaPa:fW48fPd-bicne-0O0q1a03fm000?0V0?c10Afo7Z3l0l0W0lcP0i0L0k0s0$gNfm0o0l2uf=4sgac75;gzgB0l0K1s0Z110O1{gO11gP0o0O321{fn0^9k0CgU0lgFgHd,e5gbdQf^dBdjb3gna/8@gudHaygefMfUgigs85glbndlb-haf`hnb~g5b{g8h6g(f@8HaEeUhbet8RcGfJggho040(hk8nhgg$eN6.g*04gCg-0l0igYfn2Z2I24flgO0g2_0lg/g_1{1E0CgP1Gb^2#g|gY0$0f0Qc/aAh7d{0d340s0gdcf?cjhPfOf*d3g%eneXdq2OdW7yhLg1gfi99Jf*f,if8EeO04c-2vefaui40Li6i8cXa9040!ibcLcNij9Yilhh1afR3OfTgmiA380Likg#cnf(ime8iBiDd_i2fwePf)1ac)e-8j0HizcMi5i7ge020Vc~iJeGhDbKhvgkhGgp3GhIfIfyiP7C8ggygAhW0l0|0lew0C8 1{h,jjeu2mgJ0Q0o0g9Xe$iSfTig3Ffxf%aCj1eIcYhufZb;hrf j3gqhff*i:b%i?i$c@iAi_iEjNdIgwe0cYi|c~d7fVjJedjIg3f|jLgojZbbhcjWiCi`gviRf-jzi+3!d)iWiYhji.04jRbk04jTipcVi(j{9Hjeg+1rh.i6gJ0VgEdW0m9!gV0o0i2!gD2w0hjr0ljtjv0Fjxj~dO9PjaiF8)jQgekbkJk1j_i)jUd81a0+k6d3i;1aj(0Mi hC99htbcf#cHfQjd8nhVgCjijkjm0ljokxkz0P2O2Ti*hTeoaujDh8jFf_dkf~j=j,d!grlaiqi/kMi@kejYj$iGkVkShRj?a`kSc{i}dxkcb!hmldfDhpaTj;hej^iiiXiNiZlyax8Aj}itjziUlFk4lrcykOlek7lgkSd:ligelmlvcpidk.6)k:0lkjb^1pgD0?kpkr0lktkvknk`c20lk|0Lk~i1l0i,l2lhk3lHgeiIlhjXk-m2f.jEk(hFj.iU2!9YkqkE8nc=j6lZmcd-bOlUkdm70{lIj/c;d6mee6lPl!lSiomwf|lQm8mEkGe1myiOmKink$3Fcqism372jfgCg!i*f/0_f;izgd4%0S7f7a6{m;0S6~1I0A70m_2/2+292b2-0ofe2*6~1OmB1~h%0dky0.0s0d0F0c1a1A1C1E1G0lj}1R3s1P0j0Vjj8 h.fc0Cfel~001p0|jlh1fn05gY0F2Z0h1*240Z0b0yc!8c0O0b0#0Z0k2g1r0#3-0Q0S0h0$0S0c0S1/0Ne:1j0SkDb?0X0#1;0r3J0r2a0gfn0unW0Fkj7e7404n;0Z0X1Im:2*0ohb1Y1T040%nl0h1r9z1r0~3832g`2l1`0~1e1#jrnl0b1rgJojf;h00~7`oen}3s1/np040w0$0?0o2Unzjo0`oEk^171/7.0-k^h-oXa5jh0m2T0C3Ijl0?g=7Hm:3F201.1:1=n7jVoTk5kS8pj#2*oa8Noen+0CoIp6n60YbBl:fgh,1{h!1`9jnmoVnCoYo:74o=1:221;2AaTo6o8k)j^o60Z0g0b0Fe j^o|muizpgi60$ft7=m/o4dxp4oJ1cpSof0;l=0g0Z0?e:oQ0P0ggKo)0r1fpjnBoX0soZo32W3+o?pro_iUpvl6py0sb?hxeDbcpGjbhz7cpO7gp33sp5qboHn60wh;0gh?hro!pfgU2Skj0Nh0g.1o0~739jo%0_jj8T0C0Oh:nmno1Z1#pp21o^pt5;2F2w2y1a2L0p0O0$18gJn nXmA1T6|3d7=oa8;9vn%0L0r9S7pb39vp|bwq/dH0.d:fb0$e4mTcdpzpBpDpHlY1apz2P9M9P7lq?7Rb38tf57xqZeJiQa{9P8?rb8`dH7U7W7Yo)900dpEdHj+o`dIe*fSa1a}l5pxhHf}b6jMlkedmVbg0Ep006garleqj6esmreveZf7morid#dgh9q5lMmZ3+e/m*9kj*lxrzfEiUlCmI0*rNbGaqrQrSivrmerq@rX1abAbCa5rwj6rymp1amvi!bQc0h5j6eKm(bnr0pCsajZsck9mjhql89^izbRgIpM57s06.bujG5;rWjZeu8Rexe:7!eBsqlJ2sssd?rBjyfvkPm-l%j4r|f|r6g6jbeEsR1~sTiGsulBswd-q6rCsXr-9gr/mAe-9vsZ5Vq8m?79n4771cm@0_0{0}04.