chapter_06.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 6 - Heapsort\n",
    "\n",
    "A heap is a way of representing a nearly binary complete tree as an array. It is a desirable data structure for building priority queues, and was originally conceived to provide an in-memory sorting efficiency of n * log(n). \n",
    "\n",
    "Heaps can be organized such that the root of the tree, which is also the start of the array, is the largest value in the heap. These are called `max-heap`s. Heaps can be ordered in the other way, which is called a `min-heap`.\n",
    "\n",
    "We'll first write a meta-class with the methods that are shared by min and max heap, and then subclass it to create our two kinds of heaps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 319,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from numpy import inf\n",
    "\n",
    "class MetaHeap(object):\n",
    "    \n",
    "    def __init__(self, iterable, null):\n",
    "        self.null = null\n",
    "        self.build(iterable)\n",
    "    \n",
    "    def __getitem__(self, index):\n",
    "        try:\n",
    "            value = self.data[index - 1]\n",
    "        except IndexError:\n",
    "            value = self.null\n",
    "        return value\n",
    "    \n",
    "    def __len__(self):\n",
    "        return len(self.data)\n",
    "    \n",
    "    def __setitem__(self, index, value):\n",
    "        if index > len(self):\n",
    "            self.data.extend( [self.null] * (len(self) // 2) )\n",
    "        self.data[index - 1] = value\n",
    "    \n",
    "    def build(self, iterable):\n",
    "        self.data = iterable\n",
    "        index = len(iterable) // 2 + 1\n",
    "        size = len(iterable)\n",
    "        while index > 0:\n",
    "            self.heapify(index, iterable, size)\n",
    "            index -= 1\n",
    "            \n",
    "    def insert():\n",
    "        pass\n",
    "        \n",
    "    @staticmethod\n",
    "    def left(index):\n",
    "        return 2 * index\n",
    "        \n",
    "    @staticmethod\n",
    "    def parent(index):\n",
    "        return index // 2\n",
    "    \n",
    "    @staticmethod\n",
    "    def right(index):\n",
    "        return 2 * index + 1\n",
    "\n",
    "            \n",
    "class MaxHeap(MetaHeap):\n",
    "\n",
    "    def __init__(self, iterable):\n",
    "        super(MaxHeap, self).__init__(iterable, -inf)\n",
    "         \n",
    "    def heapify(self, index, iterable, size):\n",
    "        \"\"\"Pushes value at index into correct position in iterable\"\"\"\n",
    "        left = self.left(index)\n",
    "        right = self.right(index)\n",
    "        largest = index\n",
    "        if ( left <= size ) and ( self[left] > self[largest] ):\n",
    "            largest = left\n",
    "        if ( right <= size ) and ( self[right] > self[largest] ):\n",
    "            largest = right\n",
    "        if largest != index:\n",
    "            value = self[index]\n",
    "            self[index] = self[largest]\n",
    "            self[largest] = value\n",
    "            self.heapify(largest, self.data, size)\n",
    "\n",
    "    def max(self):\n",
    "        return self[1]  \n",
    "    \n",
    "    def increase_key(self, index, key):\n",
    "        self[index] = key\n",
    "        parent = self.parent(index)\n",
    "        while ( index > 1 ) and ( self[parent] < self[index]):\n",
    "            value = self[index]\n",
    "            self[index] = self[parent]\n",
    "            self[parent] = value\n",
    "            index = parent\n",
    "    \n",
    "    def insert(self, key):\n",
    "        size = len(self) + 1\n",
    "        self[size] = self.null\n",
    "    \n",
    "    def pop(self):\n",
    "        item = self[1]\n",
    "        self[1] = self[len(self)]\n",
    "        size = len(self) - 1\n",
    "        self.heapify(1, self.data, size)\n",
    "        return item\n",
    "            \n",
    "    def sort(self):\n",
    "        index = len(self)\n",
    "        size = len(self)\n",
    "        while index > 1:\n",
    "            max_value = self[1]\n",
    "            self[1] = self[index]\n",
    "            self[index] = max_value\n",
    "            size -= 1\n",
    "            self.heapify(1, self.data, size)\n",
    "            index -= 1\n",
    "        return self.data\n",
    "    \n",
    "        \n",
    "class MinHeap(MetaHeap):\n",
    "\n",
    "    def __init__(self, iterable):\n",
    "        super(MinHeap, self).__init__(iterable, inf)\n",
    "        \n",
    "    def heapify(self, index, iterable, size):\n",
    "        \"\"\"Pushes value at index into correct position in iterable\"\"\"\n",
    "        left = self.left(index)\n",
    "        right = self.right(index)\n",
    "        smallest = index\n",
    "        if ( left <= size ) and ( self[left] < self[smallest] ):\n",
    "            smallest = left\n",
    "        if ( right <= size ) and ( self[right] < self[smallest] ):\n",
    "            smallest = right\n",
    "        if smallest != index:\n",
    "            value = self[index]\n",
    "            self[index] = self[smallest]\n",
    "            self[smallest] = value\n",
    "            self.heapify(smallest, self.data, size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 320,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[19, 18, 14, 17, 10, 12, 13, 16, 8, 9, 1, 11, 5, 2, 6, 15, 7, 3, 0, 4]"
      ]
     },
     "execution_count": 320,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heap = MaxHeap(list(range(20)))\n",
    "heap.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 321,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 2.59 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit MaxHeap(list(range(100))).sort()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Priority queues"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 322,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "19"
      ]
     },
     "execution_count": 322,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heap.max()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 323,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[18, 17, 14, 16, 10, 12, 13, 15, 8, 9, 1, 11, 5, 2, 6, 4, 7, 3, 0, 4]"
      ]
     },
     "execution_count": 323,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heap.pop()\n",
    "heap.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 324,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[18,\n",
       " 17,\n",
       " 14,\n",
       " 16,\n",
       " 10,\n",
       " 12,\n",
       " 13,\n",
       " 15,\n",
       " 8,\n",
       " 9,\n",
       " 1,\n",
       " 11,\n",
       " 5,\n",
       " 2,\n",
       " 6,\n",
       " 4,\n",
       " 7,\n",
       " 3,\n",
       " 0,\n",
       " 4,\n",
       " -inf,\n",
       " -inf,\n",
       " -inf,\n",
       " -inf,\n",
       " -inf,\n",
       " -inf,\n",
       " -inf,\n",
       " -inf,\n",
       " -inf,\n",
       " -inf]"
      ]
     },
     "execution_count": 324,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heap.insert(12)\n",
    "heap.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}