{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Priority Queues\n",
    "\n",
    "## Agenda\n",
    "\n",
    "1. Motives\n",
    "2. Naive implementation\n",
    "2. Heaps\n",
    "    - Mechanics\n",
    "    - Implementation\n",
    "    - Run-time Analysis\n",
    "3. Heapsort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Motives"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Naive implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class PriorityQueue:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "        \n",
    "    def add(self, x):\n",
    "        pass\n",
    "    \n",
    "    def max(self):\n",
    "        pass\n",
    "\n",
    "    def pop_max(self):\n",
    "        pass\n",
    "    \n",
    "    def __bool__(self):\n",
    "        return len(self.data) > 0\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self.data)\n",
    "\n",
    "    def __repr__(self):\n",
    "        return repr(self.data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "pq = PriorityQueue()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "for _ in range(10):\n",
    "    pq.add(random.randrange(100))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "pq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "while pq:\n",
    "    print(pq.pop_max())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Heaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mechanics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Heap:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "\n",
    "    def add(self, x):\n",
    "        pass\n",
    "    \n",
    "    def max(self):\n",
    "        pass\n",
    "\n",
    "    def pop_max(self):\n",
    "        pass\n",
    "    \n",
    "    def __bool__(self):\n",
    "        return len(self.data) > 0\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self.data)\n",
    "\n",
    "    def __repr__(self):\n",
    "        return repr(self.data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "h = Heap()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "for _ in range(10):\n",
    "    h.add(random.randrange(100))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "while h:\n",
    "    print(h.pop_max())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Run-time Analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Heapsort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def heapsort(iterable):\n",
    "    heap = Heap()\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def pairs(iterable):\n",
    "    it = iter(iterable)\n",
    "    a = next(it)\n",
    "    while True:\n",
    "        b = next(it)\n",
    "        yield a,b\n",
    "        a = b\n",
    "\n",
    "lst = heapsort(random.random() for _ in range(1000))\n",
    "all((a <= b) for a, b in pairs(lst))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import timeit\n",
    "def time_heapsort(n):\n",
    "    return timeit.timeit('heapsort(rlst)',\n",
    "                         'from __main__ import heapsort; '\n",
    "                         'import random; '\n",
    "                         'rlst = (random.random() for _ in range({}))'.format(n),\n",
    "                         number=1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "ns = np.linspace(100, 10000, 50, dtype=np.int_)\n",
    "plt.plot(ns, [time_heapsort(n) for n in ns], 'r+')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "ns = np.linspace(100, 10000, 50, dtype=np.int_)\n",
    "plt.plot(ns, [time_heapsort(n) for n in ns], 'r+')\n",
    "plt.plot(ns, ns*np.log2(ns)*0.01/10000, 'b') # O(n log n) plot\n",
    "plt.show()"
   ]
  }
 ],
 "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}