05_Pilas_Colas_y_Colas_de_Prioridad.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 5 Pilas, Colas y Colas de Prioridad"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En este capítulo veremos tres _tipos de datos abstractos_ (_TDAs_) que son muy utilizados.\n",
    "\n",
    "Un tipo de datos abstracto es un conjunto de datos, más operaciones asociadas, para el cual se aplica una política de \"ocultamiento de información\": los usuarios del TDA saben **qué** funcionalidad éste provee, pero no saben **cómo** se implementa esta funcionalidad.\n",
    "\n",
    "Esta separación de responsabilidad es fundamental para mantener la complejidad bajo control.\n",
    "Sólo los implementadores del TDA necesitan preocuparse de su implementación, y además son libres para modificarla en la medida que la interfaz de uso se mantenga intacta."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pilas (\"*Stacks*\")\n",
    "\n",
    "Una **pila**, también llamada *stack* o *pushdown* en inglés, es una lista de elementos en la cual todas las operaciones se realizan solo en un extremo de la lista.\n",
    "\n",
    "Es usual visualizar la pila creciendo verticalmente hacia arriba, y llamamos \"tope\" a su extremo superior:\n",
    "\n",
    "![pila](recursos/pila.png)\n",
    "\n",
    "Las dos operaciones básicas son **push** (apilar), que agrega un elemento encima de todos, y **pop** (desapilar), que extrae el elemento del tope de la pila. Más precisamente, si `s` es un objeto de tipo Pila, están disponibles las siguientes operaciones:\n",
    "\n",
    "* `s.push(x)`: apila x en el tope de la pila `s`\n",
    "* `x=s.pop()`: extrae y retorna el elemento del tope de la pila `s`\n",
    "* `b=s.is_empty()`: retorna verdadero si la pila `s` está vacía, falso si no\n",
    "\n",
    "Dado que los elementos salen de la pila en el orden inverso en que ingresaron, esta estructura también se conoce como \"lista LIFO\", por \"Last-In-First-Out\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementación usando listas de Python\n",
    "\n",
    "Es posible implementar una pila muy fácilmente usando las listas que provee el lenguaje Python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Pila:\n",
    "    def __init__(self):\n",
    "        self.s=[]\n",
    "    def push(self,x):\n",
    "        self.s.append(x)\n",
    "    def pop(self):\n",
    "        assert len(self.s)>0\n",
    "        return self.s.pop() # pop de lista, no de Pila\n",
    "    def is_empty(self):\n",
    "        return len(self.s)==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20\n",
      "30\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "a=Pila()\n",
    "a.push(10)\n",
    "a.push(20)\n",
    "print(a.pop())\n",
    "a.push(30)\n",
    "print(a.pop())\n",
    "print(a.pop())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Esta implementación simple posiblemente sirve en la mayoría de los casos, pero si necesitamos poder garantizar su eficiencia, tenemos el problema que la implementación de las listas de Python está fuera de nuestro control, y no podemos garantizar, por ejemplo, que cada una de las operaciones tome tiempo constante.\n",
    "\n",
    "Por ese motivo, es útil contar con implementaciones en que sí podamos dar ese tipo de garantía."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementación usando un arreglo\n",
    "\n",
    "Utilizaremos un arreglo $s$, en donde los elementos de la pila se almacenarán en los casilleros $0,1,\\ldots$, con el elemento del tope en el casillero ocupado de más a la derecha. Mantendremos una variable $n$ para almacenar el número de elementos presentes en la pila, y el arreglo tendrá un tamaño máximo, el que se podrá especificar opcionalmente al momento de crear la pila.\n",
    "\n",
    "![pila-arreglo](recursos/pila-arreglo.png?raw=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "class Pila:  \n",
    "    def __init__(self,maxn=100):\n",
    "        self.s=np.zeros(maxn)\n",
    "        self.n=0\n",
    "    def push(self,x):\n",
    "        assert self.n<len(self.s)-1\n",
    "        self.s[self.n]=x\n",
    "        self.n+=1     \n",
    "    def pop(self):\n",
    "        assert self.n>0 \n",
    "        self.n-=1\n",
    "        return self.s[self.n]\n",
    "    def is_empty(self):\n",
    "        return self.n==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20.0\n",
      "30.0\n",
      "10.0\n"
     ]
    }
   ],
   "source": [
    "a=Pila()\n",
    "a.push(10)\n",
    "a.push(20)\n",
    "print(a.pop())\n",
    "a.push(30)\n",
    "print(a.pop())\n",
    "print(a.pop())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Esta implementación es muy eficiente: no solo es evidente que cada operación toma tiempo constante, sino además esa constante es muy pequeña. Sin embargo, tiene la limitación de que es necesario darle un tamaño máximo al arreglo, el cual a la larga puede resultar insuficiente.\n",
    "\n",
    "Existe una manera de copiar todos los elementos a un arreglo más grande y seguir operando cuando el arreglo se llena. Si el nuevo arreglo es del doble del tamaño anterior, el costo de copiar todos los elementos se puede _amortizar_ a lo largo de las operaciones, de modo que en _promedio_ sea constante, pero se pierde la propiedad de que las operaciones tomen tiempo constante en el peor caso.\n",
    "\n",
    "La siguiente es otra alternativa de implementación, que no sufre de ese problema."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementación usando una lista enlazada\n",
    "\n",
    "En esta implementación los elementos de la pila se almacenan en una lista de enlace simple (sin cabecera), en que el elemento del tope de la pila es el primero de la lista.\n",
    "\n",
    "![pila-lista](recursos/pila-lista.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class NodoLista:\n",
    "    def __init__(self,info,sgte=None):\n",
    "        self.info=info\n",
    "        self.sgte=sgte\n",
    "class Pila:\n",
    "    def __init__(self):\n",
    "        self.tope=None\n",
    "    def push(self,x):\n",
    "        self.tope=NodoLista(x,self.tope)\n",
    "    def pop(self):\n",
    "        assert self.tope is not None\n",
    "        x=self.tope.info\n",
    "        self.tope=self.tope.sgte\n",
    "        return x\n",
    "    def is_empty(self):\n",
    "        return self.tope is None\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20\n",
      "30\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "a=Pila()\n",
    "a.push(10)\n",
    "a.push(20)\n",
    "print(a.pop())\n",
    "a.push(30)\n",
    "print(a.pop())\n",
    "print(a.pop())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aplicaciones de pilas\n",
    "\n",
    "#### Evaluación de notación polaca\n",
    "\n",
    "Si se tiene una fórmula en notación polaca, se puede calcular su valor usando una pila, inicialmente vacía.\n",
    "Los símbolos de la fórmula se van leyendo de izquierda a derecha, y:\n",
    "\n",
    "* si el símbolo es un número, se le hace `push` en la pila\n",
    "* si el símbolo es un operador, se hacen dos `pop`, se efectúa la operación indicada entre los dos datos obtenidos, y el resultado se agrega de vuelta a la pila con `push`\n",
    "\n",
    "Al terminar, si la fórmula estaba bien formada, debe haber solo un elemento en la pila, que es el resultado de la evaluación de la fórmula."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def eval_polaca(formula):\n",
    "    a=Pila()\n",
    "    for x in formula.split():\n",
    "        if x.isnumeric():\n",
    "            a.push(int(x))\n",
    "        else: # tiene que ser un operador\n",
    "            v=a.pop()\n",
    "            u=a.pop()\n",
    "            if x==\"+\":\n",
    "                w=u+v\n",
    "            elif x==\"-\":\n",
    "                w=u-v\n",
    "            elif x==\"*\":\n",
    "                w=u*v\n",
    "            elif x==\"/\":\n",
    "                w=u/v\n",
    "            else:\n",
    "                print(\"Operador desconocido:\",x)\n",
    "                return 0\n",
    "            a.push(w)\n",
    "    return a.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Escriba la fórmula en notación polaca: 2 3 + 9 4 2 / - *\n",
      "Resultado:  35.0\n"
     ]
    }
   ],
   "source": [
    "formula=input('Escriba la fórmula en notación polaca: ')\n",
    "print(\"Resultado: \",eval_polaca(formula))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Recorrido no recursivo de un árbol binario\n",
    "\n",
    "Supongamos que queremos recorrer un árbol binario en preorden.\n",
    "En lugar de utilizar un algoritmo recursivo, podemos imaginar que tenermos una \"To DO list\" en donde almacenamos la lista de nodos que debemos visitar en el futuro.\n",
    "Inicialmente, esta lista contiene solo la raíz.\n",
    "En cada iteración, extraemos un nodo de la lista, lo visitamos, y luego agregamos a la lista a sus dos hijos.\n",
    "Si la lista se mantiene como una pila, el orden del en que se visitan los nodos es exactamente preorden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Nodo:\n",
    "    def __init__(self, izq, info, der):\n",
    "        self.izq=izq\n",
    "        self.info=info\n",
    "        self.der=der\n",
    "        \n",
    "class Arbol:\n",
    "    def __init__(self,raiz=None):\n",
    "        self.raiz=raiz\n",
    "        \n",
    "    def preorden(self):\n",
    "        print(\"Preorden no recursivo:\", end=\" \")\n",
    "        s=Pila()\n",
    "        s.push(self.raiz)\n",
    "        while not s.is_empty():\n",
    "            p=s.pop()\n",
    "            if p is not None:\n",
    "                print(p.info, end=\" \")\n",
    "                s.push(p.der)\n",
    "                s.push(p.izq)\n",
    "        print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Es importante que las operaciones `push` se hagan en el orden indicado (derecho-izquierdo), para que de acuerdo a la disciplina LIFO, salga primero el izquierdo y luego el derecho."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "a=Arbol(\n",
    "    Nodo(\n",
    "        Nodo(\n",
    "            Nodo(None,15,None),\n",
    "            20,\n",
    "            Nodo(\n",
    "                Nodo(None,30,None),\n",
    "                35,\n",
    "                None\n",
    "            )\n",
    "        ),\n",
    "        42,\n",
    "        Nodo(\n",
    "            Nodo(\n",
    "                Nodo(\n",
    "                    Nodo(None,65,None),\n",
    "                    72,\n",
    "                    Nodo(None,81,None)\n",
    "                ),\n",
    "                90,\n",
    "                None\n",
    "            ),\n",
    "            95,\n",
    "            None\n",
    "        )\n",
    "       )\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Preorden no recursivo: 42 20 15 35 30 95 90 72 65 81 \n"
     ]
    }
   ],
   "source": [
    "a.preorden()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hay una pequeña optimización que se puede hacer al algoritmo de recorrido no recursivo.\n",
    "Cuando hacemos las dos operaciones `push` y volvemos a ejecutar el `while`, sabemos que la pila no está vacía, de modo que esa pregunta es superflua. Además, al hacer el `pop` sabemos que lo que va a salir de la pila es lo último que se agregó, o sea, `p.izq`. Por lo tanto, podemos saltarnos tanto la pregunta como el `pop` e ir directamente al `if`, el cual por lo tanto se transforma en un `while`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Arbol:\n",
    "    def __init__(self,raiz=None):\n",
    "        self.raiz=raiz\n",
    "        \n",
    "    def preorden(self):\n",
    "        print(\"Preorden no recursivo optimizado:\", end=\" \")\n",
    "        s=Pila()\n",
    "        s.push(self.raiz)\n",
    "        while not s.is_empty():\n",
    "            p=s.pop()\n",
    "            while p is not None:\n",
    "                print(p.info, end=\" \")\n",
    "                s.push(p.der)\n",
    "                p=p.izq\n",
    "        print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "a=Arbol(\n",
    "    Nodo(\n",
    "        Nodo(\n",
    "            Nodo(None,15,None),\n",
    "            20,\n",
    "            Nodo(\n",
    "                Nodo(None,30,None),\n",
    "                35,\n",
    "                None\n",
    "            )\n",
    "        ),\n",
    "        42,\n",
    "        Nodo(\n",
    "            Nodo(\n",
    "                Nodo(\n",
    "                    Nodo(None,65,None),\n",
    "                    72,\n",
    "                    Nodo(None,81,None)\n",
    "                ),\n",
    "                90,\n",
    "                None\n",
    "            ),\n",
    "            95,\n",
    "            None\n",
    "        )\n",
    "       )\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Preorden no recursivo optimizado: 42 20 15 35 30 95 90 72 65 81 \n"
     ]
    }
   ],
   "source": [
    "a.preorden()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Colas (\"*Queues*\")\n",
    "\n",
    "Una cola es una lista en que los elementos ingresan por un extremo y salen por el otro. Debido a que los elementos van saliendo en orden de llegada, una cola también se llama \"lista FIFO\", por \"First-In-First-Out\".\n",
    "\n",
    "![cola](recursos/cola.png)\n",
    "\n",
    "Las dos operaciones básicas son **enq** (encolar), que agrega un elemento al final de todos, y **deq** (desencolar), que extrae el elemento que encabeza la cola. Más precisamente, si `q` es un objeto de tipo Cola, están disponibles las siguientes operaciones:\n",
    "\n",
    "* `q.enq(x)`: encola x al final de la cola `q`\n",
    "* `x=q.deq()`: extrae y retorna el elemento a la cabeza de la cola `q`\n",
    "* `b=q.is_empty()`: retorna verdadero si la cola `q`está vacía, falso si no"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementación usando listas de Python\n",
    "\n",
    "Tal como hicimos en el caso de las pilas, es muy simple implementar colas usando las listas de Python, pero no tenemos mucho control sobre la eficiencia del resultado:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Cola:\n",
    "    def __init__(self):\n",
    "        self.q=[]\n",
    "    def enq(self,x):\n",
    "        self.q.insert(0,x)\n",
    "    def deq(self):\n",
    "        assert len(self.q)>0\n",
    "        return self.q.pop()\n",
    "    def is_empty(self):\n",
    "        return len(self.q)==0\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "72\n",
      "36\n",
      "20\n",
      "61\n"
     ]
    }
   ],
   "source": [
    "a=Cola()\n",
    "a.enq(72)\n",
    "a.enq(36)\n",
    "print(a.deq())\n",
    "a.enq(20)\n",
    "print(a.deq())\n",
    "print(a.deq())\n",
    "a.enq(61)\n",
    "print(a.deq())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementación usando un arreglo\n",
    "\n",
    "De manera análoga a lo que hicimos en el caso de la pila, podemos almacenar los $n$ elementos de la cola usando posiciones contiguas en un arreglo, por ejemplo, las $n$ primeras posiciones.\n",
    "Pero hay un problema: como la cola crece por un extremo y se achica por el otro, ese grupo de posiciones contiguas se va desplazando dentro del arreglo, y después de un rato choca contra el otro extremo. La solución es ver al arreglo como _circular_, esto es, que si el arreglo tiene tamaño $maxn$, a continuación de la posición $maxn-1$ viene la posición $0$. Esto se puede hacer fácilmente usando aritmética módulo $maxn$.\n",
    "\n",
    "Para la implementación, utilizaremos un subíndice $cabeza$ que apunta al primer elemento de la cola, y una variable $n$ que indica cuántos elementos hay en la cola.\n",
    "La siguiente figura muestra dos situaciones en que podría encontrarse el arreglo:\n",
    "\n",
    "![cola-arreglo](recursos/cola-arreglo.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "class Cola:  \n",
    "    def __init__(self,maxn=100):\n",
    "        self.q=np.zeros(maxn)\n",
    "        self.n=0\n",
    "        self.cabeza=0\n",
    "    def enq(self,x):\n",
    "        assert self.n<len(self.q)-1\n",
    "        self.q[(self.cabeza+self.n)%len(self.q)]=x\n",
    "        self.n+=1      \n",
    "    def deq(self):\n",
    "        assert self.n>0\n",
    "        x=self.q[self.cabeza]\n",
    "        self.cabeza=(self.cabeza+1)%len(self.q)\n",
    "        self.n-=1\n",
    "        return x\n",
    "    def is_empty(self):\n",
    "        return self.n==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "72.0\n",
      "36.0\n",
      "20.0\n",
      "61.0\n"
     ]
    }
   ],
   "source": [
    "a=Cola(3) # para forzar circularidad\n",
    "a.enq(72)\n",
    "a.enq(36)\n",
    "print(a.deq())\n",
    "a.enq(20)\n",
    "print(a.deq())\n",
    "print(a.deq())\n",
    "a.enq(61)\n",
    "print(a.deq())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementación usando una lista enlazada\n",
    "\n",
    "El operar en los dos extremos de la cola sugiere de inmediato el uso de una lista de doble enlace, y esa es una opción posible. Pero, como veremos, se puede implementar una cola con una lista de enlace simple:\n",
    "\n",
    "![cola-lista](recursos/cola-lista.png)\n",
    "\n",
    "Una cosa que complica un poco la programación es que el invariante que se ve a la derecha se cumple solo si la cola es no vacía. Para una cola vacía, los dos punteros (primero y último) son nulos. Por lo tanto, un `enq` sobre una cola vacía, y un `deq` que deja una cola vacía serán casos especiales."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "class NodoLista:\n",
    "    def __init__(self,info,sgte=None):\n",
    "        self.info=info\n",
    "        self.sgte=sgte\n",
    "class Cola:\n",
    "    def __init__(self):\n",
    "        self.primero=None\n",
    "        self.ultimo=None\n",
    "    def enq(self,x):\n",
    "        p=NodoLista(x)\n",
    "        if self.ultimo is not None: # cola no vacía, agregamos al final\n",
    "            self.ultimo.sgte=p\n",
    "            self.ultimo=p\n",
    "        else: # la cola estaba vacía\n",
    "            self.primero=p\n",
    "            self.ultimo=p\n",
    "    def deq(self):\n",
    "        assert self.primero is not None\n",
    "        x=self.primero.info\n",
    "        if self.primero is not self.ultimo: # hay más de 1 elemento\n",
    "            self.primero=self.primero.sgte\n",
    "        else: # hay solo 1 elemento, el deq deja la cola vacía\n",
    "            self.primero=None\n",
    "            self.ultimo=None\n",
    "        return x\n",
    "    def is_empty(self):\n",
    "        return self.primero is None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "72\n",
      "36\n",
      "20\n",
      "61\n"
     ]
    }
   ],
   "source": [
    "a=Cola()\n",
    "a.enq(72)\n",
    "a.enq(36)\n",
    "print(a.deq())\n",
    "a.enq(20)\n",
    "print(a.deq())\n",
    "print(a.deq())\n",
    "a.enq(61)\n",
    "print(a.deq())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aplicaciones de colas\n",
    "\n",
    "Las colas se utilizan en los sistemas operativos siempre que hay algún recurso que no puede ser compartido. Uno de los procesos que lo requieren tiene acceso al recurso, mientras los demás deben esperar en una cola. Un ejemplo de esto son los sistemas de \"spooling\" para las impresoras.\n",
    "\n",
    "También se usan mucho en sistemas de simulación, cuando se deben modelar situaciones del mundo real en que hay colas. Por ejemplo, la caja en un supermercado.\n",
    "\n",
    "A continuación veremos una aplicación análoga a la que vimos en el caso de pilas para el recorrido de un árbol binario.\n",
    "\n",
    "#### Recorrido de un árbol binario por niveles\n",
    "\n",
    "Supongamos que se desea recorrer un árbol binario, visitando sus nodos en orden de su distancia a la raíz.\n",
    "No hay manera de escribir esto de manera recursiva, pero el problema se puede resolver usando el mismo enfoque que utilizamos al recorrer un árbol binario en preorden de manera no recursiva, pero usando una cola en lugar de una pila."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Nodo:\n",
    "    def __init__(self, izq, info, der):\n",
    "        self.izq=izq\n",
    "        self.info=info\n",
    "        self.der=der\n",
    "        \n",
    "class Arbol:\n",
    "    def __init__(self,raiz=None):\n",
    "        self.raiz=raiz\n",
    "        \n",
    "    def niveles(self):\n",
    "        print(\"Recorrido por niveles:\", end=\" \")\n",
    "        c=Cola()\n",
    "        c.enq(self.raiz)\n",
    "        while not c.is_empty():\n",
    "            p=c.deq()\n",
    "            if p is not None:\n",
    "                print(p.info, end=\" \")\n",
    "                c.enq(p.izq)\n",
    "                c.enq(p.der)\n",
    "        print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "a=Arbol(\n",
    "    Nodo(\n",
    "        Nodo(\n",
    "            Nodo(None,15,None),\n",
    "            20,\n",
    "            Nodo(\n",
    "                Nodo(None,30,None),\n",
    "                35,\n",
    "                None\n",
    "            )\n",
    "        ),\n",
    "        42,\n",
    "        Nodo(\n",
    "            Nodo(\n",
    "                Nodo(\n",
    "                    Nodo(None,65,None),\n",
    "                    72,\n",
    "                    Nodo(None,81,None)\n",
    "                ),\n",
    "                90,\n",
    "                None\n",
    "            ),\n",
    "            95,\n",
    "            None\n",
    "        )\n",
    "       )\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Recorrido por niveles: 42 20 95 15 35 90 30 72 65 81 \n"
     ]
    }
   ],
   "source": [
    "a.niveles()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Colas de Prioridad\n",
    "\n",
    "Hay muchas situaciones en que los elementos que esperan en una cola deben ir siendo atendidos no por orden de llegada, sino de acuerdo a algún criterio de _prioridad_.\n",
    "En esos casos, no nos sirve la cola como la hemos visto, sino que se necesita un nuevo tipo de estructura.\n",
    "\n",
    "Una cola de prioridad es un TDA que consiste de un conjunto de datos que poseen un atributo (llamado su _prioridad_) perteneciente a algún conjunto ordenado, y en el cual se pueden ejecutar dos operaciones básicas: **insertar** un nuevo elemento con una prioridad cualquiera y **extraer** el elemento de máxima prioridad.\n",
    "\n",
    "Más específicamente, las operaciones permitidas son:\n",
    "\n",
    "* `q.insert(x)`: inserta un elemento de prioridad x en la cola de prioridad `q`\n",
    "* `x=q.extract_max()`: extrae y retorna el elemento de máxima prioridad de la cola de prioridad `q`\n",
    "* `b=q.is_empty()`: retorna verdadero si la cola de prioridad `q`está vacía, falso si no\n",
    "\n",
    "Definir qué significa tener \"máxima prioridad\" depende de la aplicación que queramos darle a la cola de prioridad. En los ejemplos de este capítulo, supondremos que mejor prioridad corresponde a un mayor valor numérico, pero por simetría también sería válido el criterio opuesto."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementación usando una lista desordenada\n",
    "\n",
    "La implementación más simple consiste en mantener el conjunto como una lista desordenada. Agregar un elemento es trivial, pero encontrar el máximo requiere tiempo $\\Theta(n)$.\n",
    "\n",
    "La lista se puede mantener ya sea en un arreglo o en una lista enlazada. Para nuestro ejemplo, utilizaremos una lista enlazada con cabecera."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "class NodoLista:\n",
    "    def __init__(self,info,sgte=None):\n",
    "        self.info=info\n",
    "        self.sgte=sgte\n",
    "class Cola_de_prioridad:\n",
    "    def __init__(self):\n",
    "        self.cabecera=NodoLista(0)\n",
    "    def insert(self,x):\n",
    "        self.cabecera.sgte=NodoLista(x,self.cabecera.sgte)\n",
    "    def extract_max(self):\n",
    "        assert self.cabecera.sgte is not None\n",
    "        p=self.cabecera # apunta al previo del candidato a máximo\n",
    "        r=self.cabecera.sgte\n",
    "        while r.sgte is not None:\n",
    "            if r.sgte.info>p.sgte.info:\n",
    "                p=r\n",
    "            r=r.sgte\n",
    "        x=p.sgte.info # anotamos el valor máximo\n",
    "        p.sgte=p.sgte.sgte # eliminamos el nodo con el máximo\n",
    "        return x\n",
    "    def is_empty(self):\n",
    "        return self.cabecera.sgte is None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "max= 45\n",
      "max= 30\n"
     ]
    }
   ],
   "source": [
    "a=Cola_de_prioridad()\n",
    "a.insert(45)\n",
    "a.insert(12)\n",
    "a.insert(30)\n",
    "print(\"max=\",a.extract_max())\n",
    "a.insert(20)\n",
    "print(\"max=\",a.extract_max())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementación usando una lista ordenada\n",
    "\n",
    "Una implementación un poco más compleja consiste en mantener el conjunto como una lista ordenada. Agregar un elemento requiere recorrer la lista para encontrar el punto de inserción (tiempo $\\Theta(n)$ en el peor caso), pero encontrar el máximo y extrarlo toma tiempo constante si la lista se ordena de mayor a menor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "class NodoLista:\n",
    "    def __init__(self,info,sgte=None):\n",
    "        self.info=info\n",
    "        self.sgte=sgte\n",
    "class Cola_de_prioridad:\n",
    "    def __init__(self):\n",
    "        self.cabecera=NodoLista(0)\n",
    "    def insert(self,x):\n",
    "        p=self.cabecera # al final apuntará al previo del punto de inserción\n",
    "        while p.sgte is not None and x<p.sgte.info:\n",
    "            p=p.sgte        \n",
    "        p.sgte=NodoLista(x,p.sgte)\n",
    "    def extract_max(self):\n",
    "        assert self.cabecera.sgte is not None\n",
    "        x=self.cabecera.sgte.info # anotamos el valor máximo que está en el primer nodo\n",
    "        self.cabecera.sgte=self.cabecera.sgte.sgte # eliminamos el primer nodo\n",
    "        return x\n",
    "    def is_empty(self):\n",
    "        return self.cabecera.sgte is None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "max= 45\n",
      "max= 30\n"
     ]
    }
   ],
   "source": [
    "a=Cola_de_prioridad()\n",
    "a.insert(45)\n",
    "a.insert(12)\n",
    "a.insert(30)\n",
    "print(\"max=\",a.extract_max())\n",
    "a.insert(20)\n",
    "print(\"max=\",a.extract_max())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Las dos implementaciones que hemos visto están en extremos opuestos desde el punto de vista de su eficiencia. En ambas, una oparación toma tiempo constante ($\\Theta(1)$) mientras la otra toma tiempo lineal ($\\Theta(n)$).\n",
    "\n",
    "Veremos a continuación que es posible diseñar una estructura que equilibre de mejor forma el costo de las dos operaciones."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementación usando un _Heap_\n",
    "\n",
    "Un heap es un árbol binario de una forma especial, que permite su almacenamiento sin usar punteros.\n",
    "\n",
    "Este árbol se caracteriza porque tiene todos sus niveles llenos, excepto posiblemente el último, y en ese último nivel, los nodos están lo más a la izquierda posible.\n",
    "\n",
    "![heap-arbol](recursos/heap-arbol.png)\n",
    "\n",
    "Un árbol que cumpla esta condición diremos que tiene \"forma de heap\".\n",
    "\n",
    "Los números bajo cada nodo corresponde a una numeración por niveles, y esa numeración se utiliza para almacenar cada elemento en el casillero respectivo de un arreglo:\n",
    "\n",
    "![heap-arreglo](recursos/heap-arreglo.png)\n",
    "\n",
    "Este arreglo contiene toda la información necesaria para representar al árbol. En efecto, tenemos que la raíz está en el casillero $0$, y además\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\text{hijos del nodo }j &= \\{2j+1,2j+2\\} \\\\\n",
    "\\text{padre del nodo }k &= \\left\\lfloor \\frac{k-1}{2} \\right\\rfloor\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Si hay $n$ casilleros ocupados en el arreglo, cualquier subíndice que sea mayor o igual a $n$ corresponde a un nodo inexistente.\n",
    "\n",
    "Un heap puede utilizarse para implementar una cola de prioridad almacenando los datos de modo que las llaves estén siempre ordenadas de arriba a abajo (a diferencia de un árbol de búsqueda binaria, que ordena sus llaves de izquierda a derecha). En otras palabras, el padre debe tener siempre mejor prioridad que sus hijos. Un árbol que cumple esta condición diremos que tiene \"orden de heap\", y también se dice que es un \"árbol de prioridad\".\n",
    "\n",
    "Por lo tanto, un heap debe satisfacer un invariante consistente en dos condiciones:\n",
    "\n",
    "* Condición estructural: el árbol debe tener \"forma de heap\"\n",
    "* Condición de orden: el árbol debe tener \"orden de heap\"\n",
    "\n",
    "#### Inserción\n",
    "\n",
    "La inserción se realiza agregando el nuevo elemento en la primera posición libre del heap, esto es, el próximo nodo que debería aparecer en el recorrido por niveles o, equivalentemente, un casillero que se agrega al final del arreglo.\n",
    "\n",
    "Después de agregar este elemento, la condición estructural se cumple, pero la condición de orden no tiene por qué cumplirse. Para resolver este problema, si el nuevo elemento es mayor que su padre, se intercambia con él, y ese proceso se repite mientras sea necesario. Una forma de describir esto es diciendo que el nuevo elemento \"trepa\" en el árbol hasta alcanzar el nivel correcto según su prioridad.\n",
    "\n",
    "![heap-ins](recursos/heap-ins.gif)\n",
    "\n",
    "Como la altura del árbol es $\\log_2{n}$ y en cada nivel se hace un trabajo constante, el tiempo que demora esta operación en el peor caso es $\\Theta(\\log{n})$.\n",
    "\n",
    "#### Extracción del máximo\n",
    "\n",
    "El máximo evidentemente está en la raíz del árbol (casillero 0 del arreglo). Al sacarlo de ahí, podemos imaginar que ese lugar queda vacante. Para llenarlo, tomamos al último elemento del heap y lo trasladamos al lugar vacante. En caso de que no esté bien ahí de acuerdo a su prioridad (¡que es lo más probable!), lo hacemos descender intercambiándolo siempre con el mayor de sus hijos. Decimos que este elemento \"se hunde\" hasta su nivel de prioridad.\n",
    "\n",
    "![heap-extract](recursos/heap-extract.gif)\n",
    "\n",
    "Esta operación también demora un tiempo proporcional a la altura del árbol en el peor caso, esto es, $\\Theta(\\log{n})$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "def trepar(a,j): # El elemento a[j] trepa hasta su nivel de prioridad \n",
    "    while j>=1 and a[j]>a[(j-1)//2]:\n",
    "        (a[j],a[(j-1)//2])=(a[(j-1)//2],a[j]) # intercambiamos con el padre\n",
    "        j=(j-1)//2 # subimos al lugar del padre\n",
    "        \n",
    "def hundir(a,j,n): # El elemento a[j] se hunde hasta su nivel de prioridad\n",
    "    while 2*j+1<n: # mientras tenga al menos 1 hijo\n",
    "        k=2*j+1 # el hijo izquierdo\n",
    "        if k+1<n and a[k+1]>a[k]: # el hijo derecho existe y es mayor\n",
    "            k+=1\n",
    "        if a[j]>=a[k]: # tiene mejor prioridad que ambos hijos\n",
    "            break\n",
    "        (a[j],a[k])=(a[k],a[j]) # se intercambia con el mayor de los hijos\n",
    "        j=k # bajamos al lugar del mayor de los hijos\n",
    "    \n",
    "class Heap:\n",
    "    def __init__(self,maxn=100):\n",
    "        self.a=np.zeros(maxn)\n",
    "        self.n=0\n",
    "    def insert(self,x):\n",
    "        assert self.n<len(self.a)\n",
    "        self.a[self.n]=x    \n",
    "        trepar(self.a,self.n)\n",
    "        self.n+=1       \n",
    "    def extract_max(self):\n",
    "        assert self.n>0\n",
    "        x=self.a[0] # esta variable lleva el máximo, el casillero 0 queda vacante\n",
    "        self.n-=1   # achicamos el heap\n",
    "        self.a[0]=self.a[self.n] # movemos el elemento sobrante hacia el casillero vacante\n",
    "        hundir(self.a,0,self.n)\n",
    "        return x\n",
    "    def imprimir(self):\n",
    "        print(self.a[0:self.n])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para poder visualizar el efecto de cada operación, agregamos una operación `imprimir` que muestra el contenido del arreglo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[45.]\n",
      "[45. 12.]\n",
      "[45. 12. 30.]\n",
      "max= 45.0\n",
      "[30. 12.]\n",
      "[30. 12. 20.]\n",
      "max= 30.0\n",
      "[20. 12.]\n"
     ]
    }
   ],
   "source": [
    "a=Heap(10)\n",
    "a.insert(45)\n",
    "a.imprimir()\n",
    "a.insert(12)\n",
    "a.imprimir()\n",
    "a.insert(30)\n",
    "a.imprimir()\n",
    "print(\"max=\",a.extract_max())\n",
    "a.imprimir()\n",
    "a.insert(20)\n",
    "a.imprimir()\n",
    "print(\"max=\",a.extract_max())\n",
    "a.imprimir()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ordenando con una cola de prioridad\n",
    "\n",
    "Las colas de prioridad tienen múltiples aplicaciones, algunas de las cuales veremos más adelante en este curso.\n",
    "\n",
    "Una de las aplicaciones más importantes es para resolver el problema de la ordenación. Dada cualquier implementaciónde una cola de prioridad, se la puede utilizar para construir un algoritmo de ordenación, de la siguiente manera:\n",
    "\n",
    "* Crear una cola de prioridad vacía e insertar en ella todos los elementos del conjunto a ordenar\n",
    "* Luego ir extrayendo máximos sucesivamente. Los elementos irán saliendo de mayor a menor.\n",
    "\n",
    "Para las dos primeras implementaciones de colas de prioridad que vimos (conjunto desordenado y conjunto ordenado) el algoritmo resultate demora tiempo $\\Theta(n^2)$ en el peor caso (y correspone a lso algoritmos de ordenación por selección y ordenación por inserción, respectivamente.\n",
    "\n",
    "En cambio, si se utiliza un heap, el algoritmo resultante demora tiempo $\\Theta(n\\log{n})$ en el peor caso y se llama _Heapsort_. A continuación veremos una versión de Heapsort construída de acuerdo a estas ideas, y más adelante en el curso volveremos sobre el tema, porque es posible optimizar aspectos importantes del algoritmo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Heapsort(a): # Versión preliminar\n",
    "    n=len(a)\n",
    "    h=Heap(n)\n",
    "    # Fase 1: insertamos los elementos en un heap\n",
    "    for k in range(0,n):\n",
    "        h.insert(a[k])\n",
    "    # Fase 2: extraemos el máximo sucesivamente\n",
    "    for k in range(n-1,-1,-1):\n",
    "        a[k]=h.extract_max()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.84809569 0.60699999 0.8400833  0.76749145 0.18499666 0.09499075]\n",
      "[0.09499075 0.18499666 0.60699999 0.76749145 0.8400833  0.84809569]\n"
     ]
    }
   ],
   "source": [
    "a = np.random.random(6)\n",
    "print(a)\n",
    "Heapsort(a)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}