Tips/2016-03-28-Heap-and-Queue.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python 的堆与优先队列\n",
    "\n",
    "Python 中内置的 `heapq` 库和 `queue` 分别提供了堆和优先队列结构，其中优先队列 `queue.PriorityQueue` 本身也是基于 `heapq` 实现的，因此我们这次重点看一下 `heapq`。\n",
    "\n",
    "堆（Heap）是一种特殊形式的完全二叉树，其中父节点的值总是大于子节点，根据其性质，Python 中可以用一个满足 `heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2]` 的列表来实现（`heapq` 也确实是这么做的）。堆可以用于实现调度器（例见：[Python 3.5 之协程](http://blog.rainy.im/2016/03/10/how-the-heck-does-async-await-work-in-python-3-5/)），更常用的是优先队列（例如：[ImageColorTheme](https://github.com/rainyear/ImageColorTheme/blob/master/ict/MMCQ.py#L207)）。\n",
    "\n",
    "`heapq` 提供了下面这些方法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['heappush', 'heappop', 'heapify', 'heapreplace', 'merge', 'nlargest', 'nsmallest', 'heappushpop']\n"
     ]
    }
   ],
   "source": [
    "import heapq\n",
    "print(heapq.__all__)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由于 Heap 是通过列表实现的，我们可以直接用列表创建："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 3, 2]\n"
     ]
    }
   ],
   "source": [
    "from heapq import *\n",
    "heap = []\n",
    "heappush(heap, 3)\n",
    "heappush(heap, 2)\n",
    "heappush(heap, 1)\n",
    "print(heap)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### pop 或 sort 前要确保 heapify\n",
    "\n",
    "或者通过 `heapify` 将普通列表转化为 Heap："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List:  [4, 3, 2, 1, 0]\n",
      "Heap:  [0, 1, 2, 4, 3]\n"
     ]
    }
   ],
   "source": [
    "heap = list(reversed(range(5)))\n",
    "print(\"List: \", heap)\n",
    "heapify(heap)\n",
    "print(\"Heap: \", heap)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "每次从 Heap 中 `pop` 出来的元素都是最小的（因而可以据此实现堆排序）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "heap = [5,4,3,2,1]\n",
    "heapify(heap)\n",
    "print(heappop(heap))\n",
    "print(heappop(heap))\n",
    "print(heappop(heap))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 优先队列\n",
    "\n",
    "`queue.PriorityQueue` 实际上只是对 `heapq` 的简单封装，直接使用其 `heappush`/`heappop` 方法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Inside PriorityQueue:  [(-5, 'Python'), (-4, 'C'), (-3, 'Js')]\n",
      "Python\n",
      "C\n",
      "Js\n"
     ]
    }
   ],
   "source": [
    "from queue import PriorityQueue as PQueue\n",
    "pq = PQueue()\n",
    "pq.put((5 * -1, 'Python'))\n",
    "pq.put((4 * -1, 'C'))\n",
    "pq.put((3 * -1, 'Js'))\n",
    "print(\"Inside PriorityQueue: \", pq.queue) # 内部存储\n",
    "while not pq.empty():\n",
    "    print(pq.get()[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由于 `heapq` 是最小堆，而通常 `PriorityQueue` 用在较大有限制的排前面，所以需要给 `priority * -1`。\n",
    "\n",
    "#### sorted 一定是 Heap，反之未必\n",
    "\n",
    "需要注意的是，虽然 Heap 通过 List 实习，但未经过 `heapify()` 处理的仍然是一个普通的 List，而 `heappush` 和 `heappop` 操作每次都会对 Heap 进行重新整理。此外，一个 Heap 列表不一定是正确排序的，但是经过 `list.sort()` 的列表一定是 Heap："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List:  [24, 55, 81, 83, 87]\n",
      "Poped:  24\n",
      "Heap:  [4, 55, 81, 87, 83]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "lst = [random.randrange(1, 100) for _ in range(5)]\n",
    "lst.sort()\n",
    "print(\"List: \", lst)\n",
    "print(\"Poped: \", heappop(lst))\n",
    "heappush(lst, 4)\n",
    "print(\"Heap: \", lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 最大/最小的 N 个数\n",
    "\n",
    "Heap 还提供了 `nsmallest` 和 `nlargest` 方法用于取出前 n 个最大/最小数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "N largest:  [999, 999, 998, 994, 992, 991, 990, 988, 985, 982]\n",
      "N smallest:  [1, 1, 1, 2, 4, 5, 5, 6, 6, 9]\n",
      "1000\n"
     ]
    }
   ],
   "source": [
    "heap = [random.randrange(1, 1000) for _ in range(1000)]\n",
    "heapify(heap)\n",
    "print(\"N largest: \", nlargest(10, heap))\n",
    "print(\"N smallest: \", nsmallest(10, heap))\n",
    "print(len(heap))  # 不原地修改"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 合并（排序）\n",
    "\n",
    "`merge` 方法用于将两个 Heap 进行合并："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 29, 66, 66, 70, 99]\n"
     ]
    }
   ],
   "source": [
    "heapA = sorted([random.randrange(1, 100) for _ in range(3)])\n",
    "heapB = sorted([random.randrange(1, 100) for _ in range(3)])\n",
    "\n",
    "merged = []\n",
    "for i in merge(heapA, heapB):\n",
    "    merged.append(i)\n",
    "print(merged)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最后两个方法 `heapreplace` 和 `heappushpop` 分别相当于："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lstA:  [0, 2, 3, 4, 5] poped:  1\n",
      "lstB:  [0, 2, 3, 4, 5] poped:  1\n",
      "******************************\n",
      "lstA:  [2, 4, 3, 9, 5] poped:  0\n",
      "lstB:  [2, 4, 3, 5, 9] poped:  0\n"
     ]
    }
   ],
   "source": [
    "lstA = [1,2,3,4,5]\n",
    "lstB = [1,2,3,4,5]\n",
    "\n",
    "poped = heapreplace(lstA, 0)\n",
    "print(\"lstA: \", lstA, \"poped: \", poped)\n",
    "\n",
    "# is equal to...\n",
    "poped = heappop(lstB)\n",
    "heappush(lstB, 0)\n",
    "print(\"lstB: \", lstA, \"poped: \", poped)\n",
    "\n",
    "print(\"*\"*30)\n",
    "\n",
    "poped = heappushpop(lstA, 9)\n",
    "print(\"lstA: \", lstA, \"poped: \", poped)\n",
    "\n",
    "# is equal to...\n",
    "heappush(lstB, 9)\n",
    "poped = heappop(lstB)\n",
    "print(\"lstB: \", lstB, \"poped: \", poped)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这两个方法的执行效率要比分开写的方法高，但要注意 `heapreplace` 要取代的值是否比 `heap[0]` 大，如果不是，可以用更有效的方法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lstA:  [0, 2, 3, 4, 5] poped:  1\n"
     ]
    }
   ],
   "source": [
    "item = 0\n",
    "lstA = [1,2,3,4,5]\n",
    "if item < lstA[0]:\n",
    "    # replace\n",
    "    poped = lstA[0]\n",
    "    lstA[0] = item\n",
    "    print(\"lstA: \", lstA, \"poped: \", poped)"
   ]
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}