Introducción a los montículos

heaps.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Montículos\n",
    "==========\n",
    "\n",
    "Un montículo es una estructura de datos que permite implementar una cola de prioridad, la cual resuelve eficientemente operaciones como obtener el máximo de un conjunto de elementos. \n",
    "\n",
    "Un mónticulo es básicamente un árbol binario 'casi' completo, es decir todos los niveles están llenos, excepto posiblemente el último. Un mónticulo se representa por un arreglo A[1..n]. El elemento A[1] corresponde a la raíz del árbol, los elementos A[2] y A[3] al primer nivel y así sucesivamente. La siguiente función imprime un arreglo conteniendo un móntículo de manera que se pueda observar la estructura del ábol.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                              1                                                               \n",
      "              2                               3                               \n",
      "      4               5               6               7               \n",
      "  8       9       10      11      12      13      14      15      \n",
      "16  17  18  19  \n"
     ]
    }
   ],
   "source": [
    "from math import log\n",
    "\n",
    "def pretty_print_heap(A):\n",
    "    n = len(A) - 1 # the heap starts at position 1, so A[0] is ignored\n",
    "    for h in range(int(log(n,2))):\n",
    "        nspc = (2**(int(log(n,2)) - h + 1) - 2)\n",
    "        line = nspc * ' '\n",
    "        for i in range(2**h, 2**(h+1)):\n",
    "            line += repr(A[i]).ljust(2) + (2*nspc + 2)*' '\n",
    "        print line\n",
    "    line = ''\n",
    "    for i in range(2**(int(log(n,2))), n+1):\n",
    "        line += repr(A[i]).ljust(2) + '  '\n",
    "    print line\n",
    "\n",
    "pretty_print_heap(range(0,20))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El padre de un node en la posición i es calculado por:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def parent(i):\n",
    "    return int(i / 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "el hijo izquierdo es calculado por:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def left(i):\n",
    "    return 2 * i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "y el hijo derecho por:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def right(i):\n",
    "    return 2 * i + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La propiedad importante que todo montículo debe cumplir es que el padre debe ser mayor o igual a sus hijos (si es un max-heap):\n",
    "$$ \\forall 1 \\le i \\le n, A[parent(i)] \\ge A[i]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Por ejemplo, el siguiente arreglo no cumple con la propiedad:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "              16                              \n",
      "      7               10              \n",
      "  8       14      9       3       \n",
      "2   4   1   \n"
     ]
    }
   ],
   "source": [
    "A = [0, 16, 7, 10, 8, 14, 9, 3, 2, 4, 1]\n",
    "pretty_print_heap(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "pues la posición A[2] es menor que su hijo derecho A[5] y que su hijo izquierdo A[4]. Mientras que este arreglo si tiene la propiedad:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "              16                              \n",
      "      14              10              \n",
      "  8       7       9       3       \n",
      "2   4   1   \n"
     ]
    }
   ],
   "source": [
    "A = [0, 16, 14, 10, 8, 7, 9, 3, 2, 4, 1]\n",
    "pretty_print_heap(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Manteniendo la propiedad de montículo\n",
    "-----------\n",
    "\n",
    "Suponga que en el anterior arreglo, se modifica la primera posición por un número menor de 10, por ejemplo 6, en ese caso se pierde la propiedad de montículo, aunque el sub-árbol derecho e izquierdo todavía la conservan. La siguiente función restablece la propiedad mediante un procedimiento recursivo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def max_heapify(A, i, trace=True):\n",
    "    if trace: # este código solo se ejecuta si trace==True\n",
    "        print \"-----------------------\"\n",
    "        print \"i =\", i\n",
    "        print A\n",
    "        pretty_print_heap(A)\n",
    "    l = left(i)\n",
    "    r = right(i)\n",
    "    if l <= (len(A)- 1) and A[l] > A[i]:\n",
    "        largest = l \n",
    "    else: \n",
    "        largest = i\n",
    "    if r <= len(A)- 1 and A[r] > A[largest]:\n",
    "        largest = r\n",
    "    if largest <> i:\n",
    "        A[i], A[largest] = A[largest], A[i]\n",
    "        max_heapify(A, largest, trace)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Probemos la función max_heapify en el siguiente arreglo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-----------------------\n",
      "i = 1\n",
      "[0, 3, 14, 10, 8, 7, 9, 3, 2, 4, 1]\n",
      "              3                               \n",
      "      14              10              \n",
      "  8       7       9       3       \n",
      "2   4   1   \n",
      "-----------------------\n",
      "i = 2\n",
      "[0, 14, 3, 10, 8, 7, 9, 3, 2, 4, 1]\n",
      "              14                              \n",
      "      3               10              \n",
      "  8       7       9       3       \n",
      "2   4   1   \n",
      "-----------------------\n",
      "i = 4\n",
      "[0, 14, 8, 10, 3, 7, 9, 3, 2, 4, 1]\n",
      "              14                              \n",
      "      8               10              \n",
      "  3       7       9       3       \n",
      "2   4   1   \n",
      "-----------------------\n",
      "i = 9\n",
      "[0, 14, 8, 10, 4, 7, 9, 3, 2, 3, 1]\n",
      "              14                              \n",
      "      8               10              \n",
      "  4       7       9       3       \n",
      "2   3   1   \n"
     ]
    }
   ],
   "source": [
    "A[1] = 3\n",
    "max_heapify(A, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Construyendo un montículo\n",
    "------------\n",
    "\n",
    "El problema ahora es como partiendo de un arreglo en un orden arbitrario, modificarlo de manera que la propiedad de montículo se cumpla. La idea es usar la función max-heapify de la base del árbol hacia arriba, restableciendo la propiedad de montículo, nivel por nivel. Esta estrategia se implementa en la siguiente función:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def build_max_heap(A, trace=False):\n",
    "    for i in range(int(len(A) / 2), 0, -1):\n",
    "        max_heapify(A, i, trace=False)\n",
    "        if trace:\n",
    "            # The next 4 lines of code just print the heap\n",
    "            print \"-----------------------\"\n",
    "            print \"i =\", i\n",
    "            print A\n",
    "            pretty_print_heap(A)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ahora aplicamos la función a un arreglo con los números del 1 al 10:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-----------------------\n",
      "i = 5\n",
      "[0, 1, 2, 3, 4, 10, 6, 7, 8, 9, 5]\n",
      "              1                               \n",
      "      2               3               \n",
      "  4       10      6       7       \n",
      "8   9   5   \n",
      "-----------------------\n",
      "i = 4\n",
      "[0, 1, 2, 3, 9, 10, 6, 7, 8, 4, 5]\n",
      "              1                               \n",
      "      2               3               \n",
      "  9       10      6       7       \n",
      "8   4   5   \n",
      "-----------------------\n",
      "i = 3\n",
      "[0, 1, 2, 7, 9, 10, 6, 3, 8, 4, 5]\n",
      "              1                               \n",
      "      2               7               \n",
      "  9       10      6       3       \n",
      "8   4   5   \n",
      "-----------------------\n",
      "i = 2\n",
      "[0, 1, 10, 7, 9, 5, 6, 3, 8, 4, 2]\n",
      "              1                               \n",
      "      10              7               \n",
      "  9       5       6       3       \n",
      "8   4   2   \n",
      "-----------------------\n",
      "i = 1\n",
      "[0, 10, 9, 7, 8, 5, 6, 3, 1, 4, 2]\n",
      "              10                              \n",
      "      9               7               \n",
      "  8       5       6       3       \n",
      "1   4   2   \n"
     ]
    }
   ],
   "source": [
    "A = range(11)\n",
    "build_max_heap(A, trace= True)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Heapsort\n",
    "--------\n",
    "\n",
    "La función puede ser usada para ordenar un arreglo. La idea es inicialmente construir un montículo y después iterativamente extraemos el elemento máximo y lo insertamos en un nuevo arreglo que al final del procedimiento estará ordenado."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[9]\n",
      "[7, 9]\n",
      "[6, 7, 9]\n",
      "[5, 6, 7, 9]\n",
      "[4, 5, 6, 7, 9]\n",
      "[2, 4, 5, 6, 7, 9]\n",
      "[2, 4, 5, 6, 7, 9]\n"
     ]
    }
   ],
   "source": [
    "def heap_sort(A):\n",
    "    B = []\n",
    "    build_max_heap(A)\n",
    "    while len(A)>1:\n",
    "        maxim = A[1]\n",
    "        A[1] = A[-1]\n",
    "        del A[-1]\n",
    "        B.insert(0,maxim)\n",
    "        print B\n",
    "        max_heapify(A,1,trace=False)\n",
    "    return B\n",
    "        \n",
    "print heap_sort([0,4,6,7,2,5,9])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cola de prioridad\n",
    "----\n",
    "\n",
    "La estructura montículo puede ser usada para implementar una cola de prioridades. En esta se pretende mantener organizados un conjunto de ítems de acuerdo con un criterio (la prioridad), de manera que sea pueda obtener el elemento con prioridad máxima de manera eficiente. La cola de prioridad debe soportar las siguientes operaciones:\n",
    "\n",
    " * Extraer el máximo (extract_max_heap(A))\n",
    " * Incrementar la prioridad de un elemento (increase_key_heap(A,i,v))\n",
    " * Insertar un elemento con una prioridad dada (increase_key_heap(A,i,v))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "              16                              \n",
      "      14              10              \n",
      "  8       7       9       3       \n",
      "2   4   1   \n",
      "-----------------------\n",
      "Extracted element: 16\n",
      "              14                              \n",
      "      8               10              \n",
      "  4       7       9       3       \n",
      "2   1   \n",
      "-----------------------\n",
      "Extracted element: 14\n",
      "              10                              \n",
      "      8               9               \n",
      "  4       7       1       3       \n",
      "2   \n",
      "-----------------------\n",
      "Extracted element: 10\n",
      "      9               \n",
      "  8       3       \n",
      "4   7   1   2   \n",
      "-----------------------\n",
      "Extracted element: 9\n",
      "      8               \n",
      "  7       3       \n",
      "4   2   1   \n",
      "-----------------------\n",
      "Extracted element: 8\n",
      "      7               \n",
      "  4       3       \n",
      "1   2   \n",
      "-----------------------\n",
      "Extracted element: 7\n",
      "      4               \n",
      "  2       3       \n",
      "1   \n",
      "-----------------------\n",
      "Extracted element: 4\n",
      "  3       \n",
      "2   1   \n",
      "-----------------------\n",
      "Extracted element: 3\n",
      "  2       \n",
      "1   \n",
      "-----------------------\n",
      "Extracted element: 2\n",
      "1   \n"
     ]
    }
   ],
   "source": [
    "def extract_max_heap(A):\n",
    "    maxim = A[1]\n",
    "    A[1] = A[-1]\n",
    "    del A[-1]\n",
    "    max_heapify(A,1,trace=False)\n",
    "    return maxim\n",
    "    \n",
    "A = [0, 16, 7, 10, 8, 14, 9, 3, 2, 4, 1]\n",
    "\n",
    "build_max_heap(A)\n",
    "pretty_print_heap(A)\n",
    "\n",
    "\n",
    "while len(A)>2:\n",
    "    print \"-----------------------\"\n",
    "    print \"Extracted element:\", extract_max_heap(A)\n",
    "    pretty_print_heap(A)\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "              16                              \n",
      "      14              10              \n",
      "  8       7       9       3       \n",
      "2   4   1   \n",
      "-----------------------\n",
      "Changed heap:\n",
      "              16                              \n",
      "      14              10              \n",
      "  8       7       9       17      \n",
      "2   4   1   \n",
      "-----------------------\n",
      "[0, 16, 14, 17, 8, 7, 9, 10, 2, 4, 1]\n",
      "              16                              \n",
      "      14              17              \n",
      "  8       7       9       10      \n",
      "2   4   1   \n",
      "i = 7\n",
      "-----------------------\n",
      "[0, 17, 14, 16, 8, 7, 9, 10, 2, 4, 1]\n",
      "              17                              \n",
      "      14              16              \n",
      "  8       7       9       10      \n",
      "2   4   1   \n",
      "i = 3\n"
     ]
    }
   ],
   "source": [
    "def increase_key_heap(A,i,v):\n",
    "    if A[i]>v:\n",
    "        print \"Error\"\n",
    "    A[i] = v\n",
    "    print \"-----------------------\"\n",
    "    print \"Changed heap:\"\n",
    "    pretty_print_heap(A)\n",
    "    \n",
    "    while i>1 and A[i>>1] < A[i]:\n",
    "        A[i>>1], A[i] = A[i], A[i>>1]\n",
    "        # The next 4 lines of code just print the heap\n",
    "        print \"-----------------------\"\n",
    "        print A\n",
    "        pretty_print_heap(A)\n",
    "        print \"i =\", i\n",
    "        ##############################################\n",
    "        i = i>>1\n",
    "\n",
    "A = [0, 16, 7, 10, 8, 14, 9, 3, 2, 4, 1]\n",
    "\n",
    "build_max_heap(A)\n",
    "pretty_print_heap(A)\n",
    "\n",
    "increase_key_heap(A,7,17)\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "              16                              \n",
      "      14              10              \n",
      "  8       7       9       3       \n",
      "2   4   1   \n",
      "-----------------------\n",
      "Changed heap:\n",
      "              16                              \n",
      "      14              10              \n",
      "  8       7       9       3       \n",
      "2   4   1   18  \n",
      "-----------------------\n",
      "[0, 16, 14, 10, 8, 18, 9, 3, 2, 4, 1, 7]\n",
      "              16                              \n",
      "      14              10              \n",
      "  8       18      9       3       \n",
      "2   4   1   7   \n",
      "i = 11\n",
      "-----------------------\n",
      "[0, 16, 18, 10, 8, 14, 9, 3, 2, 4, 1, 7]\n",
      "              16                              \n",
      "      18              10              \n",
      "  8       14      9       3       \n",
      "2   4   1   7   \n",
      "i = 5\n",
      "-----------------------\n",
      "[0, 18, 16, 10, 8, 14, 9, 3, 2, 4, 1, 7]\n",
      "              18                              \n",
      "      16              10              \n",
      "  8       14      9       3       \n",
      "2   4   1   7   \n",
      "i = 2\n"
     ]
    }
   ],
   "source": [
    "def insert_heap(A,v):\n",
    "    A.append(v-1)\n",
    "    increase_key_heap(A,len(A)-1,v)\n",
    "    \n",
    "A = [0, 16, 7, 10, 8, 14, 9, 3, 2, 4, 1]\n",
    "\n",
    "build_max_heap(A)\n",
    "pretty_print_heap(A)\n",
    "\n",
    "insert_heap(A,18)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}