Метка: алгоритмы

Расстояние Левенштейна на Python

Как понять насколько близки две строки? Как поисковая система все равно находит то, что надо, даже если вы совершили пару опечаток в запросе? В этом вопросе нам поможет расстояние по Левенштейну или редакционное расстояние. Почему редакционное? Потому что мы считаем, сколько действий по редактированию одной строки нужно совершить, чтобы получить другую строку. Действия бывают следующими: вставка символа, удаление символа и замена одного символа другим.

Одинаковые строки имеют нулевое расстояние: не нужно ничего редактировать, первая и так равна второй. «Привет» и «Привт» имеют расстояние 1 (пропущена одна буква, остальное не изменилось). «Привет» и «привты» имеют расстояние 3 (одна замена «П» на «п», удаление буквы «е» и вставка «ы» на конце). Мы будем считать

Я не буду сюда копировать теорию и тем более доказательства, это вы можете изучить в Вики.

Давайте попробуем реализовать этот алгоритм в лоб по формуле:

Рекурсивная формула

Функция m – возвращает единицу, если символы не равны, иначе 0. Вот такой код получится:

def my_dist(a, b):
    def recursive(i, j):
        if i == 0 or j == 0:
            # если одна из строк пустая, то расстояние до другой строки - ее длина
            # т.е. n вставок
            return max(i, j)
        elif a[i - 1] == b[j - 1]:
            # если оба последних символов одинаковые, то съедаем их оба, не меняя расстояние
            return recursive(i - 1, j - 1)
        else:
            # иначе выбираем минимальный вариант из трех
            return 1 + min(
                recursive(i, j - 1),  # удаление
                recursive(i - 1, j),   # вставка
                recursive(i - 1, j - 1)  # замена
            )
    return recursive(len(a), len(b))

Вспомогательная функция, чтобы протестировать производительность:

from timeit import timeit

def test_lev_dist(f: callable, a, b, n=1):
    tm = timeit("f(a, b)", globals={
        'f': f, 'a': a, 'b': b
    }, number=n)
    r = f(a, b)
    print(f'a = {a!r} and b = {b!r} and {f.__name__} = {r} and time = {tm:.4f}')

test_lev_dist(my_dist, "hello world", "bye world!")
# a = 'hello world' and b = 'bye world!' and my_dist = 6 and time = 1.3829

Как можете видеть, первый вариант кода работает экстремально медленно, потому что много раз вычисляет функцию при одних и тех же входных параметрах. Давайте узнаем, сколько раз вызывается внутренняя функция. Для этого добавим декоратор, который считает число вызовов:

def count_calls(f):
    @wraps(f)
    def wrapped(*args, **kwargs):
        wrapped.n_calls += 1
        return f(*args, **kwargs)
    wrapped.n_calls = 0
    return wrapped

def my_dist(a, b):
    @count_calls
    def recursive(i, j):
        ...  # прочий код пропущен
    r = recursive(len(a), len(b))
    print('calls =', recursive.n_calls)
    return r

my_dist("hello world", "bye world!")
# calls =  3317804

Более 3 миллионов вызовов! И большинство из них с одинаковыми параметрами. А так как они повторяются, то можно их закешировать (при помощи lru_cache). Здесь размер кэша примерно равен числу различных комбинаций входных параметров.

from functools import lru_cache

def my_dist_cached(a, b):
    @count_calls
    @lru_cache(maxsize=len(a) * len(b))
    def recursive(i, j):
        if i == 0 or j == 0:
            return max(i, j)
        elif a[i - 1] == b[j - 1]:
            return recursive(i - 1, j - 1)
        else:
            return 1 + min(
                recursive(i, j - 1), 
                recursive(i - 1, j), 
                recursive(i - 1, j - 1)
            )

    r = recursive(len(a), len(b))
    print('calls = ', recursive.n_calls)
    return r

my_dist_cached("hello world", "bye world!")
# calls = 212

Количество вызовов сократилось до 212, а скорость работы увеличилась на порядки. Выкинем count_calls и проведем замеры времени для 10000 повторных вызовов.

