Найти наименьший/наибольший элемент в несортированном массиве

Дан массив и число k, где k меньше размера массива, нам нужно найти k-й наименьший элемент в данном массиве. При этом задано, что все элементы массива различны.

Data Science: Алгоритмы и Структуры данных

Решение проблемы в поиске наименьшего/наибольшего элемента

Алгоритм 1

Простое решение - отсортировать данный массив с помощью сортировки О(N log N). После чего вернуть элемент с индексом K-1 в отсортированном массиве

Алгоритм 2

Можно оптимизировать - создав минимальную кучу из заданных n элементов и вызвать стандартный метод extractMin (что такое Heap(куча) - мы как раз поговорим завтра)

Data Science: Алгоритмы и Структуры данных

Heap (куча) - структура данных

Куча - это особая древовидная структура данных, в которой дерево представляет собой законченное двоичное дерево. Обычно кучи бывают 2х типов:

1. Max-Heap - ключ, в корневом узле, должен быть наибольшим среди ключей, присутсвующих во всех дочерних элементах. Это свойство рекурсивно истинно для всех последующих от корня узла

2. Min-Heap - полностью наоборот. То есть в корне находится самый минимальный элемент.

Data Science: Алгоритмы и Структуры данных

Представление Двоичной кучи

Как мы вчера уже поняли - двоичная куча - это полноценное двоичное дерево. Представляется куча в виде массива.

Корневой элемент будет всегда в arr0 (нулевом индексе массива). В табличке (на картинке) - как раз указано, как в дальнейшем берутся индексы.

Есть интересные свойства:

1. arr(i-1) / 2 - вернет всегда родительский узел

2. arr(2 * i) + 1 - вернет левый дочерний узел

3. arr(2 * i) + 2 - вернет правый дочерний узел

Data Science: Алгоритмы и Структуры данных

Операции над Min Heap

1. getMin - возвращает корневой элемент вашего Min Heap

2. extractMin - удаляет минимальный элемент из MinHeap (сложность О(logN) из-за того что надо поддерживать свойства кучи)

3. reduceKey - уменьшает значение ключа (так же сложность O(logN)

4. insert - вставка нового элемента (занимает также O(logN)) Добавит вам новый ключ в конец дерева, если новый ключ больше, чем родительский, вам не придется ничего делать. В противном случае нужно пройти вверх, чтобы исправить свойства кучи

5. delete - удаление ключа (также займет в худшем случае O(logN)

Data Science: Алгоритмы и Структуры данных

Биномиальная куча

Основным применением двоичной кучи является реализация очереди приоритетов. Биномиальная куча - это расширение обычной двоичной кучи, которое обеспечивет более быструю операцию объеденения или слияния.

Биномиальное дерево порядка 0 имеет 1 узел. Кго уровня можно построить, взяв два биномиальных дерева порядка к-1 и сделав одно из них крайним левым дочерним элементом.

Data Science: Алгоритмы и Структуры данных

Свойства биномиального дерева

1. У данного дерева 2К узлов
2. Глубина дерева равна К
3. На глубине i имеется ровно kCi узлов для i = 0, 1, ..., k
4. Корень дерева имеет степень k, а потомки корня сами являются биномиальными деревьями с порядком k-1, k-2,..0 слева направо

Data Science: Алгоритмы и Структуры данных

Операции над биномиальной кучей

1. insert(H, k) - вставкляет ключ К в биномиальную кучу H. Эта операция сначала создает биномиальную кучу с одним ключом, а затем вызывает объеденение для H

2. getMin(H) - пройдется по списку корней биномиальных деревьев и выдаст вам минимальный ключ

3. extractMin(H) - сначала вызывается метод getMin(), чтобы найти минимальное ключевое значение, после чего создаст новое биномиальное дерево, правильно его отформатировав

4. delete(H) - операция удаления, как и с операцией удаления в бинарном дереве: сначала уменьшает ключ до минус бесконечности, а после вызывает extractMin()

5. reduceKey(H) - сравниваем ключ уменьшения с ключом родительским, и если родительский ключ больше , мы меняем ключи и повторяем для родительского узла. Останавливаемся тогда, когда родительский элемент имеет наименьший ключ.

6. union - операция объеденения, которая используется во многих других функциях, как вы могли наблюдать.

Data Science: Алгоритмы и Структуры данных

Китайская нейросеть, которая заменяет подписку на GPT — бесплатно и оффлайн

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

⚡️Что ждет вас на вебинаре?

– Покажем, как установить DeepSeek на компьютер и пользоваться нейросетью оффлайн, без подписки и передачи данных в облако;
– Объясним, чем отличаются версии DeepSeek и какие модели использовать для текста, кода, анализа данных, обучения и исследований;
– Проверим DeepSeek на реальных задачах: коде, документах, расшифровках созвонов и работе с собственными файлами;
– Покажем, как монетизировать навыки работы с локальными ИИ и как работать быстрее GPT бесплатно.

Регистрируйтесь прямо сейчас

Участники эфира получат чек-лист по выбору модели под задачу и подборку 20+ сценариев для ИИ-помощника на своем компьютере, который работает с вашими файлами.

Эфир подойдёт всем, кто хочет пользоваться ИИ без лимитов и зависимости от чужих серверов, монетизировать навыки и оставаться в тренде технологий 2026 года.

Бесплатный практикум – по ссылке.

Сортировка кучей (HeapSort)

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

Data Science: Алгоритмы и Структуры данных

Задача: отсортировать почти отсортированный массив

Дан массив из n элементов, где каждый элемент находится не более чем на k от своей целевой позиции. Разработайте алгоритм, который выполняет сортировку за время O(n log k)

Data Science: Алгоритмы и Структуры данных

Решение задачи: отсортировать почти отсортированный массив

Я же не зря завел данную задачу, аккуратно после темы кучи (Heap). Как раз подобный вид сортировки - лучше сделать как раз при помощи Heap!

Алгоритм

1. Создайте минимальную кучу (min Heap) размера k + 1, с первыми элементами k + 1 (это кстати у вас займет где-то O(k)

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

Data Science: Алгоритмы и Структуры данных

Структура данных: Граф

Граф состоит из конечного набора вершин(узлов) и набора ребер, которые соединяют пару узлов.

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

Data Science: Алгоритмы и Структуры данных