Слабая куча - Weak heap

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

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

Описание

Слабую кучу проще всего понять как упорядоченную кучу многостороннее дерево хранится в виде двоичного дерева с использованием соглашения «правый дочерний левый брат». (Это эквивалентно обычному бинарное дерево с левым потомком и правым братом.)

В многостороннем дереве и при условии максимальной кучи каждый родительский ключ больше или равен (≥) все дочерние ключи (и, таким образом, по индукции, все члены поддерева).

Выражаясь в виде двоичного дерева, это переводится в следующие инварианты:[1]

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

Последнее условие является следствием того факта, что неявное двоичное дерево является полное двоичное дерево.

Структура этого дерева очень точно соответствует традиционному 1-основан (Анентафель ) неявная организация двоичного дерева, где узел k имеет номер следующего брата (левого ребенка) 2k и первый ребенок (правый ребенок) пронумерован 2k + 1, добавив дополнительный корень с номером 0. У этого корня нет братьев и сестер, только первый ребенок, который является узлом 1 (2×0 + 1).

Эта структура очень похожа на структуру биномиальной кучи, с деревом высоты час состоит из корня и высотных деревьев час − 1, час − 2, ..., 1. Идеальная (без пропусков листьев) слабая куча с 2п элементы точно изоморфны биномиальной куче того же размера,[2] но два алгоритма обрабатывают размеры, которые не являются 2 по-другому: биномиальная куча использует несколько совершенных деревьев, а слабая куча использует одно несовершенное дерево.

Слабые кучи требуют возможности обменивать левые и правые дочерние элементы (и связанные поддеревья) узла. В явном (указатель на основе) представления дерева, это просто. В неявном (множество ), для этого требуется один «обратный бит» на каждый внутренний узел, чтобы указать, какой дочерний элемент считается левым. Таким образом, слабая куча не является строго неявной структурой данных, поскольку требует О(п) дополнительное пространство (1/2 бит на узел). Однако часто можно найти место для этого дополнительного бита в структуре узла, например, с помощью пометка указателя который уже присутствует.

В неявном двоичном дереве узел k с обратным битом рk есть родитель ⌊k/2⌋, левый ребенок 2k + рk, и правый ребенок 2k + 1 − рk.

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

Операции на слабых кучах

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

Узел высоты час имеет час − 1 дети: первый ребенок роста час − 1, второй ребенок роста час − 2и так далее до последнего дочернего элемента высоты 1. Их можно найти, перейдя по первой дочерней ссылке, а затем по последующим соседним ссылкам.

У него также есть следующие братья и сестры по росту час − 1, час − 2, так далее.

Родитель узла в многостороннем дереве называется его «выделенным предком». Чтобы найти это в двоичном дереве, найдите двоичного родителя узла. Если узел является правым дочерним элементом (первым дочерним элементом), родительский элемент является выделенным предком. Если узел является левым дочерним узлом (следующим родственником), его выделенный предок такой же, как и его двоичный родительский элемент. В неявном дереве найти бинарный родительский элемент легко, но необходимо проконсультироваться с его обратным битом, чтобы определить, к какому типу дочернего узла относится узел. (Ранние работы использовали термин «дедушка и бабушка» для именитого предка,[3] значение, сбивающее с толку, отличается от обычного «родитель или родитель».)

Хотя выдающийся предок может быть бревно2п уровни высоко в дереве, средний расстояние 2. (Это по крайней мере 1, и в половине случаев мы рекурсивны, поэтому D = 1 + D/2, означающий, что D = 2.) Таким образом, достаточно даже простого итерационного алгоритма для поиска выделенного предка.

Как и биномиальные кучи, основная операция с непрочными кучами - объединение двух куч равной высоты. час, сделать непрочную кучу высотой час+1. Для этого требуется ровно одно сравнение между корнями. Какой бы корень больше (при условии максимальной кучи), это последний корень. Его первый дочерний элемент - это теряющий корень, который сохраняет своих дочерних элементов (правое поддерево). Потомки победившего корня устанавливаются как братья и сестры проигравшего.

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

  • Первая - это обычная слабая куча (следующая родственная ссылка существует, но игнорируется).
  • Второй - это воображаемая куча, образованная путем связывания выделенного предка первого корня (многостороннего родителя) со следующими братьями и сестрами первого корня.

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

После сравнения двух корней слияние происходит одним из двух способов:

  1. (Выделенный предок больше или равен.) Ничего не нужно перемещать, и результатом слияния является выделенный предок.
  2. (Первый корень больше.) Бинарные потомки первого корня (первый потомок и следующий брат) обмениваются (с помощью обратного бита), а затем обмениваются первый корень и его выделенный предок (путем копирования).

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

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

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

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

Сортировка слабой кучи

Слабые кучи могут использоваться для сортировки массива, по сути, так же, как и обычный heapsort.[3] Сначала создается слабая куча из всех элементов массива, а затем корень многократно обменивается с последним элементом, который отсеивается до нужного места.

Слабая куча п элементы могут быть сформированы в п − 1 сливается. Это может быть выполнено в различном порядке, но простая реализация снизу вверх работает от конца массива к началу, объединяя каждый узел с его выделенным предком. Обратите внимание, что находка выделенный предок упрощается, потому что обратные биты во всех родительских кучах, которые объединяются, не изменяются по сравнению с их начальным состоянием («не реверсировано»), и поэтому с ними не нужно обращаться.