def my_dist_cached(a, b):
    @lru_cache(maxsize=len(a) * len(b))
    def recursive(i, j):
        if i == 0 or j == 0:
            return max(i, j)
        elif a[i - 1] == b[j - 1]:
            return recursive(i - 1, j - 1)
        else:
            return 1 + min(
                recursive(i, j - 1),
                recursive(i - 1, j),
                recursive(i - 1, j - 1)
            )
    return recursive(len(a), len(b))

test_lev_dist(my_dist_cached, "hello world", "bye world!", n=10000)
# a = 'hello world' and b = 'bye world!' and my_dist_cached = 6 and time = 0.9740

Производительность улучшилась радикально (в прошлый раз мы прогоняли один вызов функции, а теперь 10000 раз, и то выходит быстрее). Однако, пока что объем требуемой памяти растет как O(len(a) * len(b)). Иными словами, для двух мегабайтных строк потребуются гигабайты памяти. Фактически в кэше будет хранится почти все матрица редактирований, а она нам не нужна целиком. Наша цель – правый нижний элемент.

Матрица редактирований recursive(i, j)
Матрица редактирований recursive(i, j)

Для его поиска можно обойтись лишь парой рядов: текущим и предыдущим. А остальные ряды не хранить в памяти. Так мы дойдем до конца таблицы, и нижний правый угол и будет искомым значением.

Вот пример реализации:

def distance(a, b):
    n, m = len(a), len(b)
    if n > m:
        # убедимся что n <= m, чтобы использовать минимум памяти O(min(n, m))
        a, b = b, a
        n, m = m, n

    current_row = range(n + 1)  # 0 ряд - просто восходящая последовательность (одни вставки)
    for i in range(1, m + 1):
        previous_row, current_row = current_row, [i] + [0] * n
        for j in range(1, n + 1):
            add, delete, change = previous_row[j] + 1, current_row[j - 1] + 1, previous_row[j - 1]
            if a[j - 1] != b[i - 1]:
                change += 1
            current_row[j] = min(add, delete, change)

    return current_row[n]

Объяснение. Сначала, чтобы использовать еще меньше памяти, мы можем поменять местами наши строки, чтобы длина рядов была минимальна. Это существенно экономит память, если одна из строк длинная, а другая короткая.

Затем мы понимаем, что нулевой ряд или столбец матрицы – просто восходящая последовательность. Потому что, чтобы из пустой строки получить любую не пустую, нужно ровно то число вставок, сколько символов в не пустой строке. И наоборот: n удалений из строки длины n приведут неизбежно к пустой строке.

Нам достаточно пары рядов.
Тут на картинке не ряды, а столбцы, но смысла это не меняет.

Потом мы шагаем по рядам матрицы, помня только текущий ряд и предыдущий, мы заполняем неизвестные клетки текущего ряда. Соседние клетки отвечают за вставку одного символа, удаление или замену (если символы неравны). Из трех возможных изменений мы выбираем то, чья стоимость наименьшая.

Эта версия еще быстрее, чем кэшированная:

 test_lev_dist(distance, "hello world", "bye world!", n=10000)
# a = 'hello world' and b = 'bye world!' and distance = 6 and time = 0.7374

Сложность этого алгоритма растет как произведение длин строк: O(n*m). Это еще не самый эффективный алгоритм. Для дальнейшего ускорения нужно воспользоваться древовидной структурой данных. Также неплохо бы учесть то, что на известном словаре можно заранее вычислить расстояния между словами.

Наконец-то, когда мы разобрались с принципом работы алгоритма, вспомним, что все велосипеды уже написаны до нас, да еще и на языке Си. Воспользуемся библиотечными функциями, установив пакет:

 pip install python-Levenshtein
import Levenshtein

test_lev_dist(Levenshtein.distance, "hello world", "bye world!", n=10000)
# a = 'hello world' and b = 'bye world!' and distance = 6 and time = 0.0032

Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈 

Пишем Brainfuck на Python

Есть мнение, что каждый программист должен написать в жизни хотя бы один язык программирования, либо реализовать уже существующий, но своими руками. В качестве примера мы начнем с самого простого и создадим Brainfuck. Согласно Вики:

Brainfuck — один из известнейших эзотерических языков программирования, придуман Урбаном Мюллером (нем.Urban Müller) в 1993 году, известен своим минимализмом. Название языка можно перевести на русский как вынос мозга, оно напрямую образовано от английского выражения brainfuck (brain — мозг, fuck — иметь половое сношение), т. е. заниматься ерундой. Язык имеет восемь команд, каждая из которых записывается одним символом. Исходный код программы на Brainfuck представляет собой последовательность этих символов без какого-либо дополнительного синтаксиса.

