Слабая куча
В информатике слабая куча — это структура данных для приоритетных очередей , сочетающая в себе функции двоичной и биномиальной кучи . Его можно хранить в массиве в виде неявного двоичного дерева, например двоичной кучи, и он имеет гарантии эффективности, присущие биномиальным кучам.
Алгоритм сортировки с использованием слабых куч (weak-heapsort) использует количество сравнений, близкое к теоретической нижней границе числа сравнений, необходимых для сортировки списка , поэтому он особенно полезен, когда сравнение является дорогостоящим, например, при сравнении строк с использованием полный алгоритм сопоставления Unicode .
Описание [ править ]
Слабую кучу легче всего понять как упорядоченное в куче многопутевое дерево, хранящееся в виде двоичного дерева с использованием соглашения «правый-потомок-левый-брат». (Это эквивалентно обычному двоичному дереву с левым дочерним элементом и правым сестринским элементом , но противоположно этому .)
В многопутевом дереве и при условии максимальной кучи каждый родительский ключ больше или равен ( ≥ ) всем дочерним ключам (и, следовательно, по индукции, всем членам поддерева).
Выраженное в виде двоичного дерева, это преобразуется в следующие инварианты: [1]
- Корневой узел не имеет левого дочернего узла
- Для каждого узла значение, связанное с этим узлом, больше или равно значениям, связанным со всеми узлами в его правом поддереве.
- Листья дерева имеют высоту, находящуюся внутри друг друга.
Последнее условие является следствием того, что неявное двоичное дерево является полным двоичным деревом .
Структура этого дерева очень аккуратно сопоставляется с традиционным на основе 1 ( Ahnentafel неявным двоичным деревом ), где узел k имеет следующего брата (левого дочернего элемента) с номером 2 k и первого дочернего элемента (правого дочернего элемента) с номером 2 k + 1 . добавив дополнительный корень с номером 0 . У этого корня нет братьев и сестер, только первый дочерний элемент, который является узлом 1 ( 2×0 + 1 ).
Эта структура очень похожа на структуру биномиальной кучи: дерево высоты h состоит из корня плюс деревьев высот h - 1 , h - 2 , ..., 1 . Идеальная (без недостающих листьев) слабая куча с 2 н элементы точно изоморфны биномиальной куче того же размера, [2] но эти два алгоритма по-разному обрабатывают размеры, не являющиеся степенью 2 : биномиальная куча использует несколько идеальных деревьев, а слабая куча использует одно несовершенное дерево.
Слабые кучи требуют возможности менять местами левых и правых дочерних элементов (и связанных поддеревьев) узла. В явном ( на основе указателей ) представлении дерева это просто. В неявном ( массивном ) представлении для этого требуется один «обратный бит» на каждый внутренний узел, чтобы указать, какой дочерний элемент считается левым дочерним элементом. Таким образом, слабая куча не является строго неявной структурой данных, поскольку для нее требуется O ( n ) дополнительного пространства ( 1/2 на бита узел). Однако часто можно найти место для этого дополнительного бита в структуре узла, например, пометив указатель уже существующий .
В неявном двоичном дереве узел k с обратным битом r k имеет родителя ⌊ k / 2 ⌋ , левый ребенок 2 k + r k и правый ребенок 2 k + 1 - r k .
Если рассматривать как многопутевое дерево, каждый узел в слабой куче связан с двумя другими: «следующим братом» и «первым дочерним элементом». В неявном дереве ссылки фиксированы, поэтому какая из двух ссылок является родственной, а какая — первым дочерним элементом, указывается обратным битом.
Операции со слабыми кучами [ править ]
Обратите внимание, что каждый узел в слабой куче можно считать корнем меньшей слабой кучи, игнорируя его следующего брата. Узлы без первого дочернего элемента автоматически считаются допустимыми слабыми кучами.
Узел высоты h имеет h - 1 дочерних элементов: первый дочерний элемент высоты h - 1 , второй дочерний элемент высоты h - 2 и так далее до последнего дочернего элемента высоты 1 . Их можно найти, перейдя по первой дочерней ссылке, а затем по последующим однородным ссылкам.
У него также есть следующие братья и сестры высотой h - 1 , h - 2 и т. д.
Родитель узла в многопутевом дереве называется его «выдающимся предком». Чтобы найти это в двоичном дереве, найдите двоичного родителя узла. Если узел является правым дочерним элементом (первым дочерним элементом), родительским элементом является выделенный предок. Если узел является левым дочерним элементом (следующим одноуровневым), его выделенный предок такой же, как и его двоичный родительский узел. В неявном дереве найти двоичного родителя легко, но необходимо обратиться к его обратному биту, чтобы определить, к какому типу дочернего узла относится узел. (Ранние статьи использовали термин «бабушка и дедушка» для обозначения выдающегося предка, [3] значение, которое до смешения отличается от обычного «родителя родителя».)
Хотя выделенный предок может находиться на уровне log 2 n в дереве, среднее расстояние равно 2 . (Это как минимум 1 , и в половине случаев мы используем рекурсию, поэтому D = 1 + D /2 , что означает, что D = 2. ) Таким образом, даже простого итерационного алгоритма для поиска выделенного предка достаточно.
Как и в случае с биномиальными кучами, основная операция над слабыми кучами — это объединение двух куч одинаковой высоты h для создания слабой кучи высотой h +1 . Для этого требуется ровно одно сравнение между корнями. Какой бы корень ни был больше (при условии максимальной кучи), он является конечным корнем. Его первым дочерним элементом является теряющий корень, который сохраняет своих детей (правое поддерево). Дочерние элементы выигравшего корня устанавливаются как братья и сестры проигравшего корня.
Эту операцию можно выполнить с неявной древовидной структурой, поскольку объединяемые кучи никогда не бывают произвольными. Скорее, две кучи формируются как часть просеивания узла вверх по многопутевому дереву:
- Первый — это обычная слабая куча (следующая одноуровневая ссылка существует, но игнорируется).
- Второй — это воображаемая куча, образованная путем связывания выделенного предка первого корня (многопоточного родителя) со следующими братьями и сестрами первого корня.
Вначале инварианты кучи применяются везде, за исключением , возможно, между первым корнем и его выделенным предком. Все остальные узлы меньше или равны своим выдающимся предкам.
После сравнения двух корней слияние происходит одним из двух способов:
- (Выделенный предок больше или равен.) Ничего перемещать не нужно, и результатом слияния является выделенный предок.
- (Первый корень больше.) Двоичные дочерние элементы первого корня (первый дочерний элемент и следующий одноуровневый элемент) обмениваются местами (с использованием обратного бита), а затем обмениваются первым корнем и его выдающимся предком (путем копирования).
Второй случай работает, потому что в многопутевом дереве каждый узел сохраняет своих дочерних элементов. Первый корень продвигается вверх по дереву, поскольку он больше, чем его выдающийся предок. Таким образом, он безопасно больше, чем все предыдущие дети предка.
Однако предыдущий предок не является безопасным родителем для старых дочерних элементов первого корня, поскольку он меньше первого корня и поэтому не гарантируется, что он больше или равен всем своим дочерним элементам.
Путем замены двоичных дочерних элементов соответствующее подмножество старых дочерних элементов пониженного предка (которые безопасно меньше или равны ему) понижается вместе с ним. Новые братья и сестры пониженного предка — это повышенные старые дочерние элементы первого корня, которые безопасно меньше или равны повышенному первому корню.
После этой операции неизвестно, сохраняется ли инвариант между новым выделенным предком и его выделенным предком, поэтому операция повторяется до тех пор, пока не будет достигнут корень.
Слабая пирамидальная сортировка [ править ]
Слабые пирамиды можно использовать для сортировки массива, по сути, так же, как и обычную пирамидальную сортировку . [3] Сначала из всех элементов массива строится слабая куча, а затем корень неоднократно меняется местами с последним элементом, который просеивается на подобающее место.
Слабая куча из n элементов может быть сформирована за n − 1 слияний. Это можно делать в разном порядке, но простая реализация снизу вверх работает от конца массива к началу, объединяя каждый узел с его выдающимся предком. Обратите внимание, что поиск выделенного предка упрощается, поскольку обратные биты во всех родителях объединяемых куч не изменяются по сравнению с их исходным состоянием («не перевернуты»), и поэтому к ним не нужно обращаться.
Как и в случае с пирамидальной сортировкой, если сортируемый массив больше, чем кэш ЦП , производительность повышается, если поддеревья объединяются, как только становятся доступными два поддерева одинакового размера, а не объединяются все поддеревья на одном уровне перед переходом к следующему. [4]
Отсеивание в слабой куче можно выполнить с помощью сравнений h = ⌈log 2 n ⌉ , в отличие от 2 log 2 n для двоичной кучи или 1,5 log 2 n для варианта пирамидальной сортировки «снизу вверх ». Это делается путем «слияния»: после замены корня на последний элемент кучи найдите последний (высота 1) дочерний элемент корня. Объедините это с корнем (его выдающимся предком), в результате чего в глобальном корне появится допустимая куча высотой 2. Затем перейдите к предыдущему одноуровневому (двоичному родительскому) узлу последнего объединенного узла и снова выполните объединение. Повторяйте до тех пор, пока не будет достигнут корень, тогда он станет правильным для всего дерева.
Операции с приоритетной очередью [ править ]
В слабой максимальной куче максимальное значение может быть найдено (за постоянное время) как значение, связанное с корневым узлом; аналогично в слабой минимальной куче минимальное значение можно найти в корне.
Как и в случае с двоичными кучами, слабые кучи могут поддерживать типичные операции структуры данных очереди с приоритетом : вставку, минимальное удаление, удаление или уменьшение ключа, за логарифмическое время на каждую операцию.
Отсеивание выполняется с использованием того же процесса, что и в двоичных кучах. Новый узел добавляется на уровне листа, затем сравнивается со своим выделенным предком и при необходимости заменяется местами (операция слияния). Это повторяется до тех пор, пока не исчезнет необходимость в свопах или не будет достигнут корень.
Варианты структуры слабой кучи допускают постоянные вставки с амортизированным временем и ключи уменьшения, соответствующие времени для куч Фибоначчи . [2]
История и приложения [ править ]
Слабые кучи были представлены Даттоном (1993) как часть варианта алгоритма сортировки кучами , который (в отличие от стандартной сортировки кучами с использованием двоичных куч) можно было использовать для сортировки n элементов, используя только n log 2 n + O ( n ) сравнений. [3] [5] Позже они были исследованы как более широко применимая структура данных очереди с приоритетами. [6] [7]
Ссылки [ править ]
- ^ Эделькамп, Стефан (26 мая 2011 г.), Питерс, Вреда; Блэк, Пол Э. (ред.), «Слабая куча» , Словарь алгоритмов и структур данных , получено 1 декабря 2015 г.
- ^ Перейти обратно: а б Эделькамп, Стефан; Эльмасри, Амр; Катаджайнен, Юрки (октябрь 2012 г.), «Структура данных слабой кучи: варианты и приложения» (PDF) , Journal of Discrete Algorithms , 16 : 187–205, CiteSeerX 10.1.1.455.1213 , doi : 10.1016/j.jda. 2012.04.010 , МР 2960353 .
- ^ Перейти обратно: а б с Даттон, Рональд Д. (1993), «Сортировка слабой пирамидой», BIT , 33 (3): 372–381, doi : 10.1007/bf01990520 , S2CID 5387832 .
- ^ Божесен, Йеспер; Катахайнен, Юрки; Спорк, Маз (2000). «Пример повышения производительности: конструкция кучи» (PostScript) . Журнал экспериментальной алгоритмики ACM . 5 (15). CiteSeerX 10.1.1.35.3248 . дои : 10.1145/351827.384257 . S2CID 16705375 . Альтернативный источник PDF .
- ^ Эделькамп, Стефан; Вегенер, Инго (2000), «О производительности WEAK-HEAPSORT », Stacs 2000 (PDF) , Конспекты лекций по информатике, том. 1770, Springer-Verlag, стр. 254–266, CiteSeerX 10.1.1.21.1863 , doi : 10.1007/3-540-46541-3_21 , ISBN 978-3-540-67141-1 .
- ^ Брюун, Асгер; Эделькамп, Стефан; Катахайнен, Юрки; Расмуссен, Йенс (2010). «Бенчмаркинг слабых куч и их родственников на основе политики» (PDF) . Материалы 9-го Международного симпозиума по экспериментальным алгоритмам (SEA 2010) . Конспекты лекций по информатике. Том. 6049. Шпрингер-Верлаг. стр. 424–435. дои : 10.1007/978-3-642-13193-6_36 . ISBN 978-3-642-13192-9 . Архивировано из оригинала (PDF) 11 августа 2017 г. .
- Брюун, Асгер; Эделькамп, Стефан; Катахайнен, Юрки; Расмуссен, Йенс (2010). «Бенчмаркинг слабых групп и их родственников на основе политики». Экспериментальные алгоритмы (PDF) . Конспекты лекций по информатике. Том. 6049. стр. 424–435. дои : 10.1007/978-3-642-13193-6_36 . ISBN 978-3-642-13192-9 . S2CID 1334592 . Архивировано из оригинала (PDF) 27 декабря 2016 г. - через Semantic Scholar.
- ^ Эделькамп, Стефан; Эльмасри, Амр; Катаджайнен, Юрки (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 г.). Слабые группы и друзья: последние события . Комбинаторные алгоритмы - 24-й международный семинар. Руан , Франция. дои : 10.1007/978-3-642-45278-9_1 .