Для многих людей, начинающих свой путь в программировании, концепция структур данных и их использования не получает широкого освещения, отчасти из-за небольшого размера и объема проектов, которые могут быть выполнены в короткие сроки. . Это, однако, приводит к отсутствию предвидения в будущем, потому что по мере того, как проекты становятся все больше и больше, понимание того, как правильно реализованная структура данных может сделать вашу конечную программу более эффективной. Сегодня мы рассмотрим только один метод сбора — Binary Heap.

Что, черт возьми, такое бинарная куча?

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

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

Тогда почему бы мне просто не использовать метод Sort()?

Это может сработать для небольших наборов данных, но представьте на секунду, что ваш массив состоит из шести миллионов элементов. Вы добавляете элемент, который должен находиться в позиции 100, но добавление элемента в ваш массив автоматически помещает его в конец очереди для начала, затем начинается сортировка, касаясь каждого элемента в массиве хотя бы один раз. Это минимум 6 000 000 касаний, чтобы вставить один элемент. Для сравнения, бинарное дерево будет касаться только небольшого количества элементов вашего массива, вероятно, около 20–40 из них, что экономит ваше время, которое вы можете выделить на другие вещи. Как оно работает? Давайте посмотрим на структуру и узнаем.

Теперь, почему это называется двоичной кучей? Что ж, когда мы смотрим на каждое число в дереве, далее именуемое узлами, у них может быть не более двух потомков или потомков. Также стоит отметить, что самый большой узел, в данном случае 20, находится на вершине кучи, и что каждый родительский узел больше, чем его дочерние узлы, если они есть. Это известно как максимальная куча, где мы всегда сортируем по большему числу. Существуют варианты для наименьшего числа, но в этой статье мы будем придерживаться максимальной кучи.

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

Начнем выращивать дерево!

Давайте начнем с пустого дерева и добавим один элемент, номер 1.

Здесь наше дерево имеет только один узел и, следовательно, является самым большим, но что произойдет, если мы добавим еще одно число? Давайте добавим число 5 и посмотрим, что произойдет.

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

Теперь дерево отсортировано и мы можем добавить еще один элемент. На этот раз мы добавим число 3. Для тех, кто занимается математикой, вы уже знаете, что 3 больше, чем 1, но меньше, чем 5, поэтому оно не поменяется местами со своим родителем. число 1 уже занимает левую ветвь, поэтому число 3 остается там, где оно было сначала размещено, и сортировка не требуется.

Теперь давайте добавим еще одно число, давайте пойдем по-крупному или пойдем домой, вот идет число 14! Но подождите, наш родитель может иметь только до двух детей. что нам теперь делать? всякий раз, когда строка или уровень заполнены, мы начинаем новый уровень, используя дочерние элементы текущего индекса. Давайте спросим Бейонсе, с чего мы начинаем наш новый уровень:

Правильный! Опять же, когда это возможно, мы используем самый левый узел, который можем, поэтому 14 будет начинаться как левый дочерний элемент нашего узла 1. Мы снова начнем сортировать наше дерево, переключая 14 и 1, но 14 также больше, чем 5, поэтому после переключения с 1, 14 и 5 поменяются местами, а 14 займет свое место на троне.

Обход полного дерева.

Надеюсь, теперь вы видите процесс и то, как мы можем постоянно расширять это дерево, если будем продолжать добавлять элементы. Мы добавляем новый элемент в самый нижний, самый левый открытый узел, а затем сравниваем наш новый номер с его родителем. Если новое число больше, чем его родитель, числа меняются местами, затем процесс продолжается до тех пор, пока родительский узел не станет больше, чем новое число, или новое число не станет самым верхним узлом, также известным как корневой узел. По мере роста дерева становится очевидным, насколько меньше шагов требуется для сортировки, чтобы найти наибольшее число. Вот 5-уровневое дерево с 29 узлами:

Возвращаясь к предыдущему примеру с использованием метода Sort(), добавление нового числа будет означать, что нам придется сравнить наше новое число со всеми 29 другими числами, но давайте посмотрим, какие наиболее возможные шаги должно было бы пройти наше дерево. сделать. мы добавим число больше, чем текущий корень, поэтому мы добавим 95 к дереву. Глядя на каждого родителя 95, нужно будет сравнить, чтобы отсортировать наше дерево, нужно всего 4 сравнения, что далеко от 29.

Отламывание некоторых веток.

Чтобы закончить, давайте посмотрим, как мы удаляем элементы из нашего дерева, в конце концов, нам нужно будет удалить элемент из нашей очереди, как только мы с ним закончим. Чтобы начать процесс удаления, мы меняем наш корневой узел на последний узел в нашем дереве. Используя полное дерево, к которому мы только что добавили, это число будет 68. Затем мы удалим число 95, его работа выполнена. Теперь у нас есть 68 в качестве корневого узла, но это не самое большое число в нашем дереве, поэтому нам нужно отсортировать.

Мы начинаем сравнивать 68, текущий корневой узел, с двумя его дочерними элементами. Оба больше 68, но правая ветвь нашего дерева — единственная с открытым узлом, так как мы не можем начать новый уровень, пока текущий не будет заполнен. Мы меняем местами 86 на 68, затем продолжаем движение вниз по нашему дереву, в этом случае всегда выбирая правую ветвь, так как на левых ветвях нет открытых узлов. Наше 68 заканчивается на 4-м уровне, где 62 является дочерним узлом, а 86 — корневым узлом.

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

Благодарим визуализатор двоичного дерева за создание изображений, использованных в этой статье. Дайте им взглянуть на: btv.melezinek.cz