Википедия.

Описание 8 команд:

Команда BrainfuckОписание команды
Начало программывыделяется память под 30 000 ячеек с нулевыми начальными значениями
>перейти к следующей ячейке
<перейти к предыдущей ячейке
+увеличить значение в текущей ячейке на 1
-уменьшить значение в текущей ячейке на 1
.напечатать значение из текущей ячейки
,ввести извне значение и сохранить в текущей ячейке
[если значение текущей ячейки ноль, перейти вперёд по тексту программы на ячейку, следующую за соответствующей ] (с учётом вложенности)
]если значение текущей ячейки не нуль, перейти назад по тексту программы на символ [ (с учётом вложенности)

Реализация интерпретатора на Python

Интерпретатор читает программу и выполняет ее сразу на лету.

Первым делом надо прочитать целиком файл с исходником на BF, имя которого мы передаем первым параметром командной строки:

if __name__ == '__main__':
    if len(sys.argv) == 2:
        # один аргумент - имя файла, который надо выполнить
        with open(sys.argv[1], 'r') as f:
            code = f.read()
        run(code)  # запустить код
    else:
        print(f'usage: python {sys.argv[0]} file.bf')

После того, как код прочитан, мы создаем память из 30 000 ячеек, заполненными нулями. Устанавливаем счетчик команд и указатель на ленте ячеек на 0. Инициализация имеет такой вид:

mem_size = 30000
memory = [0] * mem_size  # оперативная память программы
data_ptr = 0  # индекс текущей ячейки памяти (memory)
instr_ptr = 0  # индекс текущей инструкции кода (code)

Далее в цикле читаем ячейку, если это одна из наших 8 команд, то выполняем, иначе пропускаем (это могут быть пробелы и переносы строк, их просто игнорируем). После выполнения команды, указатель сдвигается вправо по коду (увеличивается на единицу). Программа выполняется до тех пор, пока счетчик инструкций не выйдет за пределы размера кода.

С командами типа «+», «-«, «<«, «>» проблем в понимании быть не должно, они делают простые действия. Разве что, вам следует обратить внимание на то, что я зацикливаю оперативную память, если команда смещения переходит границу (команда < от 0 сдвинет на 29999 ячейку, а команда > с ячейки номер 29999 сдвигает на 0 ячейку).

Фрагмент цикла:

# выполняем - пока не вылетели за пределы кода
while instr_ptr < len(code):
    command = code[instr_ptr]  # текущая команда

    if command == '+':
        memory[data_ptr] += 1
    elif command == '-':
        memory[data_ptr] -= 1
    elif command == '>':
        data_ptr = (data_ptr + 1) % mem_size  # циклическая память
    elif command == '<':
        data_ptr = (data_ptr - 1) % mem_size  # циклическая память
    ...
    instr_ptr += 1   # сдвигаеи к следующей команде

Команда точка «.» печатает на экране единственный символ из текущий ячейки памяти. Я использую функцию chr, чтобы из числа получить символ. end='' указывает, что не надо переводить строку. Команда запятая «,» вводит символ из потока ввода. Считываю строку, беру первый символ и получаю его код функцией ord. Дополним код цикла обработкой ввода и вывода:

...
elif command == '.':
    # печатаем символ с кодом = значения текущей ячейки
    print(chr(memory[data_ptr]), end='')
elif command == ',':
    # ввод - берем код первого символа или 0, если ввод пустой
    inp = input()
    memory[data_ptr] = ord(inp[0]) if inp else 0
...

Это еще не все. Осталось самое сложное – обработка циклов (они же играю роль ветвлений в BF). Открывающая квадратная скобка «[« в code – команда, говорит нам, что нужно проверить текущую ячейку памяти в memory на равенство нулю. Если нуль, то прыгаем за пределы цикла – на соответствующую закрывающую скобку «]». Если не нуль, то дальше просто выполняем тело цикла. Когда натакливаемся на «]», тут тоже нужно проверить условие цикла, и если оно даст не ноль – вернуться к началу цикла, а иначе продолжить выполнять код дальше за скобкой.