Как и в случае с heapsort, если массив для сортировки больше, чем Кэш процессора, производительность улучшается, если поддеревья объединяются, как только становятся доступными два одинаковых размера, а не объединяются все поддеревья на одном уровне перед переходом к следующему.[4]

Просеять в слабую кучу можно за час = ⌈Log2п⌉ сравнения, в отличие от 2 журнала2п для двоичной кучи или 1,5 журнала2п для "сортировка снизу вверх "вариант. Это делается путем" слияния ": после замены корня последним элементом кучи найдите последний (высота 1) дочерний элемент корня. Объедините его с корнем (его выделенным предком), в результате получится допустимая куча высотой 2 в глобальном корне. Затем перейдите к предыдущему родственнику (бинарному родительскому элементу) последнего объединенного узла и снова выполните слияние. Повторяйте, пока не будет достигнут корень, когда он будет правильным для всего дерева.

Операции с приоритетной очередью

В слабой максимальной куче максимальное значение может быть найдено (за постоянное время) как значение, связанное с корневым узлом; аналогично, в слабой минимальной куче минимальное значение может быть найдено в корне.

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

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

Варианты слабой структуры кучи допускают постоянное амортизированное время вставки и клавиши уменьшения, соответствующие времени для Куча Фибоначчи.[2]

История и приложения

Слабые кучи были введены Даттон (1993), как часть варианта куча сортировки алгоритм, который (в отличие от стандартной сортировки кучи с использованием двоичных куч) может использоваться для сортировки п предметы, использующие только п бревно2п + О(п) сравнения.[3][5] Позже они были исследованы как более широко применимая структура данных очереди приоритетов.[6][7]

Рекомендации

  1. ^ Эделькамп, Стефан (26 мая 2011 г.), Питерс, Вреда; Блэк, Пол Э. (ред.), "слабая куча", Словарь алгоритмов и структур данных, получено 2015-12-01
  2. ^ а б Эделькамп, Стефан; Элмасри, Амр; Катаянен, Юрки (октябрь 2012 г.), «Слабая структура данных: варианты и приложения» (PDF), Журнал дискретных алгоритмов, 16: 187–205, CiteSeerX  10.1.1.455.1213, Дои:10.1016 / j.jda.2012.04.010, МИСТЕР  2960353.
  3. ^ а б c Даттон, Рональд Д. (1993), "Сортировка слабой кучи", КУСОЧЕК, 33 (3): 372–381, Дои:10.1007 / bf01990520.
  4. ^ Бойесен, Джеспер; Катаянен, Юрки; Спорк, Маз (2000). «Пример проектирования производительности: строительство кучи» (PostScript). ACM Журнал экспериментальной алгоритмики. 5 (15). CiteSeerX  10.1.1.35.3248. Дои:10.1145/351827.384257. Альтернативный источник PDF.
  5. ^ Эделькамп, Стефан; Вегенер, Инго (2000), «О исполнении СЛАБЫЙ ОБЕСПЕЧЕНИЕ", Материалы симпозиума по теоретическим аспектам информатики (STACS 2000) (PDF), Конспект лекций по информатике, 1770, Springer-Verlag, стр. 254–266, CiteSeerX  10.1.1.21.1863, Дои:10.1007/3-540-46541-3_21.
  6. ^ Бруун, Асгер; Эделькамп, Стефан; Катаянен, Юрки; Расмуссен, Йенс (2010), «Сравнительный анализ слабых куч и их родственников на основе политик» (PDF), Материалы 9-го Международного симпозиума по экспериментальным алгоритмам (SEA 2010), Конспект лекций по информатике, 6049, Springer-Verlag, стр. 424–435, Дои:10.1007/978-3-642-13193-6_36, ISBN  3-642-13192-1, выложить резюме (PDF).
  7. ^ Эделькамп, Стефан; Элмасри, Амр; Катаянен, Юрки (2012), "Слабое семейство приоритетных очередей в теории и практике" (PDF), Труды восемнадцатого компьютинга: Австралазийский симпозиум по теории (CATS 2012), 128, Дарлингхерст, Австралия: Австралийское компьютерное общество, Inc., стр. 103–112, ISBN  978-1-921770-09-8.

дальнейшее чтение

  • Эделькамп, Стефан; Элмасри, Амр; Катаянен, Юрки (ноябрь 2013 г.). "Слабые кучи спроектированы" (PDF). Журнал дискретных алгоритмов. 23: 83–97. Дои:10.1016 / j.jda.2013.07.002. Мы предоставляем каталог алгоритмов, которые оптимизируют стандартные алгоритмы различными способами. В качестве критериев оптимизации мы рассматриваем время работы в наихудшем случае, количество инструкций, ошибочные предсказания переходов, промахи кеша, сравнения элементов и перемещения элементов.
  • Эделькамп, Стефан; Элмасри, Амр; Катаянен, Юрки; Вайс, Армин (июль 2013 г.). Слабые кучи и друзья: последние события (PDF). Комбинаторные алгоритмы - 24-й международный семинар. Руан, Франция. Дои:10.1007/978-3-642-45278-9_1.