Решаем задачи без самобалансирующихся деревьев в Python
Многие задачи на алгоритмы требуют знания определённых структур данных. Стек, очередь, куча, динамический массив, двоичное дерево поиска — нечасто решение алгоритмической задачи обходится без использования чего-либо из них. Однако, качественная их реализация — нетривиальная задача, и при написании кода всегда хочется по максимуму обойтись использованием стандартной библиотеки языка.
Что касается Python, то в нём есть почти всё.
- Динамический массив — встроенный тип list . Он же поддерживает и стековые операции: .append() и .pop() .
- Хэш-таблица — встроенные типы set и dict , а также неизменяемый брат сета frozenset .
- Куча — list со специальными операциями вставки и удаления, реализованными в модуле heapq .
- Двусторонняя очередь — это описанный в модуле collections тип deque .
В этой статье я разберу несколько алгоритмических задачек, подразумевающих решение с помощью двоичного дерева, и покажу, чем в разных ситуациях его можно заменить в Питоне.
На что способно дерево поиска
Вы наверняка и так знаете, что самобалансирующееся двоичное дерево поиска — удобнейшая структура данных для многих задач, поддерживающая множество операций. Но я на всякий случай перечислю их и напомню их асимптотическую сложность.
- Вставка элемента — стоит
- Удаление элемента — стоит
- Поиск элемента — стоит
- Нахождение минимального и максимального элементов — стоит . При особой необходимости можно помнить указатели на них; тогда потребность в проходе по дереву отпадает и стоимость снижается до
- Нахождение медианы, да и вообще любой k-й порядковой статистики — стоит При этом придётся в каждом узле дерева помнить размер соответствующего поддерева.
- Нахождение количества элементов меньше/больше заданного — стоит Для этого тоже необходимо в каждом узле дерева помнить размер соответствующего поддерева.
- Вставка монотонной последовательности элементов — может стоить амортизированное на каждый! (Знаете ли вы, что в C++ std::set можно наполнить из сортированного массива за ?)
Задача: небоскрёбы
На прямой стоят небоскрёбы, некоторые из которых перекрывают друг друга. Нужно описать очертания на фоне неба всей совокупности небоскрёбов.
Здания описаны как массив кортежей вида (координата левого края здания, координата правого края здания, высота). На выход нужно передать массив кортежей (x, y), описывающих общий силуэт зданий.
Эта задача решается за . Алгоритм в целом примерно такой: сортируем все точки (и левые, и правые края зданий), идём по ним слева направо. Если наткнулись на левый край здания — надо добавить его в перечень активных на данный момент, если на правый — исключить из перечня. В любом случае каждый раз надо проверять, изменилась ли максимальная высота активных зданий, и если изменилась, записывать в ответ очередную точку. (Более подробный разбор этой задачи можно найти здесь.)
Перечень активных зданий, как структура данных, должен поддерживать быстрое добавление нового элемента, удаление произвольного элемента и нахождение максимума. Двоичное дерево умеет делать все три операции за и идеально подходит для этой задачи. Попробуем обойтись без него!
Необходимость быстро брать максимум, конечно, напоминает нам о куче. Но куча не предусматривает удаления произвольного элемента! Например, чтобы удалить элемент кучи с известным индексом в Python за приемлемое время, нужно залезть в нестандартизированные детали реализации модуля heapq (что, конечно, ненадёжно и не рекомендуется):
Однако, есть возможность сделать надстройку над кучей, позволяющую удалять произвольный элемент за амортизированное . Алгоритм такой:
- Храним вместе с кучей множество удалённых элементов.
- Если требуется удалить элемент, не являющийся сейчас минимальным в куче, добавляем его в множество удалённых элементов.
- Если требуется удалить элемент, являющийся сейчас минимальным, удаляем его стандартным heappop . Если новый минимальным элемент содержится в множестве удалённых элементов, удаляем и его, и так далее.
Задача: медиана в скользящем окне
Эта задача встречается в разных вариантах. Наиболее общо с учётом специфики Питона можно сформулировать так: на вход алгоритму подаётся итератор неизвестной (и, возможно, неограниченной) длины. Нужно вернуть итератор с медианами по всем окнам заранее заданной ширины .
При оптимальном решении этой задачи каждая следующая медиана вычисляется за амортизированное . Как и большинстве задач на скользящее окно, решение заключается в построении структуры данных, позволяющей быстро добавлять в окно новый элемент, удалять самый старый и вычислять очередную медиану.
Дерево, очевидно, решает эту задачу. Добавление, удаление и нахождение медианы за дают оптимальную асимптотику для нашего варианта постановки задачи. Существует также способ уменьшить сложность нахождения медианы до амортизированного : для этого надо помнить указатель на медианный элемент (или два элемента, среднее арифметическое которых даёт медиану, если чётное) и обновлять его при добавлении и удалении элементов (обновление будет стоить амортизированное — подумайте, почему!).
Если подумать, элементы, нужные для нахождения медианы, в дереве могут лежать только в трёх местах:
- в корне;
- в наименьшем элементе правого поддерева;
- в наибольшем элементе левого поддерева.
Действительно, давайте хранить две кучи, min-кучу и max-кучу, сбалансированного размера. При этом все элементы max-кучи должны быть меньше всех элементов min-кучи. При добавлении элемента нужно положить его в правильную кучу и сбалансировать их: это потребует конечного числа операций вида «извлеки экстремальное значение из одной кучи и положи в другую», стоящих . Получение медианы стоит , так как для этого нужен только максимум max-кучи и минимум min-кучи.
(Для этого кода я добавил в HeapWithRemoval методы pop ,
__len__ и __nonzero__ .)
Решение задачи с такой структурой данных становится элементарным:
Задача: количество инверсий
Дан массив чисел Нужно вычислить количество пар элементов массива, которые стоят в неправильном порядке, то есть при имеет место Если массив состоит из разных чисел от 1 до n, то чётность этого количества есть не что иное, как чётность перестановки, описываемой этим массивом.
Задача также обобщается на случай, когда плохими парами объявляются те, для которых и , где — некоторый положительный коэффициент.
В обоих случаях она решается за памяти и времени (кроме случая перестановки, в котором она решается за — но это уже совсем другая история). Элементарное решение с деревом выглядит примерно так: идём по массиву, на каждом шаге прибавляем к ответу количество элементов больше текущего (или текущего, умноженного на ) — дерево делает это за — и после этого добавляем в дерево текущий элемент.
Здесь уже одними кучами не обойтись!
Но и без дерева не обойтись тоже. Реализовать дерево несложно; но если его не балансировать, то в худшем случае асимптотика ухудшится до ! Что же делать?
Развернём задачу и пойдём с другого конца. Ведь можно сначала построить всё дерево целиком, на каждом шаге цикла удалять из него текущий элемент и прибавлять к ответу количество элементов меньше текущего. Построить сбалансированное дерево легко — достаточно изначально отсортировать массив и написать грамотную рекурсию:
А вот удаление из дерева — занятие муторное. Неудачный алгоритм удаления может испортить дерево и снова сделать его неприемлемой высоты! Поэтому давайте будем не удалять узлы из дерева, а лишь помечать их как удалённые. Тогда с высотой дерева за всё время работы алгоритма гарантированно ничего не произойдёт и мы получим вожделенное .
Правда, при таком подходе наличие узлов с повторяющимися элементами (особенно в большом количестве) может сильно испортить жизнь. Поэтому имеет смысл перед построением дерева произвести дедупликацию элементов с подсчётом кратности.
Решение задачи, соответственно, снова элементарное:
Бонусная задача: корзина с шарами
Эта задача вообще не требует самобалансирующихся деревьев — привожу её в качестве бонуса, чтобы рассказать ещё чуть-чуть о деревьях в Питоне.
Есть виртуальная корзина с шарами k разных цветов. В корзину можно положить шар определённого цвета, а можно вытащить случайный шар. Задача — программно смоделировать такую корзину с максимально эффективными операциями.
Очевидное решение — операций на добавление шара и на выбор случайного: храним массив с количеством шаров каждого цвета и суммарное количество шаров N, при необходимости выбрать случайный шар генерируем случайное число от 0 до N — 1 и смотрим, куда оно попало. (Например, есть 2 шара нулевого цвета, 1 шар первого цвета и 4 шара второго. Если выпало 0 или 1, выбрался шар нулевого цвета; если 2, то первого цвета; если 3, 4, 5 или 6 — второго цвета.)
Однако можно организовать корзину так, чтобы обе операции стоили . Для этого количество шаров каждого цвета нужно хранить в листьях дерева, а в остальных узлах — суммы по всем листьям в соответствующих поддеревьях.
Поскольку k задано, мы заранее знаем, сколько в дереве будет листьев. Количество узлов тоже не может измениться. Итого мы имеем дерево константного размера; когда мы попробуем этот размер вычислить, мы заметим, что у него есть ещё одно особенное свойство.
Предположим, что мы знаем, сколько нам нужно узлов. Попробуем уложить всё дерево в массив, как это делает Питон в модуле heapq :
У каждого узла есть свой индекс в массиве. У корня этот индекс — 0, у детей узла с индексом i — индексы (2 * i + 1) у левого и (2 * i + 2) у правого; у родителя узла с индексом i индекс (i — 1) // 2 .
Нам нужно, чтобы в дереве было определённое число листьев. Легко, когда это число — степень двойки. Листья в этом случае просто занимают целый слой дерева и в памяти располагаются подряд.
Но что, если k между двумя степенями двойки? Что ж, мы можем раскрыть несколько бутонов (обязательно с левого края!), чтобы число листьев стало таким, как нам надо:
Заметим, что при этом все листья по-прежнему расположены в памяти подряд! Это полезное свойство очень поможет нам при реализации.
Остаётся лишь вычислить, сколько нужно узлов для дерева с заданным количеством листьев k. Когда k — степень двойки, всё понятно: всего в дереве будет узлов. Удивительно, но и во всех остальных случаях тоже!
Мы ищем дерево минимальной высоты с k листьями и перекосом в сторону левого поддерева, если он необходим (то есть если k — не степень двойки).
Если , такое дерево состоит из одного (листового) узла и для него формула верна.
Если и степень двойки, формула снова верна.
Если и не степень двойки, нужно построить дерево с двумя поддеревьями, удовлетворяющими искомому свойству (и гарантированно непустыми!). Для них формула будет верна; в первом будет листьев, во втором — листьев (), и суммарно имеем число узлов
Примеры решения простых задач на языке Python
В этом разделе мы рассмотрим несколько примеров простых программ на Python. В основном эти программы будут выполнять арифметические операции сложения, вычитания, умножения и деления. Еще здесь мы рассмотрим несколько более сложные манипуляции со входными данными, например, нахождение палиндрома или поиск простых чисел при помощи решета Эратосфена. Также мы рассмотрим программы, позволяющие поменять местами значения двух переменных без ввода временной переменной, подсчитать количество разрядов в числе и многое другое.
Английский для программистов
Наш телеграм канал с тестами по английскому языку для программистов. Английский это часть карьеры программиста. Поэтому полезно заняться им уже сейчас
���� 5 классических задач по Python для начинающих с решениями
Эта классическая задача часто встречается на собеседованиях и олимпиадах. Рассмотрим несколько способов решения на Python.
На вход программе подаются два натуральных числа n и m. Напишите программу, которая создает матрицу размером n х m, заполнив ее по спирали числами от 1 до n x m. Спираль начинается в левом верхнем углу и закручивается по часовой стрелке.
Пример ввода:
Пример вывода:
Решение
2. Единственный выживший
Это вариант классической задачи Иосифа Флавия . В кругу стоят n человек, пронумерованных числами от 1 до n. Начинается расчет, при котором каждый k-й по счету человек выбывает из круга, после чего счет продолжается со следующего за ним человека. Напишите программу, определяющую номер человека, который останется в кругу последним.
Входные данные:
Числа n и k на отдельных строках.
Выходные данные:
Номер последнего оставшегося человека.
Решение
Способ 2 – рекурсия:
3. Определение магического квадрата
Магические квадраты издавна интриговали воображение людей: дата изготовления древнейшей сохранившейся таблицы относится к 2200 г. до н.э. Магический квадрат – это квадратная таблица размера n х n, составленная из всех чисел 1, 2, 3 … n 2 таким образом, что суммы по каждому столбцу, каждой строке и каждой диагонали равны между собой. Напишем программу, которая определяет, можно ли считать матрицу магическим квадратом.
Входные данные:
Число n, затем n строк с n цифр в каждой.
Выходные данные:
YES, если введенная матрица является магическим квадратом, и NO в обратном случае.
Решение
Способ 2 – с магической константой и множествами:
4. Разделение списка на подсписки
На вход подается строка чисел, из которой формируется список. Напишите программу, создающую вложенный список, элементами которого являются все возможные подсписки исходного списка, включая пустой.
Пример ввода:
Пример вывода:
Решение
5. Ходы шахматного ферзя
На шахматной доске 8 х 8 стоит ферзь. Отметьте положение ферзя на доске и все клетки, которые бьет ферзь. Клетку, где стоит ферзь, отметьте буквой Q, клетки, которые бьет ферзь, отметьте звездочками *, остальные клетки заполните точками. Шахматный ферзь может ходить по вертикали, горизонтали и по диагоналям.
Входные данные:
Координаты ферзя на шахматной доске в формате номер столбца (буква от a до h, слева направо) и номер строки (цифра от 1 до 8, снизу вверх).
Пример ввода:
Выходные данные:
Программа выводит стилизованное изображение шахматной доски со схемой возможных передвижений ферзя.