Каждый раз во время выполнения кода искать нужную скобку – неудобно и медленно. Можно оптимизировать код, заранее пройдя по нему и запомнив, где какая скобка и где ее подруга – парная скобка. Для этого заведем словарь bracket_map. Для учета вложенности будем пользоваться структурой данных – стэк (из обычного списка):

# ключ и значения - индекс байта в коде
# по любой скобке находим ей пару
bracket_map = {}
stack = []
for pos, symbol in enumerate(code):
    # открыли скобку - положим на вершину стэка ее позицию
    if symbol == '[':
        stack.append(pos)
    elif symbol == ']':
        # вершина стэка - как раз наша парная скобка - была последней
        # удалим ее с вершины
        last_open_pos = stack.pop()
        # создадим парные записи
        bracket_map[pos] = last_open_pos
        bracket_map[last_open_pos] = pos

На иллюстрации ниже показано, что хранит этот словарь на примере простой программы.

Схема скобок для Hello world

Теперь мы готовы добавить в цикл исполнения обработку скобок. Просто проверяем условие, и когда нужно перемещаем указатель текущий команды на парную скобку: из начала цикла в конец, если ячейка содержит 0, и из конца цикла в начало, если не 0:

...
elif command == '[':
    # начало цикла - проверка текущей ячейки
    if not memory[data_ptr]:  # == 0
        # значит надо перейти на ячейку за соответствующей ей закрывающей скобкой
        instr_ptr = bracket_map[instr_ptr]
elif command == ']':
    # проверяем тоже условие, если выполняется, то скачем на начало цилка
    if memory[data_ptr]:  # не ноль
        # перемещаем на конец цикла
        instr_ptr = bracket_map[instr_ptr]

Готово! Интерпретатор завершен! Выполним простую программу hello_world.bf:

 ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++
 .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.
 ------.--------.>+.>.
(venv) ➜  bf python bf_interpretator.py hello_world.bf
Hello World! 

Работает! А вот как вам сортировка вставками на Brainfuck:

>>+>,[
    <[
        [>>+<<-]>[<<+<[->>+[<]]>>>[>]<<-]<<<
    ]>>[<<+>>-]<[>+<-]>[>>]<,
]<<<[<+<]>[>.>]

Запускаем. Пишем по очереди символы по одному, энтер после каждого. Чтобы завершить ввод массива – просто энтер без символа:

(venv) ➜  bf python bf_interpretator.py isort.bf      
8
4
6
1
9

14689  

Код программы и примеры загрузил на gist.

Компилятор Brainfuck на Python

Компилятор берет исходный код и превращает его в машинный исполняемый код. Не бойтесь, мы не будем писать в сложные по формату исполняемые файлы ассемблерные команды в виде байт. Поступим хитро. Сначала транслируем программу на BF в код на языке С, а потом обычным компилятором С транслируем код С в исполняемый файл.

Код обрамляется прелюдией, где мы подключаем стандартную библиотеку и инициализируем память. А также завершающими командами:

PRELUDE = """// brainfuck generated:
#include <stdio.h>
int main() {
    const int mem_size = 30000;
    char mem[mem_size];
    memset(mem, 0, mem_size);
    int cur = 0;
"""

ENDING = """
    return 0;
}
"""

Далее код компилятора BF в Си. Все по таблице из Википедии:

def compile_to_c(bf_code):
    instr_ptr = 0  # индекс текущей инструкции кода (code)

    indent = 4  # смещение пробелами - для красоты
    c_code = PRELUDE

    # выполняем - пока не вылетели за пределы кода
    for command in bf_code:
        content = ''
        if command == '+':
            content = 'mem[cur]++;'
        elif command == '-':
            content = 'mem[cur]--;'
        elif command == '>':
            content = 'cur++;'
        elif command == '<':
            content = 'cur--;'
        elif command == '.':
            content = 'putchar(mem[cur]);'
        elif command == ',':
            content = 'mem[cur] = getchar();'
        elif command == '[':
            content = 'while(mem[cur]) {'
        elif command == ']':
            content = '}'

        instr_ptr += 1  # сдвигаем к следующей команде

        if content:
            if command == ']':
                indent -= 4
            c_code += ' ' * indent + content + '\n'
            if command == '[':
                indent += 4

    c_code += ENDING
    return c_code

Сохраняем С-код на диск и вызывем компилятор cc:

c_code = compile_to_c(code)
c_file = f'{name}.c'
with open(c_file, 'w') as f:
    f.write(c_code)
os.system(f'cc {c_file} -o {name}.out')

Проверка:

(venv) ➜  bf python bf_compiler.py hello_world.bf
...тут какое-то предупреждение от компилятора...

(venv) ➜  bf ./hello_world.bf.out 
Hello World!

Код на Си получится примерно такой (я сократил его значительно, чтобы не занимать много места в статье):

// brainfuck generated:
#include <stdio.h>
int main() {
    const int mem_size = 30000;
    char mem[mem_size];
    memset(mem, 0, mem_size);
    int cur = 0;
    mem[cur]++;
    mem[cur]++;
    mem[cur]++;
    mem[cur]++;
    mem[cur]++;
    while(mem[cur]) {
        cur++;
        mem[cur]++;
        mem[cur]++;
        mem[cur]++;
        cur++;
        mem[cur]++;
        cur--;
        cur--;
        cur--;
        cur--;
        mem[cur]--;
    }
    cur++;
    mem[cur]++;
    mem[cur]++;
    putchar(mem[cur]);
    cur++;
    mem[cur]++;
    putchar(mem[cur]);
    mem[cur]++;
    mem[cur]++;
    mem[cur]++;
    mem[cur]++;
    mem[cur]++;
    mem[cur]++;
    putchar(mem[cur]);
    cur++;
    putchar(mem[cur]);

    return 0;
}

Код компилятора в том же самом gist.

Замечания. В это варианте запятая будет работать не так, как в интерпретаторе выше. Поэтому код с сортировкой будет вести себя иначе. И второе: проверял компилятор на своей системе macOS, на Windows компилятор скорее всего не будет работать, если только вы его не запускаете из подсистемы Linux или Cygwin или подобных.

Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈 

Короткое замыкание

Провод горит в розетке

Поговорим о логических операциях. Допустим у нас есть цепочка из or

if x() or y() or z():
    print('bingo!')

Чтобы print сработал, нужно, чтобы хотя бы один из трех вызовов давал бы True (или приводился к True). Что если x() сразу вернет True? Тогда, очевидно, все выражение будет равняться True в любом случае и независимо от того, что будет в y() и z(). Если смысл их вычислять? Нет! Python и не вычисляет. Тем самым достигается некоторая оптимизация, которая называется short circuiting (или короткое замыкание).

Это хорошо, только, если в оставшихся логических выражениях нет побочных эффектов, потому они не будут выполнены, если вычисление логического выражение будет остановлено. Давайте проверим:

def check(b):
    print('check.')
    return b

if True or check(True):
    print('ok.')  # ok.

if False or check(True):
    print('ok.')  # check. ok.

В первом случае check не работает, потому что первый операнд True уже предопределит судьбу выражения. А во втором случае – сработает, потому первый операнд False не дает определенности и нужно вычислить check().

Аналогично все с оператором and: как только первый операнд в цепочке вернет False, выполнение прекратиться. 

if True and False and check(True):
    ...  # не выполнится check

Встроенные функции all и any тоже используют короткое замыкание, то есть all перестает проверять на первом False, а any – на первом True.

all(check(i) for i in [1, 1, 0, 1, 1])  # выведет 3 check из 5
any(check(i) for i in [0, 1, 0, 0, 0])  # выведет 2 check из 5

Эту особенность стоит помнить. Лично я сталкивался с алгоритмом, где было что-то вроде:

while step(x, y, True) or step(x, y, False): ...

По задумке оба step должны выполнятся на каждой итерации, но из-за короткого замыкания второй из них иногда не выполнялся; алгоритм работал неверно.

Что если не нужно такое поведение?

Оказывается, что можно применять побитовые операторы «или» и «и» в логических выражениях, при этом каждый операнд будет вычисляться в любом случае. Цепочка вычисления не прервется, даже если результат уже очевиден. 

def check(b):
    print('check.')
    return b

check(False) & check(False)  # & – битовое и
check(True) | check(False)   # | - битовое или

В этом случае оба check сработают!

❗Внимание: есть подводные камни. Этот прием работает корректно только с булевыми типами! Если мы подставим целые числа, то результат может быть не тот, что ожидается. Яркий пример – это числа 1 и 2:

>>> bool(1 and 2)
True
>>> bool(1 & 2)
False
>>> 1 & 2
0

Поэтому, в логическом выражении, если тип операнда не булев, то его нужно привести. Недавний пример должен быть переписан так:

while bool(step(x, y, True)) | bool(step(x, y, False)):
    ...

Второй подводный камень: приоритет операторов | и & гораздо выше, чем у not, and и or. Так что, если миксуем их, то всегда ставим скобки: 

>>> not False or True
True
>>> not False | True
False
>>> (not False) | True
True

Не подумайте, что я призываю использовать побитовые операции вместо логических. Но в редких случаях это может быть оправдано.

Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈 

​​Сортировка пузырьком

Сегодня простая, но важная тема. Алгоритм сортировки пузырьком, его проходят на курсах, его часто спрашивают на собеседованиях. Сортировка — это процесс выстраивания массива или списка по возрастанию или убыванию. На примере чисел: [3, 1, 4, 2] → [1, 2, 3, 4].

Смысл пузырьковой сортировки заключается в следующем: мы начинаем с начала списка и сравниваем элементы попарно (нулевой и первый), если нулевой больше первого, то меняем их местами. Независимо от того, была ли замена или нет, мы шагаем вправо и сравниваем элементы вновь. Если на прошлом шаге была замена, то на этом шаге у нас окажется тот же элемент, и если он опять оказался больше, то «всплывет» снова вправо. Так за один проход наибольший элемент всплывет в самый-самый конец списка, подобно тому, как пузырек воздуха всплывает в бутылке воды. Когда все пузырьки всплывут – список будет отсортирован.

📎 Пример: a = [3, 1, 4, 2] – 4 элемента:

Первый проход:
  1. Сравним a[0] = 3 и a[1] = 1, 3 > 1. Меняем их местами. Теперь a = [1, 3, 4, 2].
  2. Сравним a[1] = 3 и a[2] = 4, 3 < 4. Менять не надо.
  3. Сравним a[2] = 4 и a[3] = 2, 4 > 2. Меняем. a = [1, 3, 2, 4].

Проход окончен. 4 «всплыла» в самый конец списка на свое место a[3]. Поэтому мы не трогаем больше конец списка, но список еще не отсортирован до конца, и следующий проход будет рассматривать только первые 3 элемента списка.

Второй проход:
  1. Сравним a[0] = 1 и a[1] = 3, 1 < 3. Менять не надо.
  2. Сравним a[1] = 3 и a[2] = 2, 3 > 2. Меняем их. a = [1, 2, 3, 4]. Проход окончен.
Третий проход:
  1. Сравним a[0] = 1 и a[1] = 3, 1 < 3. Менять не надо. Список отсортирован. Можно выходить.

👨‍💻 Переходим к реализации на Python:

def bubble_sort(a):
    n = len(a)
    
    # номер прохода i = 0..(n-2), т.е. (n-1 раз):
    for i in range(n - 1):
        # номер сравнения j = 0..(n - i - 2)
        for j in range(n - i - 1):
            # сравниваем только соседние элементы
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]

Алгоритм прост, но можно запутаться в индексах: с какого элемента и куда бежать, что с чем сравнивать. Как лучше запомнить:

  • Начинаем всегда с начала (0-го элемента).
  • Число проходов меньше на 1, чем число элементов
  • С каждым проходом мы делаем все меньше и меньше сравнений, так как сортированный хвост списка растет на 1 после каждого прохода
  • Сравниваем только соседние элементы a[j] > a[j + 1], (а не i и j).
  • Если знак сравнения перевернуть, то сортировка будет по убыванию.

Временная сложность алгоритма квадратичная O(n^2) – имеются два вложенных цикла по элементам. Поэтому алгоритм медлителен для больших списков.  В реальной жизни чаще применяются другие алгоритмы сортировки, но пузырек до сих пор не забывают преподавать и спрашивать.

🐉 Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈 

Куча и очередь с приоритетом

Порядок обхода кучи

Очередь с приоритетом – это такая коллекция, которая поддерживает обязательно две следующие операции: вставка элемента с некоторым приоритетом (это может быть число или другой сравнимый объект) и извлечение элемента с наибольшим (или наименьшим приоритетом).