{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# Heap\n", "\n", "La structure *heap* ou [tas](https://fr.wikipedia.org/wiki/Tas_(informatique)) en fran\u00e7ais est utilis\u00e9e pour trier. Elle peut \u00e9galement servir \u00e0 obtenir les *k* premiers \u00e9l\u00e9ments d'une liste."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["
run previous cell, wait for 2 seconds
\n", ""], "text/plain": [""]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Un tas est peut \u00eatre consid\u00e9r\u00e9 comme un tableau $T$ qui v\u00e9rifie une condition assez simple, pour tout indice $i$, alors $T[i] \\geqslant \\max(T[2i+1], T[2i+2])$. On en d\u00e9duit n\u00e9cessairement que le premier \u00e9l\u00e9ment du tableau est le plus grand. Maintenant comment transformer un tableau en un autre qui respecte cette contrainte ?"]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": ["%matplotlib inline"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Transformer en tas"]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"data": {"text/plain": ["[12, 11, 5, 10, 7, 3, 1, 6, 4, 3, 2]"]}, "execution_count": 4, "metadata": {}, "output_type": "execute_result"}], "source": ["def swap(tab, i, j):\n", " \"Echange deux \u00e9l\u00e9ments.\"\n", " tab[i], tab[j] = tab[j], tab[i]\n", "\n", "\n", "def entas(heap):\n", " \"Organise un ensemble selon un tas.\"\n", " modif = 1\n", " while modif > 0:\n", " modif = 0\n", " i = len(heap) - 1\n", " while i > 0:\n", " root = (i-1) // 2\n", " if heap[root] < heap[i]:\n", " swap(heap, root, i)\n", " modif += 1\n", " i -= 1\n", " return heap\n", "\n", "ens = [1,2,3,4,7,10,5,6,11,12,3]\n", "entas(ens)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Comme ce n'est pas facile de v\u00e9rifer que c'est un tas, on le dessine."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Dessiner un tas"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAA0AAAAIICAIAAADIfRmgAABME0lEQVR4nO3dfXBc1X3/8XPu096rlaxd2U7N+FcmTTNtSoCEtE0LVkpNQv1AjfJU3DjttDOdBtcIx5VJCwQa48Rp6jgJk6EKzZQQOomT4kAQGAUoKaV13ZakcZoGSB+MkzJtbQm0et7V3ofz++P8fH+L/ICtlfbu2X2//vBIlrRz9u537/nsueecK5VSAgAAAOawsm4AAAAAzg8BDgAAwDAEOAAAAMMQ4AAAAAxDgAMAADAMAQ4AAMAwBDgAAADDEOAAAAAMQ4ADAAAwDAEOAADAMAQ4AAAAwxDgAAAADEOAAwAAMAwBDgAAwDAEOAAAAMMQ4AAAAAxDgAMAADAMAQ4AAMAwBDgAAADDEOAAAAAMQ4ADAAAwDAEOAADAMAQ4AAAAwxDgAAAADEOAAwAAMAwBDgAAwDAEOAAAAMMQ4AAAAAxDgAMAADAMAQ4AAMAwBDgAAADDEOAAAAAMQ4ADAAAwDAEOAADAMAQ4AAAAwxDgAAAADONk3YB6RVFk23bWrWhfcRw7jsFVRP1ki/pBPagf1MP0+pFKqazbAAAAgPNgavZUSkkpy+Xy4ODgli1bfN8niTaYlLJSqezfv3/btm1BEOhXJOtGnSvqJ3PUD+pB/aAeRtdPytQROH24x8fHi8XiqlWrHMcx9ImYS0oZRdHx48dLpVKhUDDrDUD9ZI76QT2oH9TD6PpJmToCpymlLrzwwqeeeqpYLPIGaDApZalUWrt2bZIkWbdlgaifDFE/qAf1g3q0QP2IFghwcRyvWLFi2bJlWbelHTmOE8exfgPoE5BZH2Kon2xRP6gH9YN6mF4/wvQAp4VhqJQydAjUUPpoh2EohIjjWJx8A2hmvRDUT+NRP6gH9YN6tEz9tEKAk1LqI27QcW8B6WGvVqtRFKXrsY17FaifTFA/qAf1g3q0Rv20QoBDhpRS5XK5Uqnob9M9dcx6GyAr1A/qQf2gHqbXDwEOdVFKTU1NzczM2LatP9PoL7JuF8xA/aAe1A/qYXr9mB3gWLmTOaVUqVTq7u72fd+2bcuyLMsyZUIo9ZM56gf1oH5QD6PrR7RGgDPiQLckKaVSamJiYmpqSinleZ7ruvptkHXTzgn1ky3qB/WgflAP0+tHcDN71Em/AaanpyuVShiGcRzrFVVZtwtmoH5QD+oH9TC9fghwqItSamZmplwuh2EYRVGSJAZVPzJH/aAe1A/qYXr9mB3gzDrWLUkpNTc3V61Waz++mPK6mNLOFkb9oB7UD+phdP0I0wMcmoHeR0d/djGo9NEkqB/Ug/pBPYyuH7MXMTSts8xOTUukBeau6qegXinrRrUC6gf1oH6wKFq7kFqgfghwS2JeTYdhaFmWbdun/uhM4ji2LCutsCiK0kdoNkmS1E4daM73gFIqSZLmPICnmlck+syi10YtoH7mPUKzoX4WXW2RzDt7cP7JhFn1k0qrJUkSfcspzXXdcykkfafRpq0czYj6ORMC3OILw7BUKk1NTfX09BQKBSml67pCiCRJpJQ//OEPhRDLly8/0w2MdTHVVnz6CE2ryT++RFHkOI5t282cY1K19VMsFnXj0650AfVT+wjNifpZRPPqp/bssYD6UUrVnsGa87lTP0thXiHNa/axY8fEWQtJCGHbdjNHt1ST189ZmFFJptA3x929e/eWLVuGhoa+//3vSymr1Wp/f/8jjzxiWValUhkeHt6/f/9ll102MTEhTjd+qz+vPP3006VSSQiRJMlLL73U398/NDRUrVZrPwY1iWaue9228fHxvr6+xx57TEppWZa+e3TWTTuNefXz7LPPCiEcxxkfH/+7v/s7IcQC6kcppR/h0KFDQogkSTJ8gqfVnK+F1gL1Mzo62t/f/+CDD4ZhuID6kVLGcdzf33/w4EHLsjj/nBez6ic1r5B+8IMfDA8Pb9u27YMf/OCOHTv+6I/+aGJi4uyFpM8zTzzxxPbt27/5zW+KpjzzaE3+WpwdAW7xjY6OXnLJJQMDA29729vGx8d/4zd+QwjxR3/0R8PDw0EQ3HDDDbfccsvs7Kw+FcpXEkL8wz/8w549e9773vdGUSSEiOP4yiuvFELceuutn/jEJ2zb1u+uppLOAG1OuVzu4MGDGzZsWL9+/RNPPOG6rmVZURSppnzrpvXT29tbLpc/97nP9fX1HThwQAjhOM6514/+hXK5PDg42NfXd//99wshmrADFtTPoqqtn+PHj//CL/yCEOLjH//47t27F3D+GR8ff9/73ieEuP3224eHh23bbsISon6WQlpIl19+uVJKl8eLL774zW9+M5fL3XDDDTfffPOZCsmyrJdeeum3fuu3Tpw4sWnTpqNHj0opyXCLjkuoi891Xb2wxbbtO+64w3Gcu+66a2ho6KMf/egv//Ive543NjaW3jR3bGysVCrpLaEty7rwwgvf8IY3eJ43ODioh6zvueeeK6644q677rr//vvvueeeSqXSbJdTHcfJ5XK+7/u+HwRBEATNc41An3RyuVx3d/f4+Pjjjz/+5JNP3n777f39/cuXL/c8rwnfumn96EkzGzZs+Pu//3t9SJVSURSdY/3oixe2bW/cuPHw4cPN86LMQ/0srrR+LMv67Gc/+yu/8it33XXXzp07T5w4IYQ49/rRz33Xrl2u66ZnsLVr1+pn3TxX5KmfJZIWUhzH11xzzTXXXCOE+MxnPvPiiy/6vh9FUalUOrWQhBBxHL/+9a+//fbbN2zY8IUvfOHJJ588duzYT/7kTzbzkzUUAW7x6bObruy5ubmVK1eGYXjVVVddf/31MzMzHR0dejKE/jjy3HPPHT58WH+uzeVyW7duLRaLP/MzP5PekW3FihXXXHNNHMfPPfdcoVDwPC+O4+aZWKCUGh0dffHFF+fm5iYnJ7u7u4Mg0DckqedhdY9i23Yul5udndXfLvjRpqen9WULx3GiKNq1a9fg4ODWrVs3b97sum6znVbS+tFDra997WtXrFiRDrs6juM4zrnXj5Ry3iM0Fepn0dXWz2233aaUmpycHB8fX758uTif+tG/MDc3p4tHn8FmZ2eDIGiep0z9LJ20kJRScRxHUVQul4eGhrZt2yaESGf1nVpIvu+/733vGxoa+uxnP7t169YtW7b80i/9UtNOoDQaAW5p6Sueruu+9NJLnufVVrA+xfT29vb29s77q3K5rE7OdX3ve98rhAjD8Omnn96xY0faMTeJJEmef/75UqnU1dXV1dUVBIHneYt1O7lSqfSDH/zg8ssvr/PNX6lU0uvR+hQzMjKyZ8+eiy++2Pf9ph3Y1/So26kDHq9aP6/6CM2A+llSrus6jrNv376vfvWrL7zwQu2PzrF+5p3Bmq2KqJ/GsCwrl8slSfLd735306ZNtT86bSHpu4v+y7/8i23b73znO5999tlVq1Y11cBtayDALS0ppf6Y4rruvLkj+ttDhw7N+wScy+Vqq1xvEr1mzZorr7yyr69Pn0wb/TTOzLbtt7/97W984xtXr159wQUX9PT0pIPq9RsdHT1w4ID+wFenvXv36g/BcRz39PRs3759586dSqkdO3Y0z3DmaZ3plHeO9XOWR2gG1M+S0ueKG2644YUXXti7d+++ffvSYjjH+jnLGawZUD+NoadzHDx48Od+7uf0liJps08tpCAI3ve+942Ojv78z//8tddeW61WP/3pT3/yk59sts6rBRDgltbMzIye1BmGoW3b886MQoiLLrroggsuSOegpGef9Dc9z7v99tt93//MZz4jhFjE09NimZmZmZyczOfz+iNaR0eH/hBcT27Qn9VKpdLs7GwURXod/oIfZ2pqSpw80WzatOnee+/Vl5NOnDjRzOEmddpGnmP9nOURmgT1s0Qsy3rkkUe6urp++Zd/ed++fa997WtvueWWFStWpNfWxTnUz8zMjN4Q7tQzWJOgfhpAJ7a//du//dmf/dl8Pl+tVtMAd2ohSSl933/Xu9711re+VQhRLBZHRkaybH3raro00AJqt1B6z3ve8+u//ut79+7dtWtXX19fsVgUQuiJBbrue3p6enp60r9Nr1yka5T+53/+57777nvmmWcmJyeTJNGP0FT0vgOac9KinED1pRB96qznBCqlrFQqV1999c6dO9etWyeEqFarei3Yglu4dE79RH7qyMe51M/ZH6F5UD+LK60f27afeOKJhx9++MiRIw899NDP/dzP5fN5cc7nH/0L73nPe973vvelZ7BCodBs4yjUzxKpPRE5jlMul//7v/973759ouZonKmQhBA//dM//Qd/8Ad33nnnN7/5zVtvvVUI0eTP10QEuMWn98URQszNzW3cuPEv//IvL7300re+9a333XefHohWSp04cUKfK/XuvvMeQUrZ3d2t50bs37+/UqlceeWVYRh2dXU988wzXV1dTCY4X8PDw1dddZU42UWd407imUjrJ9XR0VH77TnWT+3/z3sEnC8T66dare7du/fo0aOXXnrpm9/85oceesjzPHHO9aM76Wuuuab2DKZn4jf2CbUCg+onlRaSHp2dnZ3953/+5xUrVqS/cKZC0pun7Ny58/rrr7/00kvf9KY3vec97zHxRhTNj7fiYtKfMK677jr9red5SZJs2LDhe9/7nv50omu9o6Njz549uk9Nt1+qVSgUvv3tb+uPy/39/R/4wAfiONahrbOzUzT3FbGmog9UoVDQZ8906kZTLQRJzauf9BY0H/vYx/T/6JGP86of3WfPewScI9Prx/O84eHhsbExff7Rvex51c+pZzBOPufOrPpJzSsk3eaenp7nn3/e931x8nmdqZD0hdRisXj//ffr2qNslggBbjHpQt+4caP+Vr8NkiSZd+4LgmBgYED/zpmmN+mgJoTQ+xstfdtbmTp5I8Im/wg4r37S1qYFsID6mfcIWABD60dvACGlTM8/+ox0XvWj9xMhvdXDlPpJnfZEpKO//p9XPRGlk+F05VA2S4Rr0osvjuPaKUe1O3Kl/zlvitKp5m0DkVrsxrYFPZ0l61acq3n1I04WQO3/nFf9nPYRcO7MrR958ha6oo7zz2nPYDh3ZtVP6rQnonm/c5ZCqq09LBFG4Bbfqe/VU098rzqP5NT1qmgTi14/p30EtCrqB4tiKQoJi4sROAAAAMMQ4AAAAAxDgAMAADAMAQ4AAMAwBDgAAADDEOAAAAAMQ4ADAAAwDAEOi4DNflAP6gf1oH5QD3PrpxU28uUuBY2nj3Zr7M9O/TQe9YN6UD+oR8vUj/EBTkrped5pb8mMpaOPtuu6+gt5UtbtOm/UTyaoH9SD+kE9WqZ+jA9wYRiOjo6GYZjeqtnEl8E4+kbFk5OTURRZlmVZVnrYzTr+1E8mqB/Ug/pBPVqmfswOcI7j2La9Zs0aKWWSJEop/W/tACmWiJRSKRVFkeu6+v1g3IcY6idD1A/qQf2gHi1QP8LcAKePfmdn55EjR6anpycmJkZHR0dGRo4fPz4yMlIqlWZmZubm5uI4juM4SZKs29s6LMuybdu27Vwul8/nV65c2dXVZdu2/hBjyhuA+skK9YN6UD+oR2vUT8rUAKdZllUsFoMgyOVytm3rd4Vt277vT09P6zdAFEV8oFkU6XQB/cExl8t1dnYWCoUgCDzPc11XvwQGvQ2on0aifrJur9mon6zba7bWqx9heoATQujPKHoCgeu6uVyuo6MjjmPbtvUboHaBD++BBaudIiClTD/BaPo94DhO7WQCI1A/jUH9COqnDtSPoH7q0Kr1Y3aAk1JaluU4jud5vu/n8/lCoSCE0K9NGIZJkuhZBVm3tHXoY65PN0EQdHR0dHd35/N53/drP8Rk3cxzQv00HvWDelA/qEcr1Y8wPcAJIfT1bP1iRFEkhPA8r1wuV6vVKIqYE7qI0iHo2vNOEAT5fL6rqysIAv0G0GupTEH9NAz1k3VjzUb9ZN1Ys7Vk/Rgc4PTroScNuK7r+74QwnGcIAiq1ar++MIeiYsunSWgP8Toz45BEPi+73meQdMIqJ9MUD+oB/WDerRM/WgGBzhNX892XVcIkY6LRlFUO3uAN8Aiqv0cY9u24ziu6+p3gp4cakrpa9RPg1E/qAf1g3q0WP2YHeDSY+04TvpO0Ouu+eyypGo/x9g1zPr4Qv1khfpBPagf1KM16keYHuA0fbj1EhLbtueVPu+BRZfWd+3bwNxtxKmfBqN+UA/qB/VopfoxPsDVHnH9MjDs3DDpcPS8fw1C/WSI+kE9qB/UowXqx/gAp9Ue91NfA94Mi+hMJW5c6deifhqG+kE9qB/Uo8Xqp0UCnNZirw0ajPpBPagf1IP6wfkyacsTAAAACAIcAACAcQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYxsm6AQAAtKMoimzbzroV7SuOY8cxOAUZ3HQAAMxldHpoAaYff7NbDwCAWZRSUspyuTw4OLhlyxbf95VSWTeqvUgpK5XK/v37t23bFgSBfkWybtR5I8ABANBoc3NzN9100759+xzHIcA1mJQyiqLjx4//zu/8ThAEWTdngQhwAAA0mlLqwgsvfOqpp4rFIgGuwaSUpVJp7dq1SZJk3ZaFI8ABANBoSqk4jlesWLFs2bKs29KOHMeJ41gHOB2gjbuKSoADACAbYRgqpQydg2UofbTDMBRCxHEsTgY4zaAXggAHAEA2pJQ6MRiUG1pAetir1WoURel+Ima9CgQ4AADQdpRS5XK5Uqnob9NdRUyJcQQ4AADQdpRSU1NTMzMztm3rMTn9RdbtOlcEOAAAGo2Vp5lTSpVKpe7ubt/3bdu2LMuyLIMWNBDgAABoNIOCQkuSUiqlJiYmpqamlFKe57muq2Nc1k07V8Y0FAAAYLHoADc9PV2pVMIwjONYrwjOul3nigAHAADajlJqZmamXC6HYRhFUZIkBqU3QYADAKDxzMoKLUkpNTc3V61Wa4ffDHpdCHAAAKAd6X3g9NibQdFNYxEDAACY7yzLLNKsY+4iDN1y9UpZN+r8MAIHAMAS0rc9zboV5y29XYEQQimlrzPW/uhV01scx03+xJMkqZ36ZlaGYwQOAIClEkWR4zi2besxHlN2qQjDsFQqTU1N9fT0FItFKaXrukKIJEmklD/84Q+FEMuXL1+2bNlZHsS27ca0th6GDr8JRuAAAFgKOhOMj4/39fU99thjUkrLsvTd67Nu2tnou7zv3r17y5YtQ0NDzz77rBBidHS0v7//kUcesSyrUqkMDw/v37//sssum5iYEKe7EKnXBDz11FOPPvqoOHnP+CbU5K/F2RHgAAA4PVW3XC538ODBDRs2rF+//oknnnBd17KsKIqaPDqMjo5ecsklAwMDvb29L7300i/+4i8qpW677bavfe1rQRDccMMNt9xyy+zsrE5m8pX0I0gpb7zxxocfflgIkSRJlk/mrJr8hTgLAhwAAKfheZ6+dCgXxLIsKWUul+vu7pZSPv744xs3brzjjjtefvllx3E8z2vm6OC6rl6hqZT68Ic//I53vONP//RPP/rRjx4+fFgIEUXRSy+9lN79fWxs7OjRoy+88MLRo0ePHTsWhqFt23/7t3/77LPPvva1r83yabQ05sABAHAax44dO3r0aBzH9czlmp6e1pdNHceJomjXrl2Dg4Nbt27dvHmz67pNm+GUUlJKx3GUUm9/+9u/+MUvzs7OhmH4Yz/2Y0IIx3H0j/TQ2nPPPXf48GHbtuM4zuVyH/jAB4QQd99995vf/OapqamMn0nrIsABADDf6tWrV69ePTQ0VOfjVCqVKIqEEDoIxnE8MjKyZ8+eiy++2Pf9Zr62qFUqleuuu254ePjaa6/9/ve//61vfav2pzra9vb29vb21v7/gQMHent7L730Ur3cAUuBAAcAwP+nZ3H5vj8wMLAoD7h37149CBfHcU9Pz/bt23fu3KmU2rFjR/Ov0/R9/4EHHjhx4sSXvvSlJ5988sYbb/zKV74SBIH+qZ4Dd+jQodoRuN/+7d++++6777vvvj/+4z+OoqhcLqcXW7GIOKYAAJyGHjlbMH0VUl9D1EFn06ZN99577/Lly4UQJ06cMGIXXCnl0NDQW97yllWrVv3Gb/zGtm3bpqamgiCo3eb3oosuuuCCC6SUSinbtpMk+dd//dc1a9ZMTU2FYXjRRRf9/u//vt5OJetn01I4mgAAnEadgUMHOCllpVK5+uqrd+7cuW7dOiFEtVrVa1EXqZlLonZo8MILL3zwwQd37tw5NDT0pje9qaurSwihZ8jpANfT09PT01P75//+7/+eJMmHPvQhpdTv/d7vRVGkt5HDIiLAAQCwhIaHh6+66ipxcscKvaw160a9Cr3BmxCiWq3efPPN//RP//SmN71pdnZWbyMihFBKnThxQj8jvbtv+rdSSr3wVo81BkGg95bD4iLAAQCw+HSmKRQKOr2lq1mbduWppocGr7vuuvTbzs7Ov/qrvxobG8vlcvl8Xo8sdnR07Nmzp6OjQ7zyplsppdTu3bv11wy/LQUCHAAAS0XvtWHbdvOvV9B0Ozdu3Ki/1duFSCn1RdIkSXTCC4IgXeRxanpLF4I0rNltqKmvwQMAYDQppSnRrVbtfeh1Gjv1Xq6vusjD0HuMmoIROAAA8Aqnhs5Th9ledZFH80/1MxojcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAABoU+ZuVsdGvgAAZEOdlHVD2og+2vpfc9ObIMABAJAJKaXneae9EzyWjj7aruvqL+RJWbfrvBHgAADIQBiGo6OjYRim9xg1MUYYRyklpZycnIyiyLIsy7LSw27W8SfAAQDQaI7j2La9Zs0aKWWSJEop/W/tBT4sESmlUiqKItd1dZ4zcRCOAAcAQOPo9NDZ2XnkyJHp6emJiYnR0dGRkZHjx4+PjIyUSqWZmZm5ubk4juM4TpIk6/a2DsuybNu2bTuXy+Xz+ZUrV3Z1ddm2rQfhCHAAAOBVWJZVLBaDIMjlcrZt61Rn27bv+9PT0zrARVHEgNyiSKe76YHPXC7X2dlZKBSCIPA8z3Vd/RKYFeMIcAAAZECPsekJcK7r5nK5jo6OOI5t29YBrnaBKhluwWqnuEkp0xE4TWc4x3FqJ8MZgQAHAECjSSkty3Icx/M83/fz+XyhUBBC6GwRhmGSJHpWXNYtbR36mOu4HARBR0dHd3d3Pp/3fb92EC7rZp4rAhwAABnQ87F0mIiiSAjheV65XK5Wq1EUsaZhEdXuGJLm5iAI8vl8V1dXEAQ6wOm1wKYgwAEA0FA6T+hJb67r+r4vhHAcJwiCarWqh9/Y43fRpbPc9CCcHvsMgsD3fc/zjJsGR4ADACADej6W67pCiPS6XhRFtbPfCHCLqHYczrZtx3Fc19VJTi9uMCW6aQQ4AAAaLc0KjuOkSU7vG8LY25KqHYeza5g1/CYIcAAAZEXHBb0E0rbtedGNDLfo5q1ITZc1CNNuwyAIcAAAZKI2MegYwWXThkkvp8771yAEOAAAMlObG07NEIS5RXSmiGZcdNMIcAAAZKzFsgUawKQtTwAAACAIcAAAAMYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgn6wYAgKmiKLJtO+tWtK84jh3H4F6M+smW6fVjcNMBIFtGn/1bgOnH3/T2m87042926wGg8ZRSUspyuTw4OLhlyxbf95VSWTeqvUgpK5XK/v37t23bFgSBfkWybtS5on4yZ3T9pCR1gyak305Hjx4dGhoaGBiIosj0j0popKWuH/344+PjxWJx1apVjuNwIm0wKWUURcePHy+VSoVCwawOmPrJnNH1k6JTBICFUEpdeOGFTz31VLFYpANuMCllqVRau3ZtkiRZt2WBqJ8MtUD9CAIcACyMUiqO4xUrVixbtizrtrQjx3HiONYdsA5AZg2iUD/ZMr1+BAEOAOoRhqFSytBLMIbSRzsMQyFEHMfiZAesmfVCUD+N1zL1Q4ADgIWTUuozvkHn/RaQHvZqtRpFUbofhHGvAvWTidaoHwIcAMBISqlyuVypVPS36VIVs7phZMX0+iHAAQCMpJSampqamZmxbVuPqegvsm4XzGB6/RDgAGAhWDmYOaVUqVTq7u72fd+2bcuyLMsyZUI69ZM5o+tHEOAAYGEMOtG3JCmlUmpiYmJqakop5Xme67q6G866aeeE+smW6fUjuJk9AMBQugOenp6uVCphGMZxrFd0Zt0umMH0+iHAAQCMpJSamZkpl8thGEZRlCSJQb0vMmd6/RDgAGAhzDrXtySl1NzcXLVarR0+MeV1MaWdLczo+hEEOACAufQ+XnrsxKCuF03C6PphEQMAtKazTJNP+ypzJ9HrlqtXyrpRLYX6aXIEOAB4FUqpJEls2866Iefn1M41iqJz3HFe32hIa+aleUmS1E5das4+uAXqRykVRZFlWfpZnEtu03cadRynmUOeEfVzJgQ4ADgbHXps29af0Zs2yswThmGpVJqamurp6SkWi7pn0uktSZIf/ehHQojly5ef6U7qrus2srX1aPLhk9aoHymlLokkSaSUP/zhD8VZ60cIYdu2EZm1yevnLMyoJABoPH1OHx8f7+vre+yxx6SUlmXpu49n3bSz0YNnu3fv3rJly9DQ0LPPPitO9lJ33nnn7OxsFEXDw8P79++/7LLLJiYmRE0fpkcjKpXKTTfd1N/f/8EPfvAP//APH3vsMXHytt/Npplfi1aqn9HR0f7+/qGhIcuyKpXKmeonraI4jh944IH+/v6xsbGMn89ZNflrcXYEOACtTNUtl8sdPHhww4YN69evf+KJJ1zXtSwriqImP/WPjo5ecsklAwMDvb29cRxLKZ9++unf//3fD8PQ87wbbrjhlltumZ2d1bFMnmRZVnrBS3fD3/jGN15++eVMn8qrSGegN6cWqJ+RkZHLL79cCPHHf/zHDz30UBAEZ6qf1M033/zpT39aKfWWt7wlDXkZP6UzaNqGvSouoQJoWZ7npZd+FkBHmVwu193dPT4+/vjjjz/55JO33357f3//8uXLPc9r5lO/67p6hV0cx3oe0k033eQ4jud5QogoisbGxtK7d4+NjZVKJf18pZQ/8RM/sW/fPv2jiy+++F3vepcQojmv/TmOk8vlfN/3fT8IgiAImqedrVE/lmV98pOfXLNmzV133XXLLbc88MADfX19cRyftn6UUpZldXd3P/LII9/5znc6OjoOHDgQRVG2z6VVEeAAtKxjx44dPXo0juN65uJMT0/ry16O40RRtGvXrsHBwa1bt27evNl13abtg5VSUkrHccIwtG378ccfj6Lo//yf/zM7OxsEgeM4juMopZIkEUI899xzhw8ftm07juNcLrd161YhhGVZX/va117zmteIkzOfMn5Kp1BKjY6Ovvjii3Nzc5OTk93d3UEQ6Bsi1fOwOojYtp3L5WZnZ/W3C3400+tHCDE6Ovqa17ymUqn87u/+7jve8Y5SqdTT06Nn9Z22fq6//vpvfetbQRD827/927Jly5onUrcYAhyA1rR69erVq1cPDQ3V+TiVSkUPIeggGMfxyMjInj17Lr74Yt/3dQfWzHRQ++IXv/jggw9u3LhxXrjR3/b29vb29tb+f7VadV336aef/qmf+qmOjo5qtaqH7ppKkiTPP/98qVTq6urq6uoKgsDzvMVaM1sqlX7wgx9cfvnlSZLU84Cm148Q4pprrtm7d6/v+3ffffexY8dyuVz6ozPVTy6Xq1Qqa9eu3bx5c7FYTJc/YxFxQAG0Gj1W5Pv+wMDAojzg3r179SBKHMc9PT3bt2/fuXOnUmrHjh3Nv87Odd2/+Iu/0GsJS6VSqVTq7u5Oh9P0HKZDhw7NG4FzXXdmZuY///M/r7/+enGyn242tm2//e1vf+Mb37h69eoLLrigp6dnEVPC6OjogQMHtm3bVv9DGV0/YRj+2q/92le+8pWPfOQjR44ced3rXletVvP5vP7paetn27ZtruvmcrlDhw6tX7/+1ltvXblypR7Sy/SptBoCHICWVefkG93lTE1NiZMd1aZNm+69997ly5cLIU6cOGFKh/Tv//7vBw4cGB4eHhsbW79+/be//e2uri5Vs03rRRdddMEFF6RzmBzH0WNO//Ef/9HX1yeadQKcEGJmZmZycjKfz+dyuSRJOjo69CBcPS+Nft1LpZJesbvg0aPWqB+l1Msvv/zAAw8cP348juMf//Ef7+7uFicr57T1Mzc3Nzg4uH379te97nXr1q27/fbb77777iiKDNqbxggEOAAtq87xGN0BSykrlcrVV1+9c+fOdevWiZOXF5s202jp0E4Yhh/5yEc+9KEPvfTSS1dcccU3vvGNzs5OIYSe4aQ74J6enp6envRvddr4+te/vnnzZtu2m/n6l95aVnNOWpQApy/F6ideT4AzvX48zzt8+PC+ffu++tWvPvHEE3/wB3+QtvxM9TM5Obljx45Vq1a94x3v+N73vnfjjTcqczbAM0iTvicBoHkMDw9fddVV4uSOA67rNv/Yid67QXNdt7u727Ksnp6elStXpjcROnHihH5G89Yo6NsGHD58OAgC27Zr78qABTC6fqrV6qZNmz73uc+9+c1v/vmf//n3vve9ejLfmeonjuNly5YdPHjwN3/zN7u7uz/1qU+9+93vrnMhEU6LAAcAp6f7pEKhoHvftBNq2pWDmh7quO666/S3uq8VQuTz+W9961sdHR16ZKijo2PPnj0dHR3i5D5e6SPoS1133nmnnmLPla+FaY36sSxLKTU8PDw+Pl4oFNKxtDPVjx6tvOaaa/7rv/4riqJCoWDibcSMQIADgLNRJ29kaUonpNu5ceNG/W166UpKqS+eakEQpIs8Tjsg1ITLTk1kev2kl48LhYKoKZWz10+SJLrY6lzDi7PgsALA2ejpUFm34rzFcXzqza/mjf2cfZGHvpHA4reszbRM/ZxaDGepHz1ux9S3JcUIHAC0oNOGhnkjJWefm9/887SwdE6tn1PrgfrJFtEYAADAMAQ4AAAAwxDgAAAADEOAAwAAMAwBDgAAwDAEOAAAAMMQ4AAAAAxDgAMAGIz9xlAPc+uHjXwBYOHUSVk3pI3oo63/Nbf31aifxmuZ+iHAAcACSSk9z5t3J3gsNX20XdfVX8iTsm7XeaN+MtEy9UOAA4AFCsNwdHQ0DMP0no8mdgPGUUpJKScnJ6MosizLsqz0sJt1/KmfTLRM/RDgAGAhHMexbXvNmjVSyiRJlFL639oLNFgiUkqlVBRFruvq/ti4QRTqJ0MtUD+CAAcA50uf/Ts7O48cOTI9PT0xMTE6OjoyMnL8+PGRkZFSqTQzMzM3NxfHcRzHSZJk3d7WYVmWbdu2bedyuXw+v3Llyq6uLtu29SCKKR0w9ZOV1qifFAEOABbCsqxisRgEQS6Xs21b98q2bfu+Pz09rTvgKIoYUFkU6XQlPXCVy+U6OzsLhUIQBJ7nua6rXwKDumHqp5Far34EAQ4AFkyPkegJTK7r5nK5jo6OOI5t29YdcO0CQ/rgBaudoiSlTEdQNN0HO45TO5nJCNRPY7Rq/RDgAGAhpJSWZTmO43me7/v5fL5QKAghdN8QhmGSJHpWU9YtbR36mOu4EwRBR0dHd3d3Pp/3fb92ECXrZp4T6qfxWql+BAEOABZMz6fRnUEURUIIz/PK5XK1Wo2iiDnpi6h2x4c09wRBkM/nu7q6giDQHbBey2kK6qdhWrJ+CHAAcN50f6AnLbmu6/u+EMJxnCAIqtWqHj5hj9ZFl85S0oMoeuwqCALf9z3PM2gaE/WTiZapH40ABwALpOfTuK4rhEivy0RRVDt7iQ54EdWOo9i27TiO67q6J9aT003pejXqp8FarH4IcACwEOm53nGctCfW+z4wdrKkasdR7BpmDZ9QP1lpjfoRBDgAqIc+3eslbLZtz+t66YMX3bwVhem09NofGYT6abBWqh8CHAAsUO0ZX3cDXPZqmPRy2Lx/DUL9ZKgF6ocABwB1qT3vn9oH0BkvojN1scZ1vbWon4ZpsfohwAHAImixvgENRv3gfJm05QkAAAAEAQ4AAMA4BDgAAADDEOAAAAAMQ4ADAAAwDAEOAADAMAQ4AAAAwxDgAAAADEOAAwAAMAwBDgAAwDAEOAAAAMMQ4AAAAAxDgAMAADAMAQ4AAMAwBDgAAADDEOAAAAAMQ4ADAAAwDAEOAADAMAQ4AAAAwxDgAAAADEOAAwAAMAwBDgAAwDAEOAAAAMMQ4AAAAAzjZN0AAADaURRFtm1n3Yr2Fcex4xicggxuOgAA5jI6PbQA04+/2a0HAMAsSikpZblcHhwc3LJli+/7SqmsG9VepJSVSmX//v3btm0LgkC/Ilk36rwR4AAAaLS5ubmbbrpp3759juMQ4BpMShlF0fHjx3/nd34nCIKsm7NABDgAABpNKXXhhRc+9dRTxWKRANdgUspSqbR27dokSbJuy8IR4AAAaDSlVBzHK1asWLZsWdZtaUeO48RxrAOcDtDGXUUlwAEAkI0wDJVShs7BMpQ+2mEYCiHiOBYnA5xm0AtBgAMAIBtSSp0YDMoNLSA97NVqNYqidD8Rs14FAhwAAGg7SqlyuVypVPS36a4ipsQ4AhwAAGg7SqmpqamZmRnbtvWYnP4i63adKwIcAACNxsrTzCmlSqVSd3e37/u2bVuWZVmWQQsaCHAAADSaQUGhJUkplVITExNTU1NKKc/zXNfVMS7rpp0rYxoKAACwWHSAm56erlQqYRjGcaxXBGfdrnNFgAMAAG1HKTUzM1Mul8MwjKIoSRKD0psgwAEA0HhmZYWWpJSam5urVqu1w28GvS4EOAAA0I70PnB67M2g6KYR4AAAwP9zXlHGxNyj6eUj6pWybtT5IcABALCE9G1Ps27FuUrvUqAppWrv+B7Hsb4J1Wl/+VRKKX2BcimaWr8kSWqnvpmV4dhGBACApRJFkeM4tm3rMZ4m36UiDMNSqTQ1NdXT01MsFnXj04gWx7Ft27Zt629LpdLY2FhXV1exWHRd97QPKKU804+ahKHDb4IROAAAloLOBOPj4319fY899piU0rIsfff6rJt2Gnpcbffu3Vu2bBkaGnr22WeFEI7jjI+PHzp0SAgRRZFt21//+tf7+/v1lP/vf//7Q0NDW7Zs2b17t36EeVckkyR56aWX+vv7h4aGqtVqE47DNedrcY4IcAAAnJ6qWy6XO3jw4IYNG9avX//EE0+4rmtZVhRFzRkdRkdHL7nkkoGBgd7e3nK5/LnPfa6vr+/+++8XQkgpDxw48Kd/+qdJkvT19Ukp3/a2tw0MDFxyySWjo6P6z+UrxXF85ZVXCiFuvfXWT3ziE7Zt115+bRLN+UKcCwIcAACn4XmevgIoF8SyLCllLpfr7u6WUj7++OMbN2684447Xn75ZcdxPM9rwujguq5emFmtVm3b3rBhw4//+I/ry76lUmnbtm1f+9rXBgcHX3755a997WtKKf2b+iJpkiTHjh07evToCy+88B//8R+Tk5Nf/OIXL7/88rvuuusjH/nI3//931cqlSa/gmwW5sABAHAaOo7oiV8LfpDp6Wl9bdFxnCiKdu3aNTg4uHXr1s2bN7uu22wZTiklpXQcRw+Vvfa1r12xYkW1WhVCJEni+76Od2vWrBkeHn7ve9+rZ8jpZxFF0cMPPzw3N2fbdhzH69atW7169caNG+M4fu655wqFgud5dR5M1CLAAQAw3+rVq1evXj00NFTn41QqlSiKxMkVAHEcj4yM7Nmz5+KLL/Z9v3aBZxPSY2zpIgZ9UdhxnJmZma6urnm/7Pv+Bz/4wdr/edOb3iSECMPw6aef3rFjR3qreCwKAhwAAP+fziu+7w8MDCzKA+7du1cPwsVx3NPTs3379p07dyqlduzY0eTDUfO2CNH3etcZ7tTZbJVK5c///M/TEbg1a9a89a1vrVQqb3vb26688sq+vr4wDJt8RapZCHAAAJyGHjlbMH05cmpqSgihF2Bu2rTp3nvvXb58uRDixIkTZ99BrUmkV0iVUhMTE/pJVavVzs7Oeb/pOM61116bJIn+k66uLtd1b7vtNt/3P/OZz+hfyOAJtC6OJgAAp1Fn4NBZR0pZqVSuvvrqnTt3rlu3TgihZ/0353T+U0cE9Y4hQohCoXDppZd+7GMf27Vr19DQ0He/+139BNM/sW37J37iJ2r/9n//93/vu+++Z555ZnJyMkmSYrHYmGfRJghwAAAsoeHh4auuukqc3LFCL2vNulGnNzExMe9/Ojo69Be2bT/55JObN2++9NJLv/CFL6xatapSqfi+n/5J7Xa4URS5rvvlL3+5UqlceeWVYRh2dXU988wzXV1dOvY17Bm1MAIcAACLT8eUQqGg01u6ALM5J/LrEcHrrrsu/Va39mMf+1j6P47jfP3rXx8bG+vp6RFCeJ4370/SZKbnuvX393/gAx/QY3hSSn3VlfS2WAhwAAAsFX1Dgto7UDUn3byNGzfWfiuE8H1ff6GXL0gpe3p6kiSxLEtnvlP/JOX7fvrnWHQEOAAAlkrtLLHmpxdb1DZYjxfqYTP977w7up76J7VqhxsZe1tcBDgAACDE6XLYqanr1L1FzvKAhLal04yrYAAAAHAWBDgAAADDEOAAAAAMQ4ADAAAwDAEOAADAMAQ4AAAAwxDgAAAADEOAAwAAbcrcnerYyBcAgGyok7JuSBvRR7v2DhOGIsABAJABKaXneVJKo2OEcfTRdl03vT+YoS8BAQ4AgAyEYTg6OhqGYXp3URNjhHGUUlLKycnJKIosy7IsKz3sZh1/AhwAAI3mOI5t22vWrJFSJkmilNL/1l7gwxKRUiqloihyXVfnORMH4QhwAAA0jk4PnZ2dR44cmZ6enpiYGB0dHRkZOX78+MjISKlUmpmZmZubi+M4juMkSbJub+uwLMu2bdu2c7lcPp9fuXJlV1eXbdt6EI4ABwAAXoVlWcViMQiCXC5n27ZOdbZt+74/PT2tA1wURQzILYp0upse+Mzlcp2dnYVCIQgCz/Nc19UvgVkxjgAHAEAG9BibngDnum4ul+vo6Ijj2LZtHeBqF6iS4RasdoqblDIdgdN0hnMcp3YynBEIcAAANJqU0rIsx3E8z/N9P5/PFwoFIYTOFmEYJkmiZ8Vl3dLWoY+5jstBEHR0dHR3d+fzed/3awfhsm7muSLAAQCQAT0fS4eJKIqEEJ7nlcvlarUaRRFrGhZR7Y4haW4OgiCfz3d1dQVBoAOcXgtsCgIcAAANpfOEnvTmuq7v+0IIx3GCIKhWq3r4jT1+F106y00PwumxzyAIfN/3PM+4aXAEOAAAMqDnY7muK4RIr+tFUVQ7+40At4hqx+Fs23Ycx3VdneT04gZToptGgAMAoNHSrOA4Tprk9L4hjL0tqdpxOLuGWcNvggAHAEBWdFzQSyBt254X3chwi27eitR0WYMw7TYMggAHAEAmahODjhFcNm2Y9HLqvH8NQoADACAztbnh1AxBmFtEZ4poxkU3jQAHAEDGWixboAFM2vIEAAAAggAHAABgHAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGcbJuAJClKIps2866Fe0rjmPHMfgsRP1ky/T6AepB6aOtcfbPlunH3/T2m47jj3ZG9aMdKaWklOVyeXBwcMuWLb7vK6WyblR7kVJWKpX9+/dv27YtCAL9imTdqHNF/WTO6PoBFoXkvIMmpE/HR48eHRoaGhgYiKJocT9q68cfHx8vFourVq1yHIc3QoNJKaMoOn78eKlUKhQKZnXA1E/mjK4fYFEwAof2pZS68MILn3rqqWKxSAfcYFLKUqm0du3aJEmybssCUT8ZaoH6AepEgEP7UkrFcbxixYply5Zl3ZZ25DhOHMe6A9YByKxBFOonW6bXD1AnAhzaXRiGSikuwTSSPtphGAoh4jgWJztgzawXgvppvFaqH2DBCHBod1JKfcbnvN9I6WGvVqtRFKX7QRj3KlA/mWiZ+gEWjAAHIDNKqXK5XKlU9LfpUhW6YZwL6gftjAAHIDNKqampqZmZGdu29ZiK/iLrdsEM1A/aGQEO7YuVg5lTSpVKpe7ubt/3bdu2LMuyLFMmpFM/mTO6foA6EeDQvjjRZ0tKqZSamJiYmppSSnme57qu7oazbto5oX6yZXr9AHWi0AFkRnfA09PTlUolDMM4jvWKzqzbBTNQP2hnBDgAmVFKzczMlMvlMAyjKEqShN4X5476QTsjwKF9ca7PnFJqbm6uWq3WDp+Y8rqY0s4WZnT9AHUiwAHIkt7HS4+d0PXifFE/aFssYgCa11mmyad9lbmT6HXL1Stl3aiWQv0ALYwAh7aglEqSxLbtrBtyfmo7V6VUFEWWZeln8ar9bpIk+i5DQgjXdZeukXVKkqR26lJz9sEtUD9RFOljq9dpnktu03cadRynmUOeEfUDLAUCHFpfFEWO49i2rT+jm7LLQBiGpVJpamqqp6enWCxKKdMcppT64Q9/KIRYvnz5me6krvfEalhr69HkwyetUT/pXQqEEEmS/OhHPxJnrR8hhG3bRmTWJq8fYImYcSYCFkaf08fHx/v6+h577DEppWVZ+u7jWTftbPRdunfv3r1ly5ahoaFnn302SZKRkZH+/v6HHnqoWq1WKpXh4eH9+/dfdtllExMT4pUXkvTA29/8zd/ceuut/f39N910k77XUHM+6+ZsldYa9fP888+Xy+WPf/zj27dvv+GGG4aHh6MoOkv96OHGOI4feOCB/v7+sbGxrJ/Q2TT5awEsHQIcmp2qWy6XO3jw4IYNG9avX//EE0+4rmtZVnpFqWmNjo5ecsklAwMDvb29SZKsXbtWCHHbbbd94hOfCILghhtuuOWWW2ZnZ3VckzX0qMnDDz/8+c9/PoqiarWa8TN5NekM9OZkev1cccUVtm1/+MMfHh8f11dFPc87S/1oN99886c//Wml1Fve8pY05GX9nE6vaRsGLCkuoaKpeZ5Xe+nwfOm5O7lcrru7e3x8/PHHH3/yySdvv/32/v7+5cuXe57XzKd+13X1Cjvbtu+5554rrrjirrvuuv/++++5555yuey67tjYWHpdbGxsrFQq6b3ppZSrVq3613/914MHD/7iL/5i+oDNOZPJcZxcLuf7vu/7QRAEQdA81yhbo34sy3rkkUd+9Vd/9S/+4i/0j5RScRyfqX4sy+ru7n7kkUe+853vdHR0HDhwIIqi7J4HgNMjwKGpHTt27OjRo3Ec1zMXZ3p6Wl/2chwniqJdu3YNDg5u3bp18+bNrus2bR+so5jjOHEcr1ix4pprronj+LnnnisUCrlczrIsx3GUUkmSCCGee+65w4cP27Ydx3EQBO9+97uff/75F1988cEHH3zb2962adOmJEmaJxillFKjo6Mvvvji3Nzc5ORkd3d3EAT6hkj1PKwOIrZt53K52dlZ/e2CH830+hFCDA8Pv+Y1r/mTP/mTEydO3HHHHV1dXY7jnKl+crnc9ddf/61vfSsIgn/7t39btmxZE1YOAAIcmtfq1atXr149NDRU5+NUKhU9hKCDYBzHIyMje/bsufjii33f1x1YM0uS5D3veY8QIgzDp59+eseOHbUdqs46vb29vb296X/Ozs7Ozs5+6Utfuvbaa9///ve/8MILy5cv1z1649t/FkmSPP/886VSqaurq6urKwgCz/MW63aWpVLpBz/4weWXX15neDW9foQQP/mTP/mJT3ziz/7sz7761a9KKfft25dWwmnrRwiRy+UqlcratWs3b95cLBb1So4Mmg7gDHhDohnp3sX3/YGBgUV5wL179+pBlDiOe3p6tm/fvnPnTqXUjh07mn+dnVIqDMNqtbpmzZorr7yyr6+vWq16nqd/qucwHTp0qHYEZdu2bWNjY7rT/c53vvOxj33szjvvDMOw2fYTsW377W9/+xvf+MbVq1dfcMEFPT09i5gSRkdHDxw4sG3btvofyuj6CcPw1ltv/dCHPuS6bl9f30//9E9/+MMf7unp0WOHZ6of13VzudyhQ4fWr19/6623rly5sgk/AADtjACHplbn5Bvd5UxNTYmTHdWmTZvuvffe5cuXCyFOnDhhRIekr4redtttvu9/5jOfEULUphz9FC666KILLrggncM0Nzf3Z3/2Z/39/UKIJEma+WnOzMxMTk7m8/lcLpckSUdHhx6Eq6fN+nUvlUqzs7NRFC149Kg16seyrEcffbS7u7u3t3dycnJem89UP4ODg9u3b3/d6163bt2622+//e67746iqNk+AADtjACHplbneIzugKWUlUrl6quv3rlz57p164QQ1WpVryVcpGYuiXRoJwiC//3f/73vvvueeeaZycnJJEkKhYL+UbrJak9PT09PT/q3k5OTN95446pVq3p7ex966KEjR47oKVwNfxKvTm9NrDknLUqA05di9bOuJ8CZXj+2bT/22GMPPfTQv/zLv9xyyy3vfOc7i8WiEELPkDtT/ezYsWPVqlXveMc7vve97914443KnA3wgDbRjCd0YNENDw9fddVV4uSOA67rNv/Yid67QQihlPryl79cqVSuvPLKMAy7urr+6Z/+admyZUmSnDhxQj+j2mG2OI6XLVv26KOPvv/97y8Wi5///OdXrVpV50KQNmd0/VSr1b17977wwguXXnrp5Zdf/tnPflbfVUIpdZb6OXjw4G/+5m92d3d/6lOfeve73039AM2GAIdWpvukQqGge9+0E2ralYOaHuq47rrr9LdKqf7+/g984ANxHOsxoa6uLiFEPp/fs2dPR0eHOLmPl/59Pdq0cePGF198MYoiPVxH77sArVE/lmV5nvfoo4+OjY3pYTbd/o6OjrPUzzXXXPNf//Vfun5MvI0Y0PIIcGh96uSNLE3phHQ7N27cqL+1LEtvkzbv14IgSBd5nDoglCRJZ2en/oKLX/UwvX70diFSyjS96WqhfgCj8bZE60tvTmCWOI7Tu9GLV96RIv3PsyzysCxL/zK9b51aoH50PtOVM+8O92f6c+oHaHKMwAFNal5oOO2kq7PPzW/+eVpYOqeGzlPrgfoBzMVHKwAAAMMQ4AAAAAxDgAMAADAMAQ4AAMAwBDgAAADDEOAAAAAMQ4ADAAAwDAEOQMbYbwz1oH7QntjIF+3u1NsbYKnpo33qjQFMRP00XivVD7BgBDi0NSml53m1d/JGA+ij7bqu/kKelHW7zhv1k4mWqR+gHgQ4tLUwDEdHR8MwTO/5SDfQAPp+6pOTk1EUWZZlWVZ62M06/tRPJlqmfoB6EODQvhzHsW17zZo1UsokSZRS+t/aCzRYIlJKpVQURa7r6v7YuEEU6idDLVA/QJ0IcGhH+uzf2dl55MiR6enpiYmJ0dHRkZGR48ePj4yMlEqlmZmZubm5OI7jOE6SJOv2tg7Lsmzbtm07l8vl8/mVK1d2dXXZtq0HUUzpgKmfrLRG/QCLggCH9mVZVrFYDIIgl8vZtq17Zdu2fd+fnp7WHXAURQyoLIp0upIeuMrlcp2dnYVCIQgCz/Nc19UvgUHdMPXTSK1XP0CdCHBoa3qMRE9gcl03l8t1dHTEcWzbtu6AaxcY0gcvWO0UJSllOoKi6T7YcZzayUxGoH4ao1XrB6gHAQ7tS0ppWZbjOJ7n+b6fz+cLhYIQQvcNYRgmSaJnNWXd0tahj7mOO0EQdHR0dHd35/N53/drB1GybuY5oX4ar5XqB6gTAQ5tTc+n0Z1BFEVCCM/zyuVytVqNoog56YuodseHNPcEQZDP57u6uoIg0B2wXstpCuqnYVqyfoB6EODQpnR/oCctua7r+74QwnGcIAiq1aoePmGP1kWXzlLSgyh67CoIAt/3Pc8zaBoT9ZOJlqkfoH4EOLQ1PZ/GdV0hRHpdJoqi2tlLdMCLqHYcxbZtx3Fc19U9sZ6cblbXS/00WIvVD1APAhzaV3qudxwn7Yn1vg+MnSyp2nEUu4ZZwyfUT1Zao36AOhHg0O706V4vYbNte17XSx+86OatKEynpdf+yCDUT4O1WP0AC0aAQ1urPePrboDLXg2TXg6b969BqJ8MtUD9APUgwAGvOO+f2gfQGS+iM3WxRne91E/DtGT9AAtDgAP+H/oG1IP6AdBIbJkDAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYxsm6AQBgqiiKbNvOuhXtK45jx6EXQ5ui9AFggUgP2eL4o51R/QBwfpRSUspyuTw4OLhlyxbf95VSWTeqvUgpK5XK/v37t23bFgSBfkWybhTQUJLzDoAWo7vzo0ePDg0NDQwMRFG0uEM1+vHHx8eLxeKqVascx+FE2mBSyiiKjh8/XiqVCoUCAQ5tiBE4AFgIpdSFF1741FNPFYtFAlyDSSlLpdLatWuTJMm6LUA2CHAAsBBKqTiOV6xYsWzZsqzb0o4cx4njWAc4HaAZhENbIcABwMKFYaiU4hJeI+mjHYahECKOY3EywGm8EGgTBDgAWDgppU4M5IZGSg97tVqNoijdT4RXAe2DAAcAMJJSqlwuVyoV/W26VIUYh3ZAgAMAGEkpNTU1NTMzY9u2HpPTX2TdLqARCHAAsBCsPM2cUqpUKnV3d/u+b9u2ZVmWZbGgAW2CAAcAC0FQyJaUUik1MTExNTWllPI8z3VdHeOybhrQCBQ6AMBIOsBNT09XKpUwDOM41iuCs24X0AgEOACAkZRSMzMz5XI5DMMoipIkIb2hfRDgAGAhyAqZU0rNzc1Vq9Xa4TdeF7QJAhwAwFR6Hzg99kZ0Q1thEQMAtKazLLNIs465izB0y9UrZd0ooHEYgQOAV6Fve5p1K85bersCLQxDfeOv9Eevmt70dcmlbWV9kiSpnfrW5K0FFhEjcABwNlEUOY5j27Ye4zFll4owDEul0tTUVE9PT7FYFEK4rqt/lCTJj370IyHE8uXLly1bdto/16nItu2GNXjBGH5DezLjTAQAjaczwfj4eF9f32OPPSaltCwrHcRqWvou77t3796yZcvQ0ND3v/99IcT09PTNN99888036wWbw8PD+/fvv+yyyyYmJsTpLkRalmXb9tNPP10qlUQTj2w1bcOApcYIHIBWVs/wjP6rXC538ODBhx9+eN26dQMDA7/yK78ihIiiqMmjw+jo6CWXXDIwMKDb+dGPfvTJJ5+M4/jEiRP33HPPDTfcEMfxXXfdpS8Nn3ot9R/+4R/++q//+s4773z++eczaP35aPIXAlgijMABaFme50kpXdeVC2JZlpQyl8t1d3dLKR9//PGNGzfecccdL7/8suM4nuc1c3RwXVev0FRKjY6O3n333f/8z//83e9+99JLL52bm4uiSD8L/ctjY2NHjx594YUXjh49euzYsTiO3/CGN6xfv97zPCOuogJtiBE4AC3r2LFjR48ejeO4nhQyPT2tL5s6jhNF0a5duwYHB7du3bp582bXdZs2wymlpJQ6ou3bt2/NmjUPPvjgP/7jP+7du1f/guM4SqkkSYQQzz333OHDh23bjuM4l8tt3bq1WCz+zM/8THprUQDNhgAHoDWtXr169erVQ0NDdT5OpVKJokgIoYNgHMcjIyN79uy5+OKLfd/XAajJKaVOnDjx3//9348++mgcx/v27Uuvmepo29vb29vbO++vyuUy6Q1oWgQ4AK1GpxPf9wcGBhblAffu3asH4eI47unp2b59+86dO5VSO3bsMOIKY7lcrlQqN95442/91m9dfPHFH/7wh3t6enQ403PgDh06NG8ELpfLmbtFHNAOCHAAWpYeOVswfRVyampKnAw6mzZtuvfee5cvXy6EOHHihCkR561vfeuKFSuEEJ7nzc3N1e5pp5/CRRdddMEFF0gp9T4p6dw4U54g0IYIcABaVhpEFkYHOCllpVK5+uqrd+7cuW7dOiFEtVp1XbfJN4RLhwaVUr/2a7/2+te//vrrr//rv/7r17/+9Z2dnUIIPUNOR7Senp6enp70b9Mrp3UmYABLhwAHAK9ieHj4qquuEieTjV7WmnWjXoXe4E0IMTc357ru4ODgFVdc8dJLLz388MNBEIiTE+P0M0qS5NRnJKXUy28b3HIA54IABwCnp7NLoVDQ6S1dzdrkU/v10OB1112nv/U8z7Ksa6+99pd+6Zccx+ns7NQjix0dHXv27Ono6BCn3HRLKxQK3/72t/P5vOBaKtB8CHAAcDZ6rw3bto1YryBOXjzduHGj/lbnuSRJCoWC/kL/TxAE6SKP0+YzKaW+2AqgCTX1HA4AyJyU0pToViuO49rFCnpHt3n3cn3VKW5NPtYItDNG4ACgBZ0aOk8dZnvVRR5cOQWaFiNwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAwGBsVof2xEa+ALBw6qSsG9JG9NHW/5Le0LYIcACwQFJKz/NOeyd4LB19tF3X1V/Ik7JuF9BQBDgAWKAwDEdHR8MwTO8xSoxoAKWUlHJycjKKIsuyLMtKDzvHH+2DAAcAC+E4jm3ba9askVImSaKU0v/WXuDDEpFSKqWiKHJdV+c5BuHQbghwAHB+dHro7Ow8cuTI9PT0xMTE6OjoyMjI8ePHR0ZGSqXSzMzM3NxcHMdxHCdJknV7W4dlWbZt27ady+Xy+fzKlSu7urps29aDcAQ4tBUCHAAshGVZxWIxCIJcLmfbtk51tm37vj89Pa0DXBRFDMgtinS6mx74zOVynZ2dhUIhCALP81zX1S8BMQ7tgwAHAAukx9j0BDjXdXO5XEdHRxzHtm3rAFe7QJUMt2C1U9yklOkInKYznOM4tZPhgJZHgAOAhZBSWpblOI7neb7v5/P5QqEghNDZIgzDJEn0rLisW9o69DHXcTkIgo6Oju7u7nw+7/t+7SBc1s0EGoEABwALpOdj6TARRZEQwvO8crlcrVajKGJNwyKq3TEkzc1BEOTz+a6uriAIdIDTa4GBdkCAA4DzpvOEnvTmuq7v+0IIx3GCIKhWq3r4jT1+F106y00PwumxzyAIfN/3PI9pcGgrBDgAWCA9H8t1XSFEel0viqLa2W8EuEVUOw5n27bjOK7r6iSnFzcQ3dA+JCcXAFiYdIwtrsHY21KrHYezazD8hrZCgAOABaodY0uXLLDydEnNW5GaLmsQNeNzWbYPaBQCHADUpTbGcdm0YWrjGtENbYgABwCL4EznUs6xi+hMEY3ohjZEgAMAADAMW+YAAAAYhgAHAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAACAYQhwAAAAhiHAAQAAGIYABwAAYBgCHAAAgGEIcAAAAIYhwAEAABiGAAcAAGAYAhwAAIBhCHAAAACGIcABAAAYhgAHAABgGAIcAACAYf4vas93uLHRSe4AAAAASUVORK5CYII=\n", "text/plain": [""]}, "execution_count": 5, "metadata": {}, "output_type": "execute_result"}], "source": ["from pyensae.graphhelper import draw_diagram\n", "\n", "def dessine_tas(heap):\n", " rows = [\"blockdiag {\"]\n", " for i, v in enumerate(heap):\n", " if i*2+1 < len(heap):\n", " rows.append('\"[{}]={}\" -> \"[{}]={}\";'.format(\n", " i, heap[i], i * 2 + 1, heap[i*2+1]))\n", " if i*2+2 < len(heap):\n", " rows.append('\"[{}]={}\" -> \"[{}]={}\";'.format(\n", " i, heap[i], i * 2 + 2, heap[i*2+2]))\n", " rows.append(\"}\")\n", " return draw_diagram(\"\\n\".join(rows))\n", "\n", "ens = [1,2,3,4,7,10,5,6,11,12,3]\n", "dessine_tas(entas(ens))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le nombre entre crochets est la position, l'autre nombre est la valeur \u00e0 cette position. Cette repr\u00e9sentation fait appara\u00eetre une structure d'arbre binaire."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Premi\u00e8re version"]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["1 [1]\n", "2 [2, 1]\n", "3 [3, 2, 1]\n", "4 [3, 3, 1, 2]\n", "5 [4, 3, 1, 3, 2]\n", "6 [5, 4, 3, 3, 2, 1]\n", "7 [5, 6, 3, 4, 2, 3, 1]\n", "8 [5, 7, 3, 6, 2, 3, 1, 4]\n", "9 [5, 10, 3, 7, 2, 3, 1, 6, 4]\n"]}], "source": ["def swap(tab, i, j):\n", " \"Echange deux \u00e9l\u00e9ments.\"\n", " tab[i], tab[j] = tab[j], tab[i]\n", "\n", "\n", "def _heapify_max_bottom(heap):\n", " \"Organise un ensemble selon un tas.\"\n", " modif = 1\n", " while modif > 0:\n", " modif = 0\n", " i = len(heap) - 1\n", " while i > 0:\n", " root = (i-1) // 2\n", " if heap[root] < heap[i]:\n", " swap(heap, root, i)\n", " modif += 1\n", " i -= 1\n", "\n", "\n", "def _heapify_max_up(heap):\n", " \"Organise un ensemble selon un tas.\"\n", " i = 0\n", " while True:\n", " left = 2*i + 1\n", " right = left+1\n", " if right < len(heap):\n", " if heap[left] > heap[i] >= heap[right]:\n", " swap(heap, i, left)\n", " i = left\n", " elif heap[right] > heap[i]:\n", " swap(heap, i, right)\n", " i = right\n", " else:\n", " break\n", " elif left < len(heap) and heap[left] > heap[i]:\n", " swap(heap, i, left)\n", " i = left\n", " else:\n", " break\n", "\n", "\n", "def topk_min(ens, k):\n", " \"Retourne les k plus petits \u00e9l\u00e9ments d'un ensemble.\"\n", " \n", " heap = ens[:k]\n", " _heapify_max_bottom(heap)\n", " \n", " for el in ens[k:]:\n", " if el < heap[0]:\n", " heap[0] = el\n", " _heapify_max_up(heap)\n", " return heap\n", "\n", " \n", "ens = [1,2,3,4,7,10,5,6,11,12,3]\n", "for k in range(1, len(ens)-1):\n", " print(k, topk_min(ens, k))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## M\u00eame chose avec les indices au lieu des valeurs"]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["1 [0] [1]\n", "2 [1, 0] [2, 1]\n", "3 [2, 1, 0] [3, 2, 1]\n", "4 [10, 2, 0, 1] [3, 3, 1, 2]\n", "5 [5, 10, 0, 2, 1] [4, 3, 1, 3, 2]\n", "6 [6, 5, 2, 10, 1, 0] [5, 4, 3, 3, 2, 1]\n", "7 [5, 7, 10, 6, 1, 2, 0] [4, 6, 3, 5, 2, 3, 1]\n", "8 [5, 3, 10, 7, 1, 2, 0, 6] [4, 7, 3, 6, 2, 3, 1, 5]\n", "9 [5, 4, 10, 3, 1, 2, 0, 7, 6] [4, 10, 3, 7, 2, 3, 1, 6, 5]\n"]}], "source": ["def _heapify_max_bottom_position(ens, pos):\n", " \"Organise un ensemble selon un tas.\"\n", " modif = 1\n", " while modif > 0:\n", " modif = 0\n", " i = len(pos) - 1\n", " while i > 0:\n", " root = (i-1) // 2\n", " if ens[pos[root]] < ens[pos[i]]:\n", " swap(pos, root, i)\n", " modif += 1\n", " i -= 1\n", "\n", "\n", "def _heapify_max_up_position(ens, pos):\n", " \"Organise un ensemble selon un tas.\"\n", " i = 0\n", " while True:\n", " left = 2*i + 1\n", " right = left+1\n", " if right < len(pos):\n", " if ens[pos[left]] > ens[pos[i]] >= ens[pos[right]]:\n", " swap(pos, i, left)\n", " i = left\n", " elif ens[pos[right]] > ens[pos[i]]:\n", " swap(pos, i, right)\n", " i = right\n", " else:\n", " break\n", " elif left < len(pos) and ens[pos[left]] > ens[pos[i]]:\n", " swap(pos, i, left)\n", " i = left\n", " else:\n", " break\n", "\n", "\n", "def topk_min_position(ens, k):\n", " \"Retourne les positions des k plus petits \u00e9l\u00e9ments d'un ensemble.\"\n", " \n", " pos = list(range(k))\n", " _heapify_max_bottom_position(ens, pos)\n", " \n", " for i, el in enumerate(ens[k:]):\n", " if el < ens[pos[0]]:\n", " pos[0] = k + i\n", " _heapify_max_up_position(ens, pos)\n", " return pos\n", "\n", " \n", "ens = [1,2,3,7,10,4,5,6,11,12,3]\n", "for k in range(1, len(ens)-1):\n", " pos = topk_min_position(ens, k)\n", " print(k, pos, [ens[i] for i in pos])"]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["5.59 ms \u00b1 728 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 100 loops each)\n"]}], "source": ["import numpy.random as rnd\n", "\n", "X = rnd.randn(10000)\n", "\n", "%timeit topk_min(X, 20)"]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["7.85 ms \u00b1 544 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 100 loops each)\n"]}], "source": ["%timeit topk_min_position(X, 20)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Co\u00fbt de l'algorithme"]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [{"name": "stderr", "output_type": "stream", "text": ["100%|\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588\u2588| 20/20 [00:23<00:00, 1.78s/it]\n"]}, {"data": {"text/html": ["