python_lesson4_data_structures2/lesson4_part1_data_structures.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"../img/python_theme.png\">\n",
    "# MLClass. \"Прикладной анализ данных\"\n",
    "# Модуль \"Инструментарий Data Science\"\n",
    "<img src=\"../img/mlclass_logo.jpg\" height=\"240\" width=\"240\">\n",
    "\n",
    "## Автор материала: Юрий Кашницкий, ФКН НИУ ВШЭ\n",
    "</center>\n",
    "Материал распространяется на условиях лицензии <a href=\"https://opensource.org/licenses/MS-RL\">Ms-RL</a>. Можно использовать в любых целях, кроме коммерческих, но с обязательным упоминанием автора материала."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Урок 4. Структуры данных II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Часть 1. Стек, очередь, дерево, куча, граф"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Python 2 and 3 compatibility\n",
    "# pip install future\n",
    "from __future__ import (absolute_import, division,\n",
    "                        print_function, unicode_literals)\n",
    "from builtins import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Стек"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Стек** (иногда говорят “магазин/обойма” - по аналогии с магазином огнестрельного оружия) - это упорядоченная коллекция элементов, где добавление нового или удаление существующего всегда происходит только на одном из концов. Этот конец обычно называют “вершиной”, а противоположный ему - “основанием”."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Организован по принципу **LIFO**, last-in, first-out (англ. «последним пришёл — первым вышел»). Он предоставляет упорядочение по времени нахождения в коллекции. Более новые элементы расположены ближе к вершине, более старые - ближе к основанию."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Операции со стеком"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **Stack()** - создаёт новый пустой стек.\n",
    "   Параметры не нужны, возвращает пустой стек.\n",
    "2. **push(item)** - добавляет новый элемент на вершину стека. \n",
    "   В качестве параметра выступает элемент; функция ничего не возвращает.\n",
    "3. **pop()** - удаляет верхний элемент из стека. \n",
    "   Параметры не требуются, функция возвращает элемент. Стек изменяется.\n",
    "4. **peek()** - возвращает верхний элемент стека, но не удаляет его. \n",
    "   Параметры не требуются, стек не модифицируется.\n",
    "5. **isEmpty()** - проверяет стек на пустоту. \n",
    "   Параметры не требуются, возвращает булево значение.\n",
    "6. **size()** - возвращает количество элементов в стеке. \n",
    "   Параметры не требуются, тип результата - целое число."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Реализация с помощью списка"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Stack:\n",
    "     def __init__(self):\n",
    "         self.items = []\n",
    "\n",
    "     def isEmpty(self):\n",
    "         return self.items == []\n",
    "\n",
    "     def push(self, item):\n",
    "         self.items.append(item)\n",
    "\n",
    "     def pop(self):\n",
    "         return self.items.pop()\n",
    "\n",
    "     def peek(self):\n",
    "         return self.items[-1]\n",
    "\n",
    "     def size(self):\n",
    "         return len(self.items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true\n",
      "hello\n"
     ]
    },
    {
     "ename": "IndexError",
     "evalue": "pop from empty list",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-6-d58be5ce9342>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 6\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ms\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-3-2e1e1c52007e>\u001b[0m in \u001b[0;36mpop\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m      \u001b[0;32mdef\u001b[0m \u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m          \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mitems\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m      \u001b[0;32mdef\u001b[0m \u001b[0mpeek\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mIndexError\u001b[0m: pop from empty list"
     ]
    }
   ],
   "source": [
    "s = Stack()\n",
    "s.push('hello')\n",
    "s.push('true')\n",
    "print(s.pop())\n",
    "print(s.pop())\n",
    "print(s.pop())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a href=\"http://codereview.stackexchange.com/questions/82802/stack-implementation-in-python\">Реализация</a> стека, найденная на Code Review."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Очередь"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Очередь** - это упорядоченная коллекция элементов, в которой добавление новых происходит с одного конца, называемого “хвост очереди”, а удаление существующих - с другого, “головы очереди”. Как только элемент добавляется в конец очереди, он начинает свой путь к её началу, ожидая удаления предыдущих."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Самые последние из добавленных в очередь единиц должны ждать в конце коллекции. Элемент, который пробыл в очереди дольше всего, находится в её начале. Такой принцип упорядочения иногда называют **FIFO**, first-in first-out (англ. “первым пришёл - первым вышел”). Ещё он известен, как “первым пришёл - первым обслужен”\n",
    "\n",
    "https://docs.python.org/2/library/queue.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Операции с очередью"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "1. **Queue()** создаёт новую пустую очередь. Не нуждается в параметрах, возвращает пустую очередь.\n",
    "2. **enqueue(item)** добавляет новый элемент в конец очереди. Требует элемент в качестве параметра, ничего не возвращает.\n",
    "3. **dequeue()** удаляет из очереди передний элемент. Не нуждается в параметрах, возвращает элемент. Очередь изменяется.\n",
    "4. **isEmpty()** проверяет очередь на пустоту. Не нуждается в параметрах, возвращает булево значение.\n",
    "5. **size()** возвращает количество элементов в очереди (целое число). Не нуждается в параметрах."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "\n",
    "    def enqueue(self, item):\n",
    "        self.items.insert(0,item)\n",
    "\n",
    "    def dequeue(self):\n",
    "        return self.items.pop()\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Симуляция: Hot Potato"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Одно из типичных приложений для демонстрации очереди в действии - это симуляция реальной ситуации, которая требует управления данными в манере **FIFO**. Для начала давайте рассмотрим детскую игру Hot Potato. В этой игре (см. рисунок) дети выстраиваются в круг и перебрасывают предмет от соседа к соседу так быстро, как только могут. В некоторый момент игры действие останавливается, и ребёнок, у которого в руках остался предмет (картошка), выбывает из круга. Игра продолжается до тех пор, пока не останется единственный победитель."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../img/hotpotato.png\" align=\"center\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для симуляции круга мы будем использовать очередь"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src='../img/namequeue.png'>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Brad', 'Kent', 'Jane', 'Susan', 'David', 'Bill']\n",
      "['Kent']\n",
      "Kent\n"
     ]
    }
   ],
   "source": [
    "def hotPotato(namelist, num):\n",
    "    simqueue = Queue()\n",
    "    for name in namelist:\n",
    "        simqueue.enqueue(name)\n",
    "    \n",
    "    print(simqueue.items)\n",
    "    while simqueue.size() > 1:\n",
    "        for i in range(num):\n",
    "            simqueue.enqueue(simqueue.dequeue())\n",
    "    \n",
    "        simqueue.dequeue()\n",
    "    print(simqueue.items)\n",
    "    return simqueue.dequeue()\n",
    "\n",
    "print(hotPotato([\"Bill\",\"David\",\"Susan\",\"Jane\",\"Kent\",\"Brad\"],1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a href=\"http://john16blog.blogspot.ru/2012/05/python-queue.html\">Перевод</a> примера использования очереди из документации библиотеки queuelib."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример использования queue - симуляция подтверждения регистрации пользователей на каком-либо ресурсе"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Alex\n",
      "User Alex registered\n",
      "Bob\n",
      "User Bob registered\n",
      "Leo\n",
      "User Leo registered\n",
      "Kate\n",
      "User Kate registered\n",
      "quit\n",
      "Confirming users (FIFO)\n",
      "User Alex confirmed\n",
      "User Bob confirmed\n",
      "User Leo confirmed\n",
      "User Kate confirmed\n"
     ]
    }
   ],
   "source": [
    "from queue import Queue\n",
    "\n",
    "unconfirmed_users_queue = Queue()\n",
    "\n",
    "def user_registration(user):\n",
    "    global unconfirmed_users_queue\n",
    "    unconfirmed_users_queue.put(user)\n",
    "    print(\"User {0} registered\".format(user))\n",
    "    \n",
    "def confirm_users():\n",
    "    print(\"Confirming users (FIFO)\")\n",
    "    global unconfirmed_users_queue\n",
    "    while not unconfirmed_users_queue.empty():\n",
    "        user = unconfirmed_users_queue.get()\n",
    "        print(\"User {0} confirmed\".format(user))\n",
    "\n",
    "def register_several_users(): \n",
    "    user=''\n",
    "\n",
    "    while True:\n",
    "        user = input()\n",
    "        if user == \"quit\":\n",
    "            break\n",
    "        else:\n",
    "            user_registration(user)\n",
    "\n",
    "register_several_users()\n",
    "confirm_users()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Деревья"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Основные понятия"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Узел** - это основная часть дерева. Он может иметь название, которое мы будем называть “ключом”. Также узел может содержать дополнительную информацию, которую мы будем называть “полезной нагрузкой”. Хотя во многих алгоритмах для деревьев ей не уделяется достаточно внимания, для приложений, использующих эту структуру данных, она часто оказывается критичным фактором"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ветвь** - другая фундаментальная часть дерева. Она соединяет два узла вместе, показывая наличие между ними определённых отношений. Каждый узел (кроме корня) имеет ровно одну входящую ветвь. При этом он может иметь несколько исходящих ветвей."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Корень дерева** - единственный узел, не имеющий входящих ветвей \n",
    "\n",
    "**Путь** - это упорядоченный список узлов, соединённых ветвями.\n",
    "\n",
    "**Высота** - дерева равна максимальному уровню любого его узла.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Определение 1**: Дерево состоит из набора узлов и набора ветвей, соединяющих пары узлов. Оно имеет следующие свойства:\n",
    "\n",
    "* Один из узлов дерева определён, как его корень.\n",
    "* Каждый узел n (кроме корневого) соединяется ветвью с единственным другим узлом p, где p - родитель n.\n",
    "* Каждый узел соединён с корнем единственно возможным путём.\n",
    "* Если каждый из узлов дерева имеет максимум двух потомков, то такая структура называется двоичным деревом."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../img/treedef1.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Определение 2**: Дерево либо пусто, либо содержит корень и нуль или более поддеревьев, каждое из которых тоже является деревом. Корень каждого поддерева соединён ветвью с родительским деревом."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../img/treedef2.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Изображённая на рисунке выше структура имеет как минимум четыре узла, поскольку каждый из треугольников, представляющих поддеревья, должен иметь корень. В этом дереве может быть намного больше узлов, но сказать точнее нельзя до тех пор, пока мы не продвинемся по нему глубже.\n",
    "\n",
    "http://www.laurentluce.com/posts/binary-search-tree-library-in-python/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Реализация с использованием списков"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В дереве, представленном как список списков, на первой позиции мы будем хранить значение корневого узла. Второй элемент сам по себе будет списком и представит левое поддерево. Третий элемент станет правым поддеревом. Чтобы проиллюстрировать такую технику хранения, рассмотрим пример"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src='../img/smalltree.png'>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "myTree = ['a',   #root\n",
    "      ['b',  #left subtree\n",
    "       ['d' [], []],\n",
    "       ['e' [], []] ],\n",
    "      ['c',  #right subtree\n",
    "       ['f' [], []],\n",
    "       [] ]\n",
    "     ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Обратите внимание, что у нас есть доступ к каждому из поддеревьев с использованием стандартной списковой индексации. Корень дерева - myTree[0], левое поддерево - myTree[1], правое - myTree[2]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', ['b', ['d', [], []], ['e', [], []]], ['c', ['f', [], []], []]]\n",
      "left subtree =  ['b', ['d', [], []], ['e', [], []]]\n",
      "root =  a\n",
      "right subtree =  ['c', ['f', [], []], []]\n",
      "e\n"
     ]
    }
   ],
   "source": [
    "myTree = ['a', ['b', ['d',[],[]], ['e',[],[]] ], ['c', ['f',[],[]], []] ]\n",
    "print(myTree)\n",
    "print('left subtree = ', myTree[1])\n",
    "print('root = ', myTree[0])\n",
    "print('right subtree = ', myTree[2])\n",
    "print(myTree[1][2][0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Давайте формализуем это определение с помощью некоторых функций, которые сделают проще использование списков в качестве деревьев. Обратите внимание, мы не собираемся определять новый класс для двоичного дерева. Функции, которые будут написаны, всего лишь помогут манипулировать стандарным списком, с которым мы работаем, как с деревом."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, [4, [], []], []]\n",
      "[3, [9, [4, [], []], []], [7, [], [6, [], []]]]\n",
      "[3, [9, [11, [4, [], []], []], []], [7, [], [6, [], []]]]\n",
      "[6, [], []]\n"
     ]
    }
   ],
   "source": [
    "def BinaryTree(r):\n",
    "    return [r, [], []]\n",
    "\n",
    "def insertLeft(root, newBranch):\n",
    "    t = root.pop(1)\n",
    "    if len(t) > 1:\n",
    "        root.insert(1,[newBranch,t,[]])\n",
    "    else:\n",
    "        root.insert(1,[newBranch, [], []])\n",
    "    return root\n",
    "\n",
    "def insertRight(root, newBranch):\n",
    "    t = root.pop(2)\n",
    "    if len(t) > 1:\n",
    "        root.insert(2,[newBranch,[],t])\n",
    "    else:\n",
    "        root.insert(2,[newBranch,[],[]])\n",
    "    return root\n",
    "\n",
    "def getRootVal(root):\n",
    "    return root[0]\n",
    "\n",
    "def setRootVal(root,newVal):\n",
    "    root[0] = newVal\n",
    "\n",
    "def getLeftChild(root):\n",
    "    return root[1]\n",
    "\n",
    "def getRightChild(root):\n",
    "    return root[2]\n",
    "\n",
    "r = BinaryTree(3)\n",
    "insertLeft(r,4)\n",
    "insertLeft(r,5)\n",
    "insertRight(r,6)\n",
    "insertRight(r,7)\n",
    "l = getLeftChild(r)\n",
    "print(l)\n",
    "\n",
    "setRootVal(l,9)\n",
    "print(r)\n",
    "insertLeft(l,11)\n",
    "print(r)\n",
    "print(getRightChild(getRightChild(r)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Реализация с помощью ссылок и узлов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Наш второй способ представления деревьев будет использовать узлы и ссылки. Для этого случая мы определим класс, чьими атрибутами станут корневое значение и левое и правое поддеревья. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Начнём с простого определения класса для варианта с узлами и ссылками. Важно помнить, что в этом представлении атрибуты left и right являются ссылками на другие сущности класса BinaryTree. Например, когда мы вставляем нового левого потомка в дерево, мы создаём другой объект BinaryTree и изменяем self.leftChild корня, чтобы этот атрибут ссылался на новое дерево."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class BinaryTree:\n",
    "    def __init__(self, rootObj):\n",
    "        self.key = rootObj\n",
    "        self.leftChild = None\n",
    "        self.rightChild = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Далее давайте рассмотрим функцию, которую требуется написать для строительства дерева за пределы корневого значения. Чтобы добавить левого потомка в дерево, мы создадим новый объект двоичного дерева и поместим в его атрибут корня **left** ссылку на новый объект."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def insertLeft(self, newNode):\n",
    "    if self.leftChild == None:\n",
    "        self.leftChild = BinaryTree(newNode)\n",
    "    else:\n",
    "        t = BinaryTree(newNode)\n",
    "        t.leftChild = self.leftChild\n",
    "        self.leftChild = t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Нам необходимо рассмотреть два случая вставки. Первый - для узла, у которого нет левого потомка. В этом варианте узел просто вставляется в дерево. Второй вариант характеризуется узлом, имеющим левого потомка. Тогда нам надо вставить новый узел и спустить имеющегося потомка на один уровень ниже."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Код для **insertRight** должен содержать симметричный набор случаев. Здесь также может либо отсутствовать правый потомок, либо существовать необходимость вставить узел между корнем и имеющимся правым потомком"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def insertRight(self,newNode):\n",
    "    if self.rightChild == None:\n",
    "        self.rightChild = BinaryTree(newNode)\n",
    "    else:\n",
    "        t = BinaryTree(newNode)\n",
    "        t.rightChild = self.rightChild\n",
    "        self.rightChild = t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Завершая наше определение простого двоичного дерева, напишем методы доступа к корню, правому и левому потомкам"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def getRightChild(self):\n",
    "    return self.rightChild\n",
    "\n",
    "def getLeftChild(self):\n",
    "    return self.leftChild\n",
    "\n",
    "def setRootVal(self,obj):\n",
    "    self.key = obj\n",
    "\n",
    "def getRootVal(self):\n",
    "    return self.key"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Подводя итог проделанной работы:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a\n",
      "None\n",
      "<__main__.BinaryTree object at 0x1050deb70>\n",
      "b\n",
      "<__main__.BinaryTree object at 0x1050fe048>\n",
      "c\n",
      "hello\n"
     ]
    }
   ],
   "source": [
    "class BinaryTree:\n",
    "    def __init__(self,rootObj):\n",
    "        self.key = rootObj\n",
    "        self.leftChild = None\n",
    "        self.rightChild = None\n",
    "\n",
    "    def insertLeft(self,newNode):\n",
    "        if self.leftChild == None:\n",
    "            self.leftChild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.leftChild = self.leftChild\n",
    "            self.leftChild = t\n",
    "\n",
    "    def insertRight(self,newNode):\n",
    "        if self.rightChild == None:\n",
    "            self.rightChild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.rightChild = self.rightChild\n",
    "            self.rightChild = t\n",
    "\n",
    "\n",
    "    def getRightChild(self):\n",
    "        return self.rightChild\n",
    "\n",
    "    def getLeftChild(self):\n",
    "        return self.leftChild\n",
    "\n",
    "    def setRootVal(self,obj):\n",
    "        self.key = obj\n",
    "\n",
    "    def getRootVal(self):\n",
    "        return self.key\n",
    "    \n",
    "#     def __str__(self):\n",
    "#         if self.getRootVal():\n",
    "#             print(self.getRootVal())\n",
    "\n",
    "\n",
    "r = BinaryTree('a')\n",
    "print(r.getRootVal())\n",
    "print(r.getLeftChild())\n",
    "r.insertLeft('b')\n",
    "print(r.getLeftChild())\n",
    "print(r.getLeftChild().getRootVal())\n",
    "r.insertRight('c')\n",
    "print(r.getRightChild())\n",
    "print(r.getRightChild().getRootVal())\n",
    "r.getRightChild().setRootVal('hello')\n",
    "print(r.getRightChild().getRootVal())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Куча"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Куча** — двоичное дерево. А это значит, что каждый родительский элемент имеет два дочерних. И хотя мы называем эту структуру данных кучей, но выражается она через обычный массив. \n",
    "Высота кучи - примерно целая часть log(n), где n — количество элементов.\n",
    "\n",
    "https://docs.python.org/2/library/heapq.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "На рисунке представлена куча типа max-heap, основанная на следующем правиле: дочерние элементы меньше родительского. Существуют также кучи min-heap, где дочерние элементы всегда больше родительского. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src = \"../img/heap1.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Несколько простых функций для работы с кучами:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "global heap\n",
    "global currSize\n",
    "\n",
    "def parent(i): #Получить индекс родителя для i-того элемента\n",
    "    return i/2\n",
    "\n",
    "def left(i): #Получить левый дочерний элемент от i-того\n",
    "    return 2*i\n",
    "\n",
    "def right(i): #Получить правый дочерний элемент от i-того\n",
    "    return (2*i + 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Добавление элемента в существующую кучу**\n",
    "\n",
    "\n",
    "Для начала мы добавляем элемент в самый низ кучи, т.е. в конец массива. Затем мы меняем его местами с родительским элементом до тех пор, пока он не встанет на свое место. \n",
    "\n",
    "**Алгоритм**:\n",
    "\n",
    "1. Добавляем элемент в самый низ кучи.\n",
    "2. Сравниваем добавленный элемент с родительским; если порядок верный — останавливаемся.\n",
    "3. Если нет — меняем элементы местами, и возвращаемся к предыдущему пункту."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src = \"../img/heapadd.jpg\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def swap(a, b): # меняем элемент с индексом a на элемент с индексом b\n",
    "    temp = heap[a]\n",
    "    heap[a] = heap[b]\n",
    "    heap[b] = temp\n",
    "\n",
    "def insert(elem):\n",
    "    global currSize\n",
    "    \n",
    "    index = len(heap)\n",
    "    heap.append(elem)\n",
    "    currSize += 1\n",
    "    par = parent(index)\n",
    "    flag = 0\n",
    "    while flag != 1:\n",
    "        if index == 1: #Дошли до корневого элемента\n",
    "            flag = 1\n",
    "        elif heap[par] > elem: #Если индекс корневого элемента больше индекса нашего элемента - наш элемент на своем месте\n",
    "            flag = 1\n",
    "        else: #Меняем местами родительский элемент с нашим\n",
    "            swap(par, index)\n",
    "            index = par\n",
    "            par = parent(index)\n",
    "            \n",
    "    print(heap)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Максимальное количество проходов цикла *while* равно высоте дерева, или *log(n)*, следовательно, трудоемкость алгоритма — **O(log(n))**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Извлечение максимального элемента кучи**\n",
    "\n",
    "\n",
    "Первый элемент в куче — всегда максимальный, так что мы просто удалим его (предварительно запомнив), и заменим самым нижним. Затем мы приведем кучу в правильный порядок, используя функцию: maxHeapify()\n",
    "\n",
    "**Алгоритм**:\n",
    "1. Заменить корневой элемент самым нижним.\n",
    "2. Сравнить новый корневой элемент с дочерними. Если они в правильном порядке — остановиться.\n",
    "3. Если нет — заменить корневой элемент на одного из дочерних (меньший для min-heap, больший для max-heap), и повторить шаг 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def extractMax():\n",
    "    global currSize\n",
    "    if currSize != 0:\n",
    "        maxElem = heap[1]\n",
    "        heap[1] = heap[currSize] # Заменяем корневой элемент - последним\n",
    "        heap.pop(currSize) # Удаляем последний элемент\n",
    "        currSize -= 1 # Уменьшаем размер кучи\n",
    "        maxHeapify(1)\n",
    "        return maxElem\n",
    "\n",
    "def maxHeapify(index):\n",
    "    global currSize\n",
    "    \n",
    "    lar = index\n",
    "    l = left(index)\n",
    "    r = right(index)\n",
    "\n",
    "    # Вычисляем, какой из дочерних элементов больше; если он больше родительского - меняем местами\n",
    "    if l <= currSize and heap[l] > heap[lar]:\n",
    "        lar = l\n",
    "    if r <= currSize and heap[r] > heap[lar]:\n",
    "        lar = r\n",
    "    if lar != index:\n",
    "        swap(index, lar)\n",
    "        maxHeapify(lar)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "И вновь максимальное количество вызовов функции *maxHeapify* равно высоте дерева, или *log(n)*, а значит, трудоемкость алгоритма — **O(logn)**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Делаем кучу из любого рандомного массива**\n",
    "\n",
    "\n",
    "Есть два пути сделать это. Первый — поочередно вставлять каждый элемент в кучу. Это просто, но совершенно неэффективно. Трудоемкость алгоритма в этом случае будет **O(nlogn)**, т.к. функция **O(logn)** будет выполняться n раз.\n",
    "\n",
    "Более эффективный способ — применить функцию **maxHeapify** для *под-кучи*, от **(currSize/2)** до первого элемента.\n",
    "\n",
    "Сложность получится **O(n)**, и доказательство этого утверждения, к сожалению, выходит за рамки данного курса. Интуиция: элементы, находящиеся в части кучи от **currSize/2** до **currSize**, не имеют потомков, и большинство образованных таким образом *под-куч* будут высотой меньше, чем **log(n)**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def buildHeap():\n",
    "    global currSize\n",
    "    for i in range(currSize/2, 0, -1): #третий агрумент в range() - шаг перебора, в данном случае определяет направление.\n",
    "        print heap\n",
    "        maxHeapify(i)\n",
    "    currSize = len(heap)-1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Графы"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вершина**\n",
    "\n",
    "*Вершина* (иногда её называют “узел”) - основная часть графа. Может иметь имя, которое называется “ключ”. Также вершина может обладать дополнительной информацией, которую мы будем называть “полезной нагрузкой”.\n",
    "\n",
    "**Ребро**\n",
    "\n",
    "*Ребро* (или “дуга”) - другая фундаментальная часть графа. Ребро, соединяющее две вершины, показывает наличие между ними определённых отношений. Рёбра могут быть одно- и двунаправленными. \n",
    "\n",
    "Если все рёбра графа однонаправленные, то мы называем его направленным графом или диграфом (от англ. directed graph - прим. переводчика). Показанный выше граф необходимых для профилирования предметов - явный диграф, поскольку вы обязаны проходить одни курсы прежде, чем другие.\n",
    "\n",
    "**Вес**\n",
    "\n",
    "Рёбра могут иметь вес, показывающий стоимость перемещения от одной вершины к другой. Например, в графе дорог, связывающих города, вес ребра может отображать расстояние между двумя населёнными пунктами.\n",
    "Имея на руках все эти формулировки, мы способны дать формальное определение графа. Он может быть представлен как **G**, где **G=(V,E)**. Здесь **V** - множество вершин графа, а **E** - множество соединяющих их рёбер. Каждое ребро представляет собой кортеж **(v,w)**, где **w**,**v∈V**. Сюда можно добавлять третий компонент, отображающий вес ребра. Подграф **s** - это набор рёбер e и вершин v таких, что **e⊂E** и **v⊂V**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src = \"../img/digraph.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Путь**\n",
    "\n",
    "Путь в графе - это последовательность вершин, соединённых рёбрами. Формально путь можно определить, как $w_{1},w_{2},...,w_{n}$ такой, что $(w_{i},w_{i+1})$∈E для всех 1 ≤ i ≤n−1.\n",
    "\n",
    "Длиной пути без весов станет количество в нём рёбер: n−1. Взвешенный путь в графе будет суммой весов всех входящих в него рёбер. Например, на рисунке 2 путём из $V_{3}$ в $V_{1}$ является последовательность вершин $(V_{3},V_{4},V_{0},V_{1})$. Рёбрами - ${(v_{3},v_{4},7),(v_{4},v_{0},1),(v_{0},v_{1},5)}.$\n",
    "\n",
    "**Цикл**\n",
    "\n",
    "Цикл в направленном графе начинается и заканчивается в одной и той же вершине. Например, на рисунке 2 циклом будет путь $(V_{5},V_{2},V_{3},V_{5})$. Граф без циклов называется ацикличным. Направленный граф без циклов - это *ациклический направленный граф* или **DAG** (от англ. *directed acyclic graph* - прим. автора). Мы увидим, что с его помощью можно решить некоторые важные задачи.\n",
    "\n",
    "http://www.python-course.eu/graphs_python.php\n",
    "\n",
    "https://networkx.github.io/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Операции с графами\n",
    "\n",
    "* **Graph()** создаёт новый пустой граф.\n",
    "* **addVertex(vert)** добавляет в граф объект типа Vertex.\n",
    "* **addEdge(fromVert, toVert)** Добавляет в граф новое направленное ребро, соединяющее две вершины.\n",
    "* **addEdge(fromVert, toVert, weight)** Добавляет в граф новое взвешенное направленное ребро, соединяющее две вершины.\n",
    "* **getVertex(vertKey)** находит в графе вершину vertKey.\n",
    "* **getVertices()** возвращает список всех вершин графа.\n",
    "* **in** возвращает True для оператора формы vertex in graph, если данная вершина в графе имеется, и False в противном случае."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Представление графа\n",
    "\n",
    "1. **Матрица смежности**\n",
    "\n",
    "Одним из простейших способов реализовать граф является использование двумерной матрицы. В ней каждая строка и столбец представляют собой вершину графа, а хранимое в ячейке на пересечении строки **v** и столбца **w** значение показывает, что существует ребро из вершины **v** к вершине **w**. Когда две вершины соединены, мы говорим, что они смежные\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src = \"../img/adjMat.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. **Список смежности**\n",
    "\n",
    "Более пространственно-экономичным способом реализации разреженного графа является использование списка смежности. В таком представлении мы храним основной список из всех вершин объекта **Graph**, каждый из элементов которого поддерживает перечень из связанных с ним вершин. В нашей реализации класса **Vertex** в качестве последнего будет использоваться словарь, где ключами станут вершины, а значениями - веса."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src = \"../img/adjlist.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Преимуществом такой реализации является то, что она позволяет нам компактно представлять разреженные графы. Также в списке смежности легко найти все ссылки, непосредственно связанные с конкретной вершиной."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Реализация"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **Graph** - содержит основной список вершин.\n",
    "2. **Vertex** - представление в графе."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Объекты **Vertex** будут использовать словарь для отслеживания смежных вершин и весов рёбер. Называться он будет *connectedTo*. Листинг ниже показывает код для класса **Vertex**. Конструктор просто инициализирует *id* (обычную строку) и словарь *connectedTo*. Метод *addNeighbor* используется для добавления связи данной вершины с другой. Метод *getConnections* возвращает все вершины из списка смежности, которые представлены в connectedTo. Метод *getWeight* возвращает вес ребра из этой вершины к передаваемой ему в качестве параметра."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Vertex:\n",
    "    def __init__(self,key):\n",
    "        self.id = key\n",
    "        self.connectedTo = {}\n",
    "\n",
    "    def addNeighbor(self,nbr,weight=0):\n",
    "        self.connectedTo[nbr] = weight\n",
    "\n",
    "    def __str__(self):\n",
    "        return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])\n",
    "\n",
    "    def getConnections(self):\n",
    "        return self.connectedTo.keys()\n",
    "\n",
    "    def getId(self):\n",
    "        return self.id\n",
    "\n",
    "    def getWeight(self,nbr):\n",
    "        return self.connectedTo[nbr]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Класс **Graph**, показанный в следующем листинге, содержит словарь, отображающий имена вершин на их объекты. Также **Graph** предоставляет методы для добавления вершин в граф и связывания их друг с другом. Дополнительно мы имеем реализацию метода __iter__, облегчающего итерации по объектам **Vertex** в конкретном графе. Вместе два метода позволяют делать итерации по именам вершин или непосредственно по объектам."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Graph:\n",
    "    def __init__(self):\n",
    "        self.vertList = {}\n",
    "        self.numVertices = 0\n",
    "\n",
    "    def addVertex(self,key):\n",
    "        self.numVertices = self.numVertices + 1\n",
    "        newVertex = Vertex(key)\n",
    "        self.vertList[key] = newVertex\n",
    "        return newVertex\n",
    "\n",
    "    def getVertex(self,n):\n",
    "        if n in self.vertList:\n",
    "            return self.vertList[n]\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    def __contains__(self,n):\n",
    "        return n in self.vertList\n",
    "\n",
    "    def addEdge(self,f,t,cost=0):\n",
    "        if f not in self.vertList:\n",
    "            nv = self.addVertex(f)\n",
    "        if t not in self.vertList:\n",
    "            nv = self.addVertex(t)\n",
    "        self.vertList[f].addNeighbor(self.vertList[t], cost)\n",
    "\n",
    "    def getVertices(self):\n",
    "        return self.vertList.keys()\n",
    "\n",
    "    def __iter__(self):\n",
    "        return iter(self.vertList.values())"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}