heaps/heaps.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 🤖 Робот в лабиринте: обрабатываем очереди с приоритетом в Python с помощью модуля heapq\n",
    "\n",
    "Данный блокнот Jupyter является переводом и адаптацией публикации одного из разработчиков Twisted [Моше Задка](https://github.com/moshez) [The Python heapq Module: Using Heaps and Priority Queues](https://realpython.com/python-heapq-module/). Перевод подготовлен для [Библиотеки программиста](https://proglib.io/).\n",
    "\n",
    "[Кучи](https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D1%87%D0%B0_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)) и [очереди с приоритетом](https://ru.wikipedia.org/wiki/%D0%9E%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C_%D1%81_%D0%BF%D1%80%D0%B8%D0%BE%D1%80%D0%B8%D1%82%D0%B5%D1%82%D0%BE%D0%BC_(%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5)) – не самые популярные, но удивительно полезные структуры данных. Для многих проблем, связанных с поиском лучшего элемента в наборе данных, они предлагают простое в использовании высокоэффективное решение. Например, очередь с приоритетом – это мощный инструмент, помогающий решать такие задачи, как создание планировщика заданий, поиск кратчайшего пути или объединение логов. Реализующий соответствующие структуры данных модуль Python `heapq` является частью стандартной библиотеки.\n",
    "\n",
    "Из этого туториала вы узнаете:\n",
    "* Что такое кучи и очереди с приоритетом и как они связаны.\n",
    "* Какие виды задач можно решить с помощью очереди с приоритетом.\n",
    "* Как использовать модуль heapq.\n",
    "\n",
    "Кому будет полезен материал: питонистам, уже хорошо знакомым со стандартными структурами данных и готовых познакомиться с более специализированными решениями."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Что такое кучи?\n",
    "\n",
    "Очереди с приоритетом относятся к [асбтрактным типам данных](https://ru.wikipedia.org/wiki/%D0%90%D0%B1%D1%81%D1%82%D1%80%D0%B0%D0%BA%D1%82%D0%BD%D1%8B%D0%B9_%D1%82%D0%B8%D0%BF_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85), а кучи – к конкретным.\n",
    "Абстрактная структура данных определяет интерфейс, а конкретная структура данных – реализацию.\n",
    "\n",
    "Конкретные структуры данных также определяют производительность, взаимосвязь между размером структуры и временем выполнения операций. Понимание этих гарантий позволяет предсказать, сколько времени займет программа при изменении размера входных данных.\n",
    "\n",
    "Абстрактные структуры данных определяют операции и отношения между ними. Например, очередь с приоритетами поддерживает три операции:\n",
    "* `is_empty` проверяет, пуста ли очередь;\n",
    "* `add_element` добавляет  в очередь элемент;\n",
    "* `pop_element` выталкивает элемент с наивысшим приоритетом.\n",
    "\n",
    "После завершения задачи ее приоритет понижается и она возвращается в очередь. Приоритет очереди определяется соглашением. Самый высокий приоритет может иметь, к примеру, наибольший или наименьший элемент. Модуль Python `heapq` использует наиболее распространенное соглашение, согласно которому самый маленький элемент имеет самый высокий приоритет. Может звучать удивительно, но в реальных примерах, которые вы увидите позже, это соглашение существенно упрощает код.\n",
    "\n",
    "___\n",
    "\n",
    "**Примечание**. Модуль `heapq` и структура данных кучи не предназначены для обычного поиска элементов. В таком деле больше пригодится [двоичное дерево поиска](https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0). Соответствующие инструменты описаны в публикации Бартоша Зачински [Как сделать бинарный поиск на Python](https://realpython.com/binary-search-python/) (англ.).\n",
    "___\n",
    "\n",
    "Реализация кучи гарантирует, что операции добавления и удаления элементов имеют логарифмическую [временную сложность](https://ru.wikipedia.org/wiki/%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0). То есть время, необходимое для выполнения `push` и `pop`, пропорционально логарифму по основанию 2 от числа элементов.\n",
    "\n",
    "Логарифмические функции растут медленно. Двоичный логарифм из десяти составляет 3.3, а из миллиарда 29.9. Это означает, что если алгоритм достаточно быстр для десяти элементов,  он будет лишь в десять раз медленнее для миллиарда элементов.\n",
    "\n",
    "Однако при любом обсуждении производительности абстрактные соображения менее значимы, чем замеры времени выполнения на конкретной программе. Гарантии производительности важны для прогнозирования поведения программы, но должны быть подтверждены.\n",
    "\n",
    "---\n",
    "**Примечание.** О различных библиотеках работы со временем и интервалами времени в Python читайте в нашей публикации [«Назад в будущее: практическое руководство по путешествию во времени с Python»](https://proglib.io/p/nazad-v-budushchee-prakticheskoe-rukovodstvo-po-puteshestviyu-vo-vremeni-s-python-2019-12-01)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Реализация структуры данных\n",
    "\n",
    "Куча реализует очередь с приоритетом в виде полного двоичного дерева. В двоичном дереве каждый узел имеет не более двух дочерних элементов. В полном бинарном дереве все уровни, кроме, возможно, самого глубокого, всегда заполнены. На одном уровне узлы заполняются слева направо. Свойство полноты означает, что глубина дерева – это двоичный логарифм числа элементов, округленный в большую сторону. Пример полного двоичного дерева:\n",
    "\n",
    "![](https://files.realpython.com/media/heap-tree.4b4413ff133c.png)\n",
    "\n",
    "В этом частном примере заполнены все уровни. Каждый узел, кроме самых глубоких (нижних), имеет ровно по два потомка. Всего на трёх уровнях имеется 7 узлов. Единственный узел базового уровня называется `root`. Гарантии производительности в куче зависят от того, как элементы перемещаются вверх и вниз по дереву. Число сравнений в куче является двоичным логарифмом от размера дерева.\n",
    "\n",
    "___\n",
    "**Примечание**. При сравнении объектов обычно вызываются пользовательские методы `.__ lt __ ()`. Вызов пользовательских методов в Python является относительно медленной операцией по сравнению с другими операциями, выполняемыми в куче, так что это узкое место.\n",
    "___\n",
    "\n",
    "В дереве кучи значение, хранящееся в узле всегда меньше, чем у обоих дочерних элементов. Это свойство, называемое *свойство кучи* отличает его от бинарного дерева поиска, где лишь значение левого узла меньше значения его родителя.\n",
    "\n",
    "Алгоритмы вставки и выдачи элементов основаны на временном нарушении свойства кучи и последующем его исправлении путем сравнения и замены вверх или вниз по одной ветви.\n",
    "\n",
    "Чтобы поместить элемент в кучу, Python сначала выбирает, куда его вставить. Если нижний слой заполнен не до конца, узел добавляется в следующий открытый слот. Иначе создается новый уровень и элемент добавляется в него. Как только узел добавлен, Python сравнивает новый узел с его родителем. Если свойство кучи нарушено, узел и родительский объект обмениваются местами. Проверка продолжается до тех пор, пока не будет восстановлено свойство кучи или не будет достигнут корень."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Использование приоритетных очередей\n",
    "\n",
    "Очередь с приоритетом и куча, как реализация такой очереди, полезны для программ, которые включают в себя поиск некоторого экстремального элемента. Очередь с приоритетом может понадобиться для эффективного решения следующих задач:\n",
    "* Получить три самых популярных поста в блоге по данным о посещениях.\n",
    "* Найти скорейший способ добраться из одной точки в другую.\n",
    "* Спрогнозировать на основе частоты прибытия автобусов, какой из них прибудет первым.\n",
    "\n",
    "Другой пример, на котором мы остановимся подробнее, – планирование отправки электронных писем. Представьте себе систему, работающую с несколькими видами электронных писем. Каждый вид необходимо отправлять с определенной частотой: один вид сообщений должен отправляться каждые 15 мин., другой — каждые 40 мин. \n",
    "\n",
    "Планировщик добавляет оба типа писем в очередь с отметкой времени, указывающей, когда электронное письмо нужно отправить в следующий раз. Затем планировщик смотрит на элемент с ближайшей временной меткой и вычисляет, сколько времени нужно подождать перед отправкой.\n",
    "\n",
    "По завершении ожидания планировщик отправляет соответствующее послание и берет следующее письмо из приоритетной очереди, вычисляет время до его отправки. Предыдущее письмо планировщик помещает обратно в очередь, как новый элемент."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Кучи в виде списков в модуле heapq\n",
    "\n",
    "Напомним, что куча представляет собой полное двоичное дерево. Полнота означает, что на каждом слое (кроме последнего) известно число элементов. За счет этого кучи легко реализовать с помощью списков Python, что и сделано в модуле heapq.\n",
    "\n",
    "Связи между элементом с индексом `k` и окружающими его элементами описывают три правила:\n",
    "\n",
    "1. Первый потомок k-го элемента имеет индекс `2*k + 1`.\n",
    "2. Второй потомок k-го элемента имеет индекс `2*k + 2`.\n",
    "3. Родитель k-го элемента имеет индекс `(k + 1) // 2`.\n",
    "\n",
    "**Примечание**: символ `//` соответствует операции целочисленного деления.\n",
    "\n",
    "Приведенные правила помогают представить список, как полное двоичное дерево. Также нужно понимать, что у любого элемента есть родительский элемент, но необязательно присутствует дочерний. Если индекс `2*k` находится за пределами списка, то у элемента нет дочерних элементов. Если `2*k` является допустимым индексом, а `2*k+1` – нет, то у элемента есть лишь один потомок.\n",
    "\n",
    "Свойство кучи подразумевает, что если `h` является кучей, то следующее выражение никогда не будет ложным:\n",
    "\n",
    "```python\n",
    "h[k] <= h[2*k + 1] and h[k] <= h[2*k + 2]\n",
    "```\n",
    "\n",
    "Выражение может вызвать исключение `IndexError`, если индекс вышел за пределы списка, но вычисляемое логическое значение никогда не будет `False`.\n",
    "\n",
    "То есть в терминах списков: k-й элемент всегда меньше, чем каждый из пары элементов, стоящих вслед за 2k-м элементом.\n",
    "\n",
    "Пример списка, удовлетворяющего свойству кучи:\n",
    "\n",
    "![](https://files.realpython.com/media/heap-list.2db422e53ead.png)\n",
    "\n",
    "Стрелки проведены от элемента с индексом `k` к элементам с индексами `2 * k + 1` и `2 * k + 2`. Например, первый элемент в списке Python имеет индекс 0, поэтому две стрелки указывают на индексы 1 и 2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Базовые операции\n",
    "\n",
    "В отличие от многих других модулей Python,  `heapq` не определяет пользовательский класс, а работает со списками напрямую. \n",
    "\n",
    "Обычно, как в приведенном примере электронной почты, элементы вставляются в кучу один за другим, начиная с пустой кучи. Однако, если уже есть список элементов, их можно преобразовать с помощью функции `heapify()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 5, 6, 8, 7]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import heapq\n",
    "a = [3, 5, 1, 2, 6, 8, 7]\n",
    "heapq.heapify(a)\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Хотя 7 идет после 8, легко проверить, что список подчиняется свойству кучи. Например, значение `a[2]`, равное 3, меньше значения `a[2*2 + 2]`, равного 7.\n",
    "\n",
    "`heapify()` изменяет список на месте, но не сортирует его. Чтобы удовлетворять необходимому свойству куча не должна быть отсортирована. В то же время любой отсортированный список удовлетворяет свойству кучи и запуск `heapify()` на отсортированном списке не изменит порядок элементов.\n",
    "\n",
    "Другие основные операции в модуле Python `heapq` предполагают, что список уже является кучей. Полезно отметить, что кучей всегда являются пустой список или список единичной длины.\n",
    "\n",
    "Поскольку корень дерева является первым элементом, нам не требуется специальной функции для чтения наименьшего элемента – достаточно извлечь его по индексу `a[0]`. Чтобы вытолкнуть наименьший элемент при сохранении свойства кучи, используется функция `heappop()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 [2, 5, 3, 7, 6, 8]\n"
     ]
    }
   ],
   "source": [
    "root = heapq.heappop(a)\n",
    "print(root, a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Функция возвращает первый элемент, 1. Сама куча изменяется, но сохраняется свойство кучи: например, `a[1]` равно 5, `а[1*2 + 2]` равно 6.\n",
    "\n",
    "Модуль Python `heapq` также включает в себя `heappush()` для помещения элемента в кучу при сохранении свойства кучи."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 5, 3, 7, 6, 8, 4]\n"
     ]
    }
   ],
   "source": [
    "heapq.heappush(a, 4)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Мы добавили в кучу 4, но затем вытолкнули из нее три элемента. Как можно видеть, всегда выталкивается наименьший элемент.\n",
    "\n",
    "Модуль Python `heapq` определяет еще две операции:\n",
    "* `heapreplace()` эквивалентно `heappop()` с последующим `heappush()`. \n",
    "* `heappushpop()` эквивалентно `heappush()` c последующим `heappop()`.\n",
    "\n",
    "Эта пара методов эффективнее, чем входящие в них функции, запущенные по отдельности."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Высокоуровневые операции\n",
    "\n",
    "Поскольку очереди с приоритетом часто используются для объединения отсортированных последовательностей, модуль `heapq` имеет готовую функцию `merge()` для объединения нескольких очередей. Функция `merge()` предполагает, что входные итерируемые объекты уже упорядочены, и возвращает итератор, а не список.\n",
    "\n",
    "В качестве примера использования `merge()` рассмотрим реализацию планировщика электронной почты:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import datetime\n",
    "\n",
    "def email(frequency, details):\n",
    "    current = datetime.datetime.now()\n",
    "    while True:\n",
    "        current += frequency\n",
    "        yield current, details\n",
    "\n",
    "fast_email = email(datetime.timedelta(minutes=15), \"fast email\")\n",
    "slow_email = email(datetime.timedelta(minutes=40), \"slow email\")\n",
    "\n",
    "unified = heapq.merge(fast_email, slow_email)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Входные данные для `merge()` в этом примере являются бесконечными генераторами. Возвращаемое значение, присвоенное переменной `unified` является бесконечным итератором. Этот итератор возвращает электронные письма, которые будут отправлены в порядке будущих временных меток.\n",
    "\n",
    "Для отладки и подтверждения правильности слияния кода выведем на экран десять первых отправленных писем:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(datetime.datetime(2020, 7, 7, 11, 56, 15, 654916), 'fast email')\n",
      "(datetime.datetime(2020, 7, 7, 12, 11, 15, 654916), 'fast email')\n",
      "(datetime.datetime(2020, 7, 7, 12, 21, 15, 654923), 'slow email')\n",
      "(datetime.datetime(2020, 7, 7, 12, 26, 15, 654916), 'fast email')\n",
      "(datetime.datetime(2020, 7, 7, 12, 41, 15, 654916), 'fast email')\n",
      "(datetime.datetime(2020, 7, 7, 12, 56, 15, 654916), 'fast email')\n",
      "(datetime.datetime(2020, 7, 7, 13, 1, 15, 654923), 'slow email')\n",
      "(datetime.datetime(2020, 7, 7, 13, 11, 15, 654916), 'fast email')\n",
      "(datetime.datetime(2020, 7, 7, 13, 26, 15, 654916), 'fast email')\n",
      "(datetime.datetime(2020, 7, 7, 13, 41, 15, 654916), 'fast email')\n"
     ]
    }
   ],
   "source": [
    "for _ in range(10):\n",
    "    print(next(unified))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Обратите внимание, что `fast email` идут каждые 15 минут, а `low email` каждые 40 минут, при этом электронные письма правильно чередуются и идут в порядке их временных меток. При этом функция `merge()` не читает входные данные целиком, а работает динамически.\n",
    "\n",
    "Другой пример – объединение упорядоченных по времени последовательностей строк из разных файлов журналирования. Даже если файлы большие, операция занимает разумное количество времени. Рассмотрим также другие задачи.\n",
    "\n",
    "# Поиск нескольких наименьших (наибольших) элементов кучи\n",
    "\n",
    "Как мы увидели выше, кучи хороши для объединения отсортированных последовательностей. Но они пригодны и для решения других задач. Например, кучи помогают идентифицировать верхние или нижние `n` объектов. Для подобных задач в модуль Python heapq есть функции высокого уровня.\n",
    "\n",
    "Например, этот код получает в качестве входных данных [результаты финального забега на 100 метров среди женщин](https://www.olympic.org/rio-2016/athletics/100m-women) на летних Олимпийских играх 2016 года и печатает список медалисток (трех лучших участниц):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Elaine Thompson          10.71\n",
      "Tori Bowie               10.83\n",
      "Marie-Josee Ta Lou       10.86\n"
     ]
    }
   ],
   "source": [
    "results=\"\"\"\\\n",
    "Christania Williams      11.80\n",
    "Marie-Josee Ta Lou       10.86\n",
    "Elaine Thompson          10.71\n",
    "Tori Bowie               10.83\n",
    "Shelly-Ann Fraser-Pryce  10.86\n",
    "English Gardner          10.94\n",
    "Michelle-Lee Ahye        10.92\n",
    "Dafne Schippers          10.90\n",
    "\"\"\"\n",
    "\n",
    "top_3 = heapq.nsmallest(\n",
    "    3, results.splitlines(), key=lambda x: float(x.split()[-1])\n",
    ")\n",
    "\n",
    "print(\"\\n\".join(top_3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Этот код использует функцию `nsmallest()`, которая возвращает `n` наименьших элементов итерируемого объекта и принимает три аргумента:\n",
    "1. `n` – количество возвращаемых элементов,\n",
    "2. `iterable` – итерируемый набор данных для сравнения,\n",
    "3. `key` – функция, определяющая как должны сравнваться элементы.\n",
    "\n",
    "Здесь на месте `key` мы видим lambda-функцию, которая разбивает строку на пробелы, берет последний элемент и преобразует его в число с плавающей запятой. То есть код «сортирует» строки по времени забега и возвращает три строки с наименьшим временем. Они соответствуют трем самым быстрым бегуньям – золотой, серебряной и бронзовой медалистке.\n",
    "\n",
    "Для поиска самых больших элементов есть аналогичная функция `nlargest()`. Такая функция, например, была бы полезна, если бы мы хотели получить список медалистов на соревнованиях по метанию копья."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Когда использовать heapq\n",
    "\n",
    "Куча является хорошим инструментом для решения задач с поиском экстремумов. Таким образом, проблемы, для которых подходят кучи, обычно содержат следующие слова:\n",
    "* наибольший / наименьший\n",
    "* лучший / худший\n",
    "* верх / низ\n",
    "* максимум / минимум\n",
    "* оптимум\n",
    "\n",
    "Всякий раз, когда формулировка проблемы указывает на то, что вы ищете какой-то экстремальный элемент, может пригодиться очередь с приоритетом. Также кучи более эффективны, если нужно проводить упорядочение на месте, когда в последовательность во время работы с ней могут добавляться новые элементы.\n",
    "\n",
    "Иногда приоритетная очередь является лишь частью решения, а остальная часть лежит в области [динамического программирования](https://proglib.io/p/python-i-dinamicheskoe-programmirovanie-na-primere-zadachi-o-ryukzake-2020-02-04). Это относится к примеру, который мы рассмотрим в следующих разделах."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Практический пример: поиск путей для робота в лабиринте \n",
    "\n",
    "Следующий пример служит реалистичным вариантом использования модуля heapq. В примере будет использован классический алгоритм, важной составляющей которого является использование кучи.\n",
    "\n",
    "Представим себе робота, которому нужно ориентироваться в двумерном лабиринте. Робот должен пройти от стартовой точки в верхнем левом углу к месту назначения в правом нижнем углу. Карта лабиринта хранится в памяти робота – путь можно спланировать заранее. Цель – преодолеть лабиринт как можно быстрее (робот движется с постоянной скоростью, по горизонтали, вертикали и диагонально).\n",
    "\n",
    "Рассматриваемый алгоритм является вариацей [алгоритма Дейкстры](https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B). В алгоритме сохраняются и обновляются три структуры данных:\n",
    "\n",
    "1. `tentative` – карта предварительного пути от начальной точки до конечной позиции. Путь называется *предварительным*, поскольку это самый короткий известный на данный момент путь, его можно улучшить.\n",
    "2. `certain` – множество точек, для которых путь, определяемый картой `tentative` является кратчайшим из возможных.\n",
    "3. `candidates` – куча, составленная позициями-кандидатами, по которым может пройти путь. Ключ сортировки – длина пути.\n",
    "\n",
    "На каждом шаге мы выполняем от двух до четырех действий:\n",
    "1. Выталкиваем позицию-кандидата из кучи `candidates`\n",
    "2. Добавляем кандидата в множество `certain`. Если кандидат уже является частью множества `certain`, пропускаем следующие два действия. \n",
    "3. Находим кратчайший известный путь к текущему кандидату.\n",
    "4. Для каждого из ближайших соседей текущего кандидата рассматриваем, даёт ли проход через кандидата более короткий путь, чем текущий путь `tentative`. Если это так, обновляем путь `tentative` и кучу `candidates` этим новым путем.\n",
    "\n",
    "Перечисленные шаги выполняются в цикле до тех пор, пока в множество `certain` не попадет позиция пункта назначения. Результатом алгоритма является путь, состоящий из точек, перечисленных в `certain`, который теперь точно является кратчайшим из возможных путей."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Робот в лабиринте: вспомогательный код\n",
    "\n",
    "Теперь, когда мы в общих чертах понимаем алгоритм, напишем код для его реализации. Предварительно напишем несколько вспомогательных функций.\n",
    "\n",
    "Определим простую карту:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = \"\"\"\\\n",
    "⚪⚪⚪⚪⚪⚪⚪🌳⚪⚪\n",
    "⚪⚪⚪⚪⚪⚪⚪🌲⚪⚪\n",
    "⚪⚪⚪⚪🌲🌲🌳🌳⚪⚪\n",
    "⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪\n",
    "⚪⚪⚪⚪⚪⚪⚪⚪⚪⚪\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Карта представляет собой строку в тройных кавычках, отображающую область, в которой робот может двигаться, а также препятствия (в сравнении с оригинальной статьей для наглядности мы заменили точки и крестики на эмодзи — прим. пер.).\n",
    "\n",
    "Хотя в более реалистичном сценарии карта считывается из файла, для целей обучения проще определить наглядную переменную в коде. Код будет работать на любой карте, но для отладки воспользуемся простым примером.\n",
    "\n",
    "Определим функцию, которая преобразует карту так, чтобы ее было проще анализировать программно:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse_map(m):\n",
    "    \"\"\"Возвращает построчную карту, позиции начала координат\n",
    "    и позицию места.\"\"\"\n",
    "    lines = m.splitlines()\n",
    "    \n",
    "     # начало координат (точка отправления)\n",
    "    origin = 0, 0 \n",
    "    \n",
    "     # координаты места назначения\n",
    "    destination = len(lines[-1]) - 1, len(lines) - 1 \n",
    "    return lines, origin, destination"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Список `lines` можно индексировать с помощью координат (x, y) – выражение `lines[y][x]` возвращают значение позиции в виде одного из двух символов:\n",
    "\n",
    "* ⚪ – пустая позиция\n",
    "* 🌲 – позиция препятствия\n",
    "\n",
    "Следующая функция определяет, может ли робот занять позицию (x, y) с учетом содержания карты и ее границ:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_valid(lines, position):\n",
    "    \"\"\"Проверяет, не выходит ли координата position за границы карты\n",
    "    и доступна ли  position для перемещения\"\"\"\n",
    "    x, y = position\n",
    "    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):\n",
    "        return False\n",
    "    if lines[y][x] != \"⚪\":\n",
    "        return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Описанную функцию `is_valid()` применим в следующей функции для нахождения соседей текущей позиции:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_neighbors(lines, current):\n",
    "    \"\"\"Возвращает коордианты соседей текущей позиции\"\"\"\n",
    "    x, y = current\n",
    "    for dx in [-1, 0, 1]:\n",
    "        for dy in [-1, 0, 1]:\n",
    "            if dx == 0 and dy == 0:\n",
    "                continue\n",
    "            position = x + dx, y + dy\n",
    "            if is_valid(lines, position):\n",
    "                yield position"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Последняя вспомогательная функция будет использоваться для нахождения пути:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_shorter_paths(tentative, positions, through):\n",
    "    \"\"\"Возвращает позиции, при прохождении через которые\n",
    "    путь короче текущего пути\"\"\"\n",
    "    path = tentative[through] + [through]\n",
    "    for position in positions:\n",
    "        if position in tentative and len(tentative[position]) <= len(path):\n",
    "            continue\n",
    "        yield position, path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "У функции `get_shorter_paths()` три параметра:\n",
    "* `tentative` — словарь, ставящий в соответствие ключу позиции наиболее короткий известный путь\n",
    "* `positions` — итерируемый объект позиций, до которых мы хотим сократить путь\n",
    "* `through` – позиция, при прохождению через которую может быть найден более короткий путь до `positions`\n",
    "\n",
    "Предполагается, что все элементы в `positions` могут быть достигнуты за один шаг.\n",
    "\n",
    "Функция `get_shorter_paths()` проверяет, приведет ли использование позиции `through` в качестве последнего шага текущего пути к лучшему пути для каждой позиции. Если путь к позиции отсутствует, то любой путь считается «более коротким». Если есть известный путь, то новый путь будет возвращен, только если его длина меньше. Чтобы упростить работу с интерфейсом `get_shorter_paths()`, инструкция `yield` включает не только позицию, но и путь.\n",
    "\n",
    "Все вспомогательные функции написаны как [чистые функции](https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D1%82%D0%BE%D1%82%D0%B0_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8), то есть они не изменяют структуры данных, а только возвращают значения. Все обновления структуры данных выполняет основной алгоритм."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Робот в лабиринте: код основного алгоритма\n",
    "\n",
    "Итак, мы ищем кратчайший путь между началом координат и пунктом назначения, и у нас есть три структуры данных:\n",
    "1. `certain` – множество позиций, являющихся частью пути (исходно пустое).\n",
    "2. `candidates` – куча, состоящая из позиций-кандидатов.\n",
    "3. `tentative` – словарь, ставящий в соответствие узлам промежуточные кратчайшие пути.\n",
    "\n",
    "Позиция находится в `certain`, если мы уверены, что самый короткий из известных путей – самый короткий из возможных. Если в `certain` оказался пункт назначения, значит, найден искомый путь.\n",
    "\n",
    "Куча `candidates` упорядочена по длине самого короткого известного пути и управляется с помощью функций модуля heapq.\n",
    "\n",
    "На каждом шаге мы смотрим на позицию-кандидата и кратчайший известный путь. Из кучи `candidates` выталкивается элемент с помощью `heappop()`. До этой позиции-кандидата не существует более короткого пути – все остальные пути проходят через другие узлы, и все они длиннее. Из-за этого текущий кандидат может быть отмечен как `certain`.\n",
    "\n",
    "Затем мы просматриваем всех непосещённых соседей и, если проход через текущую позицию является улучшением, мы добавляем их в кучу `candidates`, используя `heappush()`.\n",
    "\n",
    "Описанный алгоритм реализует функция `find_path()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_path(m):\n",
    "    lines, origin, destination = parse_map(m)\n",
    "    tentative = {origin: []}\n",
    "    candidates = [(0, origin)]\n",
    "    certain = set()\n",
    "    while destination not in certain and len(candidates) > 0:\n",
    "        _ignored, current = heapq.heappop(candidates)\n",
    "        if current in certain:\n",
    "            continue\n",
    "        certain.add(current)\n",
    "        neighbors = set(get_neighbors(lines, current)) - certain\n",
    "        shorter = get_shorter_paths(tentative, neighbors, current)\n",
    "        for neighbor, path in shorter:\n",
    "            tentative[neighbor] = path\n",
    "            heapq.heappush(candidates, (len(path), neighbor))\n",
    "    if destination in tentative:\n",
    "        return tentative[destination] + [destination]\n",
    "    else:\n",
    "        raise ValueError(\"no path\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Функция `find_path()` получает карту в виде строки и возвращает путь от начала координат к пункту назначения в виде списка позиций. Эта функция немного длиннее и сложнее тех, что мы писали раньше – давайте пробежимся построчно:\n",
    "\n",
    "* В первых трех строчках после объявления функции мы объявляем переменные, которые будет просматривать и обновлять цикл `while`. Исходный путь имеет длину 0 – это путь от начала координат в него же. \n",
    "* Далее идйт цикл `while`. Если позиций-кандидатов нет, то и путь сократить нельзя. Если пункт назначения находится в `certain`, путь найден.\n",
    "* Первые четыре строки после объявления цикла получают позицию-кандидата с помощью `heappop()`, пропускают итерацию, если позиция-кандидат уже находится в `certain` или, в противном случае, добавляют её в `certain`. Это гарантирует, что каждая позиция-кандидат обрабатываеся циклом не более одного раза.\n",
    "* Следующие строки цикла ищут более короткие пути к соседним позициям и обновляют словарь  `tentative` и кучу `candidates`, используя `get_neighbors()` и `get_shorter_paths()`.\n",
    "* Условная конструкция после цикла возвращает необходимый результат. Хотя вычисление путей без конечной позиции сделало реализацию алгоритма более простой, в самом интерфейсе логично вернуть путь целиком вместе с пунктом назначения. Если путь не найден, вызываем исключение."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Код для демонстрации алгоритма\n",
    "\n",
    "Итак, роботу уже всё понятно. Но чтобы сделать результат нагляднее для людей, хорошо бы визуализировать алгоритм. Напишем для этого функцию, отображающую путь робота."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "🤖🤖⚪⚪⚪⚪⚪🌳⚪⚪\n",
      "⚪⚪🤖⚪⚪⚪⚪🌲⚪⚪\n",
      "⚪⚪⚪🤖🌲🌲🌳🌳⚪⚪\n",
      "⚪⚪⚪⚪🤖🤖🤖🤖🤖⚪\n",
      "⚪⚪⚪⚪⚪⚪⚪⚪⚪🤖\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def show_path(path, m):\n",
    "    lines = m.splitlines()\n",
    "    for x, y in path:\n",
    "        lines[y] = lines[y][:x] + \"🤖\" + lines[y][x+1:]\n",
    "    return \"\\n\".join(lines) + \"\\n\"\n",
    "\n",
    "path = find_path(m)\n",
    "print(show_path(path, m))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Здесь всё просто: сначала получили кратчайший путь с помощью `find_path()`, затем передали его в `show_path()` для рендеринга карты с отмеченным на ней путём робота. Наконец, вывели карту. Как и ожидалось, робот, успешно преодолел все препятствия.\n",
    "\n",
    "Подобные проблемы с поиском пути, которые можно решить с помощью комбинации динамического программирования и очередей с приоритетами, нередко встречаются на собеседованиях и соревнованиях по программированию. Например, на Advent of Code 2019 года  [соответствующую задачу](https://adventofcode.com/2019/day/18) было можно решить с помощью описанных здесь методов."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Заключение\n",
    "\n",
    "Теперь вы знаете о том, как реализуются структуры данных кучи в модуле Python heapq и для каких задач программирования они полезны. Главное понимать, что эффективность этого инструмента проявляется не в непосредственной сортировке значений, а в поиске экстремальных и приоритетных значений за минимальное время и корректной обработке очередей с приоритетом. Функций в модуле немного, а вся необходимая дополнительная информация и примеры доступны в [документации](https://docs.python.org/3/library/heapq.html)."
   ]
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}