Colab_Codes/chapter_python_datastrcutures.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "chapter_python_datastrcutures.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/liyin2015/Algorithms-and-Coding-Interviews/blob/master/chapter_python_datastrcutures.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "f3PH6cZu5ori",
        "colab_type": "text"
      },
      "source": [
        "### Sequence\n",
        "#### List"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VBKkaaiS5lhk",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "lst_lst = [[], [1], ['1'], [1, 2], ['1', '2']]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qjrTbHg_5xMR",
        "colab_type": "code",
        "outputId": "835af2d0-bc33-45af-f56a-c94d7b8408ac",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "import sys\n",
        "for lst in lst_lst:\n",
        "  print(sys.getsizeof(lst), end=' ')\n",
        "print(sys.getsizeof(lst_lst))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "64 72 72 80 80 104\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WpkbbrQISfWR",
        "colab_type": "text"
      },
      "source": [
        "print('compare the length and the additiobal memory size in bytes')"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XS34IasNPvcJ",
        "colab_type": "code",
        "outputId": "00a3e7c4-431b-40cb-fb99-7265004f2077",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 312
        }
      },
      "source": [
        "a = []\n",
        "for size in range(17):\n",
        "  a.insert(0, size)\n",
        "  print('size:', len(a), 'bytes:', (sys.getsizeof(a)-64)//8, 'id:', id(a))\n",
        "  "
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "size: 1 bytes: 4 id: 139702851424712\n",
            "size: 2 bytes: 4 id: 139702851424712\n",
            "size: 3 bytes: 4 id: 139702851424712\n",
            "size: 4 bytes: 4 id: 139702851424712\n",
            "size: 5 bytes: 8 id: 139702851424712\n",
            "size: 6 bytes: 8 id: 139702851424712\n",
            "size: 7 bytes: 8 id: 139702851424712\n",
            "size: 8 bytes: 8 id: 139702851424712\n",
            "size: 9 bytes: 16 id: 139702851424712\n",
            "size: 10 bytes: 16 id: 139702851424712\n",
            "size: 11 bytes: 16 id: 139702851424712\n",
            "size: 12 bytes: 16 id: 139702851424712\n",
            "size: 13 bytes: 16 id: 139702851424712\n",
            "size: 14 bytes: 16 id: 139702851424712\n",
            "size: 15 bytes: 16 id: 139702851424712\n",
            "size: 16 bytes: 16 id: 139702851424712\n",
            "size: 17 bytes: 25 id: 139702851424712\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JsLMOxtfKKHY",
        "colab_type": "text"
      },
      "source": [
        "### Tuple"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6pW_iKdQccTi",
        "colab_type": "code",
        "outputId": "0cf35433-af54-4bc4-ff2a-864af0f00f1b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "record1 = ('Bob', 12345, 89)\n",
        "from collections import namedtuple\n",
        "Record = namedtuple('Computer_Science', 'name id score')\n",
        "record2 = Record('Bob', id=12345, score=89)\n",
        "print(record1, record2)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "('Bob', 12345, 89) Computer_Science(name='Bob', id=12345, score=89)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jtg_FHoGZXRV",
        "colab_type": "code",
        "outputId": "3685bfb8-f91e-449e-b943-765d83efc5ce",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "a=()\n",
        "b=(1)\n",
        "c=(1,)\n",
        "print(type(a), type(b), type(c))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "<class 'tuple'> <class 'int'> <class 'tuple'>\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BjCNDU8bKMEF",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "lst_tup = [(), (1,), ('1',), (1, 2), ('1', '2')]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7Bozw-YBKRs-",
        "colab_type": "code",
        "outputId": "f5f821d5-c2d3-4cac-f03f-d8f70c1881c1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "import sys\n",
        "for tup in lst_tup:\n",
        "  print(sys.getsizeof(tup), end=' ')\n",
        "  "
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "48 56 56 64 64 "
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "n5Sm5NJVn9ON",
        "colab_type": "text"
      },
      "source": [
        "### String"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9C-_UxZSn_hM",
        "colab_type": "code",
        "outputId": "6a32a157-1ea5-475e-d535-da7662f9e10a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "lst_string = ['', str(), \"\",'b', 'ab', 'abc', 'abcd']\n",
        "import sys\n",
        "for string in lst_string:\n",
        "  print(sys.getsizeof(string), end=' ')"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "53 53 53 58 51 52 53 "
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "z9fadMw_dfJD",
        "colab_type": "text"
      },
      "source": [
        "### Experiments about tuple and list"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aiznFcZLQnRB",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "## experiment\n",
        "\n",
        "def iterate(obj):\n",
        "  for _ in obj:\n",
        "    pass"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mtsz7-awQzKb",
        "colab_type": "code",
        "outputId": "6e01af72-c00e-4362-e660-a4be0a11bfdb",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 69
        }
      },
      "source": [
        "a = [1]*100000\n",
        "b =(1,)*100000\n",
        "print(type(b))\n",
        "%timeit iterate(a)\n",
        "%timeit iterate(b)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "<class 'tuple'>\n",
            "1000 loops, best of 3: 774 µs per loop\n",
            "1000 loops, best of 3: 768 µs per loop\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ptmcUSMS7LX-",
        "colab_type": "code",
        "outputId": "88f51fdf-6d44-4aae-9a1f-2faf93e89f08",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 106
        }
      },
      "source": [
        "print(dir(1))#print all attributes\n",
        "print(isinstance(1, int)) # check instance type\n",
        "print(isinstance(1, float))\n",
        "o=object()\n",
        "print(dir(o))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "['__abs__', '__add__', '__and__', '__bool__', '__ceil__', '__class__', '__delattr__', '__dir__', '__divmod__', '__doc__', '__eq__', '__float__', '__floor__', '__floordiv__', '__format__', '__ge__', '__getattribute__', '__getnewargs__', '__gt__', '__hash__', '__index__', '__init__', '__init_subclass__', '__int__', '__invert__', '__le__', '__lshift__', '__lt__', '__mod__', '__mul__', '__ne__', '__neg__', '__new__', '__or__', '__pos__', '__pow__', '__radd__', '__rand__', '__rdivmod__', '__reduce__', '__reduce_ex__', '__repr__', '__rfloordiv__', '__rlshift__', '__rmod__', '__rmul__', '__ror__', '__round__', '__rpow__', '__rrshift__', '__rshift__', '__rsub__', '__rtruediv__', '__rxor__', '__setattr__', '__sizeof__', '__str__', '__sub__', '__subclasshook__', '__truediv__', '__trunc__', '__xor__', 'bit_length', 'conjugate', 'denominator', 'from_bytes', 'imag', 'numerator', 'real', 'to_bytes']\n",
            "True\n",
            "False\n",
            "['__class__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__le__', '__lt__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__']\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8zZI8X9MFHXY",
        "colab_type": "code",
        "outputId": "9f5b0584-52ae-4ad0-ba6e-85e46d630cd3",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 217
        }
      },
      "source": [
        "eg_tuple = ([1,2,3], '3', '4')\n",
        "eg_tuple[0].append(4)\n",
        "print(eg_tuple)\n",
        "eg_tuple[0]=[1]"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "([1, 2, 3, 4], '3', '4')\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "error",
          "ename": "TypeError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-12-4b3290314903>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0meg_tuple\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0meg_tuple\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0meg_tuple\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;31mTypeError\u001b[0m: 'tuple' object does not support item assignment"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cRwZzC1nbya-",
        "colab_type": "text"
      },
      "source": [
        "## Linked List\n",
        "### Singly Linked List"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_bOzVhCsb2r2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class Node(object):\n",
        "  def __init__(self, val = None):\n",
        "    self.val = val\n",
        "    self.next = None"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JBELJl1Mg_5t",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "head = None"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7HNDqOpYv1eQ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "head = Node(None)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aaFT7eqJiBOh",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def append(head, val):\n",
        "  node = Node(val)\n",
        "  cur = head\n",
        "  while cur.next:\n",
        "    cur = cur.next\n",
        "  cur.next = node\n",
        "  return"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mgqoX1FvlQ6e",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "for val in ['A', 'B', 'C', 'D']:\n",
        "  append(head, val)\n",
        "print(head)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "r6jguLJ2ncuk",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def iter(head):\n",
        "    cur = head.next\n",
        "    while cur:\n",
        "      yield cur\n",
        "      cur = cur.next"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fr2smn7KnlLr",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "for node in iter(head):\n",
        "  print(node.val, end = ' ')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "slfA4hZKp39X",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def search(head, val):\n",
        "  for node in iter(head):\n",
        "    if node.val == val:\n",
        "      return node\n",
        "  return None"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "O8pCCYD5rvSa",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "node = search(head, 'B')\n",
        "print(node)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mD-zaFfktkuU",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Delete 'B'\n",
        "def deleteByNode(node):\n",
        "    node.val = node.next.val\n",
        "    node.next = node.next.next\n",
        "    return node"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2Xl5HJaNts6e",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "deleteByNode(node)\n",
        "for n in iter(head):\n",
        "  print(n.val, end = ' ')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DA9EM3JWzApy",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def delete(head, val):\n",
        "    cur = head.next # start from dummy node\n",
        "    prev = head\n",
        "    while cur:\n",
        "        if cur.val == val:\n",
        "            # rewire\n",
        "            prev.next = cur.next\n",
        "            return\n",
        "        prev = cur\n",
        "        cur = cur.next"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bEyQTqp_zsyT",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "delete(head,'A')\n",
        "for n in iter(head):\n",
        "  print(n.val, end = ' ')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ahdQYQ4l01Xf",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def clear(head):\n",
        "  head.next = None"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "eZ1FMYEH05vq",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "clear(head)\n",
        "for n in iter(head):\n",
        "  print(n.val, end = ' ')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tzyU7Uf-2Fa7",
        "colab_type": "text"
      },
      "source": [
        "### Doubly Linked List"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aBPpNAi6hAiS",
        "colab_type": "text"
      },
      "source": [
        "#### Class"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZyASd_JKe2mI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class SinglyLinkeList:\n",
        "    def __init__(self):\n",
        "        self.head = None\n",
        "        self.size = 0\n",
        "        \n",
        "    def len(self):\n",
        "        return self.size\n",
        "      \n",
        "    def append(self, val):\n",
        "        node = SinglyLinkedNode(val)\n",
        "        if self.head:\n",
        "            current = self.head\n",
        "            while current:\n",
        "                current = current.next\n",
        "            current.next = node\n",
        "        else:\n",
        "            self.head = node\n",
        "        self.size += 1\n",
        "\n",
        "    def delete(self, val):\n",
        "        current = self.head\n",
        "        prev = self.head\n",
        "        while current:\n",
        "            if current.val == val:\n",
        "                # if the node is head\n",
        "                if current == self.head:\n",
        "                    self.head = current.next\n",
        "                # rewire\n",
        "                else:\n",
        "                    prev.next = current.next\n",
        "                self.size -= 1\n",
        "            prev = current\n",
        "            current = current.next\n",
        "\n",
        "    def deleteByNode(self, node):\n",
        "        node.val = node.next.val\n",
        "        node.next = node.next.next\n",
        "        \n",
        "    def iter(self):\n",
        "        current = self.head\n",
        "        while current:\n",
        "          val = current.val\n",
        "          current = current.next\n",
        "          yield val\n",
        "          \n",
        "    def search(self, val):\n",
        "        for value in self.iter():\n",
        "            if value == val:\n",
        "                return True\n",
        "        return False\n",
        "      \n",
        "   def clear(self):\n",
        "      self.head = None\n",
        "      self.size = 0"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lRzzlJK2b4Rc",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "head = Node('A')\n",
        "print(head)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "torUZUYliBhC",
        "colab_type": "text"
      },
      "source": [
        "## Heap\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "IXOKDdj0iGks",
        "colab_type": "text"
      },
      "source": [
        "### push"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qjBdqfnyISQg",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "'''\n",
        "Enforce min-heap property, leaf-to-root\n",
        "'''\n",
        "def _float(idx, heap): \n",
        "  while idx // 2: \n",
        "      p = idx // 2\n",
        "      # Violation\n",
        "      if heap[idx] < heap[p]:\n",
        "          heap[idx], heap[p] = heap[p], heap[idx]\n",
        "      else:\n",
        "        break\n",
        "      idx = p \n",
        "  return\n",
        "\n",
        "def push(heap, k):\n",
        "  heap.append(k)\n",
        "  _float(idx = len(heap) - 1, heap=heap)\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ICFvjZoAz-uh",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "heap = [None, 6, 7, 12, 10, 15, 17] \n",
        "push(heap, 5)\n",
        "print(heap)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "09fdIkas1RxR",
        "colab_type": "text"
      },
      "source": [
        "### Pop"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "S0lEx88ARQgE",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def _sink(idx, heap): \n",
        "  size = len(heap)\n",
        "  while 2 * idx < size:\n",
        "    li = 2 * idx\n",
        "    ri = li + 1\n",
        "    mi = idx\n",
        "    if heap[li] < heap[mi]:\n",
        "      mi = li\n",
        "    if ri < size and heap[ri] < heap[mi]:\n",
        "      mi = ri\n",
        "    if mi != idx:\n",
        "        # swap index with mi\n",
        "        heap[idx], heap[mi] = heap[mi], heap[idx]\n",
        "    else:\n",
        "      break\n",
        "    idx = mi\n",
        "\n",
        "def pop(heap):\n",
        "    val = heap[1]\n",
        "    # Move the last item into the root position\n",
        "    heap[1] = heap.pop()\n",
        "    _sink(idx=1, heap=heap)\n",
        "    return val"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "10cRJ3MCSzaO",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "k = pop(heap)\n",
        "print(k, heap)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "58m92FBiqRMp",
        "colab_type": "text"
      },
      "source": [
        "### Heapify"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yk3HbmPHqPk8",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def _sink(idx, heap): \n",
        "  size = len(heap)\n",
        "  while 2 * idx < size:\n",
        "    li = 2 * idx\n",
        "    ri = li + 1\n",
        "    mi = idx\n",
        "    if heap[li] < heap[mi]:\n",
        "      mi = li\n",
        "    if ri < size and heap[ri] < heap[mi]:\n",
        "      mi = ri\n",
        "    if mi != idx:\n",
        "        # swap index with mi\n",
        "        heap[idx], heap[mi] = heap[mi], heap[idx]\n",
        "    else:\n",
        "      break\n",
        "    idx = mi\n",
        "\n",
        "def heapify(lst):\n",
        "    heap = [None] + lst\n",
        "    n = len(lst)\n",
        "    for i in range(n//2, 0, -1):\n",
        "      _sink(i, heap)\n",
        "    return heap"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sItWBj0CyXI7",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "a = [21, 1, 45, 78, 3, 5]\n",
        "heapify(a)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vfd0-49zzW-9",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def _float(idx, heap): \n",
        "  while idx // 2: \n",
        "      p = idx // 2\n",
        "      # Violation\n",
        "      if heap[idx] < heap[p]:\n",
        "          heap[idx], heap[p] = heap[p], heap[idx]\n",
        "      # else:\n",
        "      #   break\n",
        "      idx = p \n",
        "  return\n",
        "\n",
        "\n",
        "def heapify(lst):\n",
        "    heap = [None] + lst\n",
        "    n = len(lst)\n",
        "    for i in range(n, n//2, -1):\n",
        "      _float(i, heap)\n",
        "    return heap"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JLTpZvJiziSb",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "a = [21, 1, 45, 78, 3, 5]\n",
        "heapify(a)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZU3Y9FdTOJy1",
        "colab_type": "text"
      },
      "source": [
        "## Python Heapq"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6X_33HRdOM70",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from heapq import heappush, heappop, heapify\n",
        "h = [21, 1, 45, 78, 3, 5]\n",
        "heapify(h)\n",
        "h"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6sKjGWBcVzWj",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "heappop(h)\n",
        "heappush(h, 15)\n",
        "h"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "r5EZnDW6XGFN",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from heapq import nlargest, nsmallest\n",
        "h = [21, 1, 45, 78, 3, 5]\n",
        "nl = nlargest(3, h)\n",
        "ns = nsmallest(3, h)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9HBRESbMXdU9",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "print(nl)\n",
        "print(ns)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hTp-vCjabfip",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Efficiency\n",
        "import random\n",
        "h = [random.randint(1, 1000) for _ in range(10000)]\n",
        "%time nl = nlargest(3, h)\n",
        "%time ns = nsmallest(3, h)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8wdwg2Ora5L9",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "%time h.sort()\n",
        "%time nl = h[:3]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ad-PPc_5YOOM",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Merge\n",
        "from heapq import merge\n",
        "a = [1, 3, 5, 21, 45, 78]\n",
        "b = [2, 4, 8, 16]\n",
        "ab = merge(a, b)\n",
        "ab"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wrR9-VeiaLVU",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "ab_lst = [n for n in ab]\n",
        "ab_lst"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bDrjp_ATY9Vr",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "for n in ab:\n",
        "  print(n, end=' ')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "n3xnm-3_cuN0",
        "colab_type": "text"
      },
      "source": [
        "#### Max heap"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "o0v6p3A4cv5S",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from heapq import _heapify_max\n",
        "h = [21, 1, 45, 78, 3, 5]\n",
        "_heapify_max(h)\n",
        "h"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tYh_pTBHdKXC",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from heapq import _heapify_max\n",
        "h = [21, 1, 45, 78, 3, 5]\n",
        "h = [-n for n in h]\n",
        "heapify(h)\n",
        "a = -heappop(h)\n",
        "a"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "I0IsJlmz18CZ",
        "colab_type": "text"
      },
      "source": [
        "### Heap with More Operations\n",
        "\n",
        "Random access and change of value"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fHEzP69W2EYx",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import heapq\n",
        "heap = [[3, 'a'], [10, 'b'], [5,'c'], [8, 'd']]\n",
        "heapify(heap)\n",
        "print(heap)\n",
        "\n",
        "heap[0] = [6, 'a']\n",
        "# Increased value\n",
        "heapq._siftup(heap, 0) \n",
        "print(heap)\n",
        "#Decreased Value\n",
        "heap[2] = [3, 'a']\n",
        "heapq._siftdown(heap, 0, 2)\n",
        "print(heap)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aQzfFn7M-vO8",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# tasks with same priorities\n",
        "h = [[3, 'e'], [3, 'd'], [10, 'c'], [5,'b'], [3, 'a']]\n",
        "heapify(h)\n",
        "print(h)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Q5E_Ne9POTdu",
        "colab_type": "text"
      },
      "source": [
        "## Priority Queue"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "I2PUG9MpPmjH",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from dataclasses import dataclass, field\n",
        "from typing import Any\n",
        "\n",
        "@dataclass(order=True)\n",
        "class PrioritizedItem:\n",
        "    priority: int\n",
        "    item: Any=field(compare=False)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "feBiuMDQPrK1",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# it does not seem working\n",
        "h = [PrioritizedItem(3, 'c'), PrioritizedItem(3, 'a'), PrioritizedItem(10, 'b'), PrioritizedItem(5,'c'), PrioritizedItem(3, 'b')]\n",
        "heapify(h)\n",
        "print(h)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Krf5b7uxoA6a",
        "colab_type": "text"
      },
      "source": [
        "### With heapq"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MEZVoPbkAaM0",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Add counter as a tie-breaker so that sort stability is kept\n",
        "import itertools\n",
        "counter = itertools.count()\n",
        "h = [[3, 'e'], [3, 'd'], [10, 'c'], [5,'b'], [3, 'a']]\n",
        "h = [[p, next(counter), t] for p, t in h]\n",
        "print(h)\n",
        "heapify(h)\n",
        "h"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8HTtbM3FiKaE",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Removed mark\n",
        "REMOVED = '<removed-task>'\n",
        "# Remove task 'd'\n",
        "h[1][2] = REMOVED\n",
        "# Updata task 'b''s proprity to 14\n",
        "h[3][2] = REMOVED\n",
        "heappush(h, [14, next(counter), 'b'])\n",
        "vh = []\n",
        "while h:\n",
        "  item = heappop(h)\n",
        "  if item[2] != REMOVED:\n",
        "    vh.append(item)\n",
        "vh\n",
        "  "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EX-43EOHiAuK",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# A heap associated with entry_finder\n",
        "counter = itertools.count()\n",
        "entry_finder = {}\n",
        "h = [[3, 'e'], [3, 'd'], [10, 'c'], [5,'b'], [3, 'a']]\n",
        "heap = []\n",
        "for p, t in h:\n",
        "  item = [p, next(counter), t]\n",
        "  heap.append(item)\n",
        "  entry_finder[t] = item\n",
        "heapify(heap)\n",
        "print(heap)\n",
        "print(entry_finder)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yc1LDeRyrzd5",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# With entry_finder\n",
        "REMOVED = '<removed-task>'\n",
        "def remove_task(task_id):\n",
        "  if task_id in entry_finder:\n",
        "    entry_finder[task_id][2] = REMOVED\n",
        "    entry_finder.pop(task_id) # delete from the dictionary\n",
        "  return\n",
        "\n",
        "# Remove task 'd'\n",
        "remove_task('d')\n",
        "# Updata task 'b''s priority to 14\n",
        "remove_task('b')\n",
        "new_item = [14, next(counter), 'b']\n",
        "heappush(heap, new_item)\n",
        "entry_finder['b'] = new_item\n",
        "\n",
        "print(heap)\n",
        "vh = []\n",
        "while heap:\n",
        "  item = heappop(heap)\n",
        "  if item[2] != REMOVED:\n",
        "    vh.append(item)\n",
        "vh"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4DtjHkQ0oGzO",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# A heapq based priority queue class\n",
        "from heapq import heappush, heappop, heapify\n",
        "from typing import List\n",
        "import itertools\n",
        "class PriorityQueue:\n",
        "  def __init__(self, items:List[List]=[]):\n",
        "      self.heap = []\n",
        "      self.entry_finder = {} \n",
        "      self.REMOVED = '<removed-task>'\n",
        "      self.counter = itertools.count()  \n",
        "      # Add items to heap\n",
        "      for p, t in items:\n",
        "        item = [p, next(self.counter), t]\n",
        "        self.entry_finder[t] = item\n",
        "        self.heap.append(item)\n",
        "      heapify(self.heap)\n",
        "        \n",
        "  def add_task(self, task, priority=0):\n",
        "      'Add a new task or update the priority of an existing task'\n",
        "      if task in self.entry_finder:\n",
        "          self.remove_task(task)\n",
        "      count = next(self.counter)\n",
        "      item = [priority, count, task]\n",
        "      self.entry_finder[task] = item\n",
        "      heappush(self.heap, item)\n",
        "      \n",
        "  def remove_task(self, task):\n",
        "      'Mark an existing task as REMOVED.  Raise KeyError if not found.'\n",
        "      entry = self.entry_finder.pop(task)\n",
        "      entry[-1] = self.REMOVED\n",
        "\n",
        "  def pop_task(self):\n",
        "      'Remove and return the lowest priority task. Raise KeyError if empty.'\n",
        "      while self.heap:\n",
        "          priority, count, task = heappop(self.heap)\n",
        "          if task is not self.REMOVED:\n",
        "              del self.entry_finder[task]\n",
        "              return task\n",
        "      raise KeyError('pop from an empty priority queue')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0Ad-zEmD-4hW",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "pq = PriorityQueue([[3, 'e'], [3, 'd'], [10, 'c'], [5,'b'], [3, 'a']])\n",
        "pq.remove_task('d')\n",
        "pq.add_task('b', 14)\n",
        "vh = []\n",
        "print(pq.heap)\n",
        "while pq.heap:\n",
        "  task_id = pq.pop_task()\n",
        "  vh.append(task_id)\n",
        "print(vh)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "B3mm_e1-oDbx",
        "colab_type": "text"
      },
      "source": [
        "### With PriorityQueue()"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "y-PvMDzG0k1h",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from queue import PriorityQueue\n",
        "data = [[3, 'e'], [3, 'd'], [10, 'c'], [5,'b'], [3, 'a']]\n",
        "pq = PriorityQueue()\n",
        "for d in data:\n",
        "  pq.put(d)\n",
        "  \n",
        "process_order = []\n",
        "while not pq.empty():\n",
        "  process_order.append(pq.get())\n",
        "process_order"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ReGWutff4DAt",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import itertools\n",
        "from dataclasses import dataclass, field\n",
        "\n",
        "@dataclass(repr=True, order=True)\n",
        "class Job:\n",
        "  counter = itertools.count()\n",
        "  priority: float\n",
        "  task: str = field(compare=False)\n",
        "  count: int = next(Job.counter)\n",
        "  \n",
        "\n",
        "  # def __init__(self, priority, task):\n",
        "  #   self.priority = priority\n",
        "  #   self.count = next(Job.counter)\n",
        "  #   self.task = task\n",
        "\n",
        "  # def __lt__(self, other): \n",
        "  #     try:\n",
        "  #         return [self.priority, self.count] < [other.priority, other.count]\n",
        "  #     except AttributeError:\n",
        "  #         return NotImplemented\n",
        "  # def __eq__(self, other): \n",
        "  #     try:\n",
        "  #         return [self.priority, self.count] == [other.priority, other.count]\n",
        "  #     except AttributeError:\n",
        "  #         return NotImplemented\n",
        "  # def __cmp__(self, other):\n",
        "  #   return cmp([self.priority, self.count], [other.priority, other.count])\n",
        "    "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kdZxnhAa9aRM",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "@dataclass\n",
        "class C:\n",
        "    x: int\n",
        "    y: int = field(repr=False)\n",
        "    z: int = field(repr=False, default=10)\n",
        "    t: int = 20\n",
        "\n",
        "a = C(1, 2)\n",
        "print(a)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3FWTCf9z5Mat",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "data = [[3, 'e'], [3, 'd'], [10, 'c'], [5,'b'], [3, 'a']]\n",
        "pq = PriorityQueue()\n",
        "for p, t in data:\n",
        "  pq.put(Job(p, t))\n",
        "  \n",
        "process_order = []\n",
        "while not pq.empty():\n",
        "  process_order.append(pq.get())\n",
        "process_order"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mtOycJegCj8K",
        "colab_type": "text"
      },
      "source": [
        "### Hands-on examples"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jLcY0VH4CmTk",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "nums = [1,1,1,2,2,3]\n",
        "k = 2"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OVFTSwrNCqUn",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from collections import Counter\n",
        "topk = [x for x, _ in Counter(nums).most_common(k)]\n",
        "print(topk)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZeOezbL9DRmb",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import heapq\n",
        "count = Counter(nums)\n",
        "# Use the value to compare with\n",
        "topk = heapq.nlargest(k, count.keys(), key=lambda x: count[x])\n",
        "topk"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KPrKjREaFPhD",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from  queue  import  PriorityQueue\n",
        "count = Counter(nums)\n",
        "pq = PriorityQueue()\n",
        "for key, c in count.items():\n",
        "  pq.put((-c, key))\n",
        "\n",
        "topk =  [pq.get()[1] for i in range(k)]\n",
        "topk\n"
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}