Рубрики

Турнирное дерево (Winner Tree) и бинарная куча

Дана команда из N игроков. Сколько нужно минимум игр, чтобы найти второго лучшего игрока?

Мы можем использовать аргументы противника на основе дерева турниров (Binary Heap).

Турнирное дерево — это форма min (max) кучи, которая является полным двоичным деревом. Каждый внешний узел представляет игрока, а внутренний узел представляет победителя. В дереве турниров каждый внутренний узел содержит победителя, а каждый листовой узел содержит одного игрока.

В двоичном дереве будет N — 1 внутренних узлов с N листовыми (внешними) узлами. Подробности см. В этом посте (укажите n = 2 в уравнении, приведенном в посте).

Очевидно, что для выбора лучшего игрока из N игроков необходимо исключить (N — 1) игроков, то есть нам нужно минимум (N — 1) игр (сравнений). Математически мы можем это доказать. В двоичном дереве I = E — 1, где I — количество внутренних узлов, а E — количество внешних узлов. Это значит, чтобы найти максимальный или минимальный элемент массива, нам нужно N — 1 (внутренние узлы) сравнения.

Второй лучший игрок

Информация, полученная во время выбора лучшего игрока, может быть использована для минимизации количества сравнений при отслеживании следующих лучших игроков. Например, мы можем выбрать второго лучшего игрока в (N + log 2 N — 2) сравнениях.

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

Вышеуказанное дерево содержит 4 конечных узла, которые представляют игроков и имеют 3 уровня 0, 1 и 2. Первоначально 2 игры проводятся на уровне 2, одна между 5 и 3 и еще одна между 7 и 8. В следующем ходу еще одна игра проводится между 5 и 8, чтобы определить окончательного победителя. Всего нам нужно 3 сравнения. Для второго лучшего игрока нам нужно отследить кандидатов, участвовавших с финальным победителем, что приводит к 7 как второй лучший.

Медиана отсортированных массивов

Турнирное дерево может эффективно использоваться для поиска медианы отсортированных массивов. Предположим, что задано M отсортированных массивов одинакового размера L (для простоты). Мы можем прикрепить все эти отсортированные массивы к дереву турниров, по одному массиву на лист. Нам нужно дерево высоты CEIL (log 2 M), чтобы иметь как минимум M внешних узлов.

Рассмотрим пример. Дано 3 (M = 3) отсортированных целочисленных массива с максимальным размером 5 элементов.

{ 2, 5, 7, 11, 15 } ---- Array1
{1, 3, 4} ---- Array2
{6, 8, 12, 13, 14} ---- Array3

Какой должна быть высота турнирного дерева? Нам нужно построить дерево турниров с высотой log 2 3. = 1.585 = 2, округленное до следующего целого числа. Бинарное дерево высотой 2 будет иметь 4 листа, к которым мы можем прикрепить массивы, как показано на рисунке ниже.

После первого турнира дерево выглядит так:

Мы можем наблюдать, что победитель от Array2. Следовательно, следующий элемент из Array2 будет погружен, и игры будут проводиться по пути победителя предыдущего турнира.

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

После второго турнира дерево выглядит так:

Следующий победитель — от Array1, поэтому следующий элемент массива Array1, равный 5, перейдет в следующий раунд, а следующий турнир будет разыгран по пути 2.

Турниры можно продолжать до тех пор, пока мы не получим медианный элемент, который равен (5 + 3 + 5) / 2 = 7-й элемент. Обратите внимание, что существуют еще лучшие алгоритмы для нахождения медианы объединения отсортированных массивов, подробности см. По ссылкам, приведенным ниже.

В общем случае с M отсортированными списками размера L 1 , L 2 … L m требуется временная сложность O ((L 1 + L 2 +… + L m ) * logM) для объединения всех массивов и O (m * logM) время, чтобы найти медиану, где м — медианная позиция.

Выберите наименьший миллион элементов из одного миллиарда несортированных элементов:

В качестве простого решения мы можем отсортировать миллиардные числа и выбрать первый миллион.

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

Разделите большой массив (возможно, хранящийся на диске) на массивы меньшего размера размером один миллион каждый (или даже меньше, которые могут быть отсортированы на машине). Сортируйте эти 1000 массивов небольшого размера и сохраняйте их на диске в виде отдельных файлов. Создайте турнирное дерево, которое может иметь как минимум 1000 листовых узлов (дерево должно быть высотой 10 с 2 9 <1000 <2 10 , если отдельный размер файла еще меньше, нам потребуется больше листовых узлов). Каждый конечный узел будет иметь механизм, который выбирает следующий элемент из отсортированного файла, хранящегося на диске. Мы можем сыграть в дерево турниров, чтобы извлечь первый миллион элементов.

Общая стоимость = сортировка 1000 списков по миллиону каждый + построение дерева + турниры

Реализация
Нам нужно построить дерево снизу вверх. Все листовые узлы заполнены первыми. Начните с левого края дерева и заполните по ширине (то есть от 2 k-1 до 2 k- 1, где k — глубина дерева) и играйте в игру. После практики с несколькими примерами будет легко написать код. Реализация обсуждается в коде ниже

Второй минимальный элемент с использованием минимальных сравнений

Похожие сообщения
Найдите самый маленький и второй самый маленький элемент в массиве .
Второй минимальный элемент с использованием минимальных сравнений

Венки . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Турнирное дерево (Winner Tree) и бинарная куча

0.00 (0%) 0 votes