http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=NastyaВикиконспекты - Вклад участника [ru]2026-08-04T13:36:28ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%9D%D0%9C_(%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8)&diff=39007СНМ (наивные реализации)2014-06-13T12:05:36Z<p>Nastya: /* С помощью списка */</p>
<hr />
<div>'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами. <br />
__TOC__<br />
== Описание ==<br />
Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1 </tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.<br />
<br />
Определены две операции:<br />
* <math> \mathrm{union(x, y)} </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y </tex><br />
* <math> \mathrm{find (x)} </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x </tex><br />
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.<br />
<br />
[[Файл:DSU_1_Example.png|500px|center|Пример работы СНМ]]<br />
<br />
== Реализации ==<br />
=== С помощью массива ===<br />
<br />
<!--<br />
'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|<tex>O(n)</tex><br />
|}<br />
--><br />
<br />
Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.<br />
<br />
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда <math> \mathrm{union} </math> работает за <tex>O(n)</tex>.<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве </font><br />
</code><br />
<code> <br />
'''int''' find(k):<br />
'''return''' s[k]<br />
</code><br />
<code> <br />
'''func''' union(x, y):<br />
'''if''' s[x] == s[y]<br />
'''return'''<br />
'''else'''<br />
t = s[y]<br />
'''for''' i = 0 '''to''' n - 1<br />
'''if''' s[i] == t<br />
s[i] = s[x]<br />
</code><br />
<br />
=== С помощью списка ===<br />
<!--'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|}--><br />
<br />
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head </tex>. Значит <math> \mathrm{find} </math> работает за <tex> O(1) </tex>.<br />
<br />
Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head </tex>. Таким образом, <math> \mathrm{union} </math> работает за <tex> O(n) </tex>.<br />
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.<br />
<br />
<code><br />
'''struct''' SetItem <br />
'''int''' data <br />
'''int''' head<br />
'''SetItem''' next<br />
'''SetItem''' tail<br />
<br />
'''SetItem''' s[n]<br />
<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i].data = i<br />
s[i].head = s[i] <br />
s[i].tail = s[i]<br />
s[i].next = null<br />
</code> <br />
<code><br />
'''int''' find('''SetItem''' x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font><br />
'''return''' x.head.data<br />
</code> <br />
<code><br />
'''func''' union('''SetItem''' x, '''SetItem''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font><br />
x = x.head<br />
y = y.head<br />
'''if''' x == y<br />
'''return'''<br />
x.tail.next = y <font color=green> // соединим списки </font><br />
x.tail = y.tail <font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font><br />
'''while''' y <tex> \neq </tex> null <font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font><br />
y.head = x<br />
y = y.next<br />
</code><br />
[[Файл:DSU_list_example.png|800px|center|Пример объединения двух множеств (union)]]<br />
<br />
== Другие реализации ==<br />
* [[СНМ (списки с весовой эвристикой)]]<br />
* [[СНМ (реализация с помощью леса корневых деревьев)]]<br />
<br />
== Источники информации ==<br />
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.<br />
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]<br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BD%D0%B5%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D0%B5%D0%BA%D0%B0%D1%8E%D1%89%D0%B8%D1%85%D1%81%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2 Википедия: Система непересекающихся множеств]<br />
[[Категория: Дискретная математика и алгоритмы]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%9D%D0%9C_(%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8)&diff=39005СНМ (наивные реализации)2014-06-13T12:02:01Z<p>Nastya: /* С помощью списка */</p>
<hr />
<div>'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами. <br />
__TOC__<br />
== Описание ==<br />
Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1 </tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.<br />
<br />
Определены две операции:<br />
* <math> \mathrm{union(x, y)} </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y </tex><br />
* <math> \mathrm{find (x)} </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x </tex><br />
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.<br />
<br />
[[Файл:DSU_1_Example.png|500px|center|Пример работы СНМ]]<br />
<br />
== Реализации ==<br />
=== С помощью массива ===<br />
<br />
<!--<br />
'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|<tex>O(n)</tex><br />
|}<br />
--><br />
<br />
Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.<br />
<br />
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда <math> \mathrm{union} </math> работает за <tex>O(n)</tex>.<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве </font><br />
</code><br />
<code> <br />
'''int''' find(k):<br />
'''return''' s[k]<br />
</code><br />
<code> <br />
'''func''' union(x, y):<br />
'''if''' s[x] == s[y]<br />
'''return'''<br />
'''else'''<br />
t = s[y]<br />
'''for''' i = 0 '''to''' n - 1<br />
'''if''' s[i] == t<br />
s[i] = s[x]<br />
</code><br />
<br />
=== С помощью списка ===<br />
<!--'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|}--><br />
<br />
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head </tex>. Значит <math> \mathrm{find} </math> работает за <tex> O(1) </tex>.<br />
<br />
Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head </tex>. Таким образом, <math> \mathrm{union} </math> работает за <tex> O(n) </tex>.<br />
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.<br />
<br />
<code><br />
'''struct''' SetItem <br />
'''int''' data <br />
'''int''' head<br />
'''SetItem''' next<br />
'''SetItem''' tail<br />
<br />
'''SetItem''' s[n]<br />
<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i].data = i<br />
s[i].next = null<br />
s[i].head = s[i]<br />
</code> <br />
<code><br />
'''int''' find('''SetItem''' x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font><br />
'''return''' x.head.data<br />
</code> <br />
<code><br />
'''func''' union('''SetItem''' x, '''SetItem''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font><br />
x = x.head<br />
y = y.head<br />
'''if''' x == y<br />
'''return'''<br />
x.tail.next = y <font color=green> // соединим списки </font><br />
x.tail = y.tail <font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font><br />
'''while''' y <tex> \neq </tex> null <font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font><br />
y.head = x<br />
y = y.next<br />
</code><br />
[[Файл:DSU_list_example.png|800px|center|Пример объединения двух множеств (union)]]<br />
<br />
== Другие реализации ==<br />
* [[СНМ (списки с весовой эвристикой)]]<br />
* [[СНМ (реализация с помощью леса корневых деревьев)]]<br />
<br />
== Источники информации ==<br />
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.<br />
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]<br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BD%D0%B5%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D0%B5%D0%BA%D0%B0%D1%8E%D1%89%D0%B8%D1%85%D1%81%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2 Википедия: Система непересекающихся множеств]<br />
[[Категория: Дискретная математика и алгоритмы]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%9D%D0%9C_(%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8)&diff=39003СНМ (наивные реализации)2014-06-13T11:55:49Z<p>Nastya: /* Источники информации */</p>
<hr />
<div>'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами. <br />
__TOC__<br />
== Описание ==<br />
Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1 </tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.<br />
<br />
Определены две операции:<br />
* <math> \mathrm{union(x, y)} </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y </tex><br />
* <math> \mathrm{find (x)} </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x </tex><br />
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.<br />
<br />
[[Файл:DSU_1_Example.png|500px|center|Пример работы СНМ]]<br />
<br />
== Реализации ==<br />
=== С помощью массива ===<br />
<br />
<!--<br />
'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|<tex>O(n)</tex><br />
|}<br />
--><br />
<br />
Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.<br />
<br />
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда <math> \mathrm{union} </math> работает за <tex>O(n)</tex>.<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве </font><br />
</code><br />
<code> <br />
'''int''' find(k):<br />
'''return''' s[k]<br />
</code><br />
<code> <br />
'''func''' union(x, y):<br />
'''if''' s[x] == s[y]<br />
'''return'''<br />
'''else'''<br />
t = s[y]<br />
'''for''' i = 0 '''to''' n - 1<br />
'''if''' s[i] == t<br />
s[i] = s[x]<br />
</code><br />
<br />
=== С помощью списка ===<br />
<!--'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|}--><br />
<br />
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head </tex>. Значит <math> \mathrm{find} </math> работает за <tex> O(1) </tex>.<br />
<br />
Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head </tex>. Таким образом, <math> \mathrm{union} </math> работает за <tex> O(n) </tex>.<br />
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.<br />
<br />
<code><br />
'''srtruct''' nameOfStruct <br />
int head<br />
*nameOfStruct next<br />
int data<br />
<br />
nameOFStruct s[n]<br />
<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i].data = i<br />
s[i].next = null<br />
s[i].head = s[i]<br />
</code> <br />
<code><br />
'''int''' find(nameOfStruct x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font><br />
'''return''' x.head.data<br />
</code> <br />
<code><br />
'''func''' union(nameOfStruct x, nameOfStruct y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font><br />
x = x.head<br />
y = y.head<br />
'''if''' x == y<br />
'''return'''<br />
x.tail.next = y <font color=green> // соединим списки </font><br />
x.tail = y.tail <font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font><br />
'''while''' y <tex> \neq </tex> null <font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font><br />
y.head = x<br />
y = y.next<br />
</code><br />
[[Файл:DSU_list_example.png|800px|center|Пример объединения двух множеств (union)]]<br />
<br />
== Другие реализации ==<br />
* [[СНМ (списки с весовой эвристикой)]]<br />
* [[СНМ (реализация с помощью леса корневых деревьев)]]<br />
<br />
== Источники информации ==<br />
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.<br />
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]<br />
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BD%D0%B5%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D0%B5%D0%BA%D0%B0%D1%8E%D1%89%D0%B8%D1%85%D1%81%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2 Википедия: Система непересекающихся множеств]<br />
[[Категория: Дискретная математика и алгоритмы]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%B2%D0%B5%D1%80%D1%85%D1%83&diff=39002Реализация запроса в дереве отрезков сверху2014-06-13T11:52:12Z<p>Nastya: /* Реализация */</p>
<hr />
<div>Данная операция позволяет выполнять запросы на [[Дерево отрезков. Построение|дереве отрезков]], причем алгоритм запускается от корня и рекурсивно идет сверху вниз.<br />
<br />
==Алгоритм==<br />
''Замечание.''<br />
Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая {{---}} нет).<br />
<br />
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на полуинтервале <tex>[a .. b)</tex>.<br />
<br />
В качестве параметров рекурсий передаем следующие переменные:<br />
* <tex>node</tex> {{---}} номер (в массиве с деревом отрезков) текущей вершины дерева.<br />
* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого полуинтервала.<br />
<br />
Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы полуинтервала, за которые "отвечает" наша вершина.<br />
Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).<br />
<br />
Для текущего состояния проверяем следующие условия :<br />
<br />
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.<br />
:''Например'': текущий <tex>[1..3)</tex>, а искомый <tex>[3 .. 5)</tex>;<br />
<br />
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.<br />
:''Например'': текущий <tex>[2..3)</tex>, а искомый <tex>[2..4)</tex>;<br />
<br />
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.<br />
<br />
Так как на каждом уровне дерева рекурсия может дойти до не более, чем двух вершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок, за который отвечает вершина предыдущего уровня), а всего уровней <tex>\log n</tex>, то операция выполняется за <tex>O(\log n)</tex>.<br />
<br />
==Пример==<br />
<br />
Рассмотрим данный алгоритм на примере задачи RSQ (Range Sum Query {{---}} запрос суммы на отрезке).<br />
<br />
При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях.<br />
<br />
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма <br />
{{---}} это отрезок <tex>[1 .. 4]</tex> (полуинтервал <tex>[1 .. 5)</tex>).<br />
[[Файл:Image_4.png|right|602px|Пример рабoты алгоритма]]<br />
Рассмотрим данный алгоритм на определенных глубинах рекурсии (то есть на разных уровнях дерева):<br />
<br />
* На глубине <tex>0</tex>. (на рисунке глубина обозначена слева от уровня). Текущий полуинтервал <tex>[0 .. 8)</tex> пересекается с <tex>[1 .. 5) \Rightarrow</tex> переходим по рекурсивным вызовам на <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине <tex>1</tex>. <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex> пересекаются с <tex> [1 .. 5) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex>[0 ..<br />
2)</tex>, <tex>[2 .. 4)</tex>, <tex>[4 .. 6)</tex> и <tex>[6 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине <tex>2</tex>. <br />
** <tex>[0 .. 2)</tex> и <tex>[4 .. 6)</tex> пересекаются с <tex>[1 .. 5) \Rightarrow </tex> переходим в листья <tex>0, 1, 4, 5 </tex><br />
** <tex>[2 .. 4) </tex> полностью лежит внутри <tex>[1 .. 5) \Rightarrow </tex> возвращаем сумму на этом отрезке<br />
** <tex>[6 .. 8)</tex> не пересекается с <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
<br />
<br />
* На глубине <tex>3</tex>. <br />
** Листья <tex>1, 4</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них<br />
** Листья <tex>0, 5</tex> лежат вне <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
Таким образом ответ на полуинтервале <tex>[1 .. 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 .. 2)</tex>, <tex>[2 .. 4)</tex> и <tex>[4 .. 5)</tex>.<br />
<br />
==Реализация==<br />
Рассмотрим реализацию задачи о дереве отрезков с произвольной ассоциативной бинарной операцией.<br />
<br />
Пусть в узлах дерева хранятся структуры из трех полей:<br />
* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.<br />
* <tex>right</tex> {{---}} правая граница этого полуинтервала.<br />
* <tex> res</tex> {{---}} результат операции на полуинтервале.<br />
<br />
<code><br />
<br />
'''int''' query ('''int''' node, '''int''' a, '''int''' b) <br />
l = tree[node].left<br />
r = tree[node].right <br />
'''if''' [l, r) <tex>\cap </tex> [a, b) == <tex> \varnothing</tex><br />
'''return''' neutral<br />
'''if''' [l, r) <tex>\subset</tex> [a, b)<br />
'''return''' tree[node].res<br />
'''return''' query (node * 2 + 1, a, b) <tex> \circ </tex> query (node * 2 + 2, a, b)<br />
</code><br />
<br />
==См. также==<br />
* [[Реализация запроса в дереве отрезков снизу]]<br />
<br />
==Источники информации==<br />
* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]<br />
* [http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Дерево отрезков — Википедия]<br />
<br />
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор дерева отрезков]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Дерево отрезков]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%B2%D0%B5%D1%80%D1%85%D1%83&diff=39001Реализация запроса в дереве отрезков сверху2014-06-13T11:49:20Z<p>Nastya: /* Реализация */</p>
<hr />
<div>Данная операция позволяет выполнять запросы на [[Дерево отрезков. Построение|дереве отрезков]], причем алгоритм запускается от корня и рекурсивно идет сверху вниз.<br />
<br />
==Алгоритм==<br />
''Замечание.''<br />
Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая {{---}} нет).<br />
<br />
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на полуинтервале <tex>[a .. b)</tex>.<br />
<br />
В качестве параметров рекурсий передаем следующие переменные:<br />
* <tex>node</tex> {{---}} номер (в массиве с деревом отрезков) текущей вершины дерева.<br />
* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого полуинтервала.<br />
<br />
Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы полуинтервала, за которые "отвечает" наша вершина.<br />
Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).<br />
<br />
Для текущего состояния проверяем следующие условия :<br />
<br />
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.<br />
:''Например'': текущий <tex>[1..3)</tex>, а искомый <tex>[3 .. 5)</tex>;<br />
<br />
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.<br />
:''Например'': текущий <tex>[2..3)</tex>, а искомый <tex>[2..4)</tex>;<br />
<br />
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.<br />
<br />
Так как на каждом уровне дерева рекурсия может дойти до не более, чем двух вершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок, за который отвечает вершина предыдущего уровня), а всего уровней <tex>\log n</tex>, то операция выполняется за <tex>O(\log n)</tex>.<br />
<br />
==Пример==<br />
<br />
Рассмотрим данный алгоритм на примере задачи RSQ (Range Sum Query {{---}} запрос суммы на отрезке).<br />
<br />
При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях.<br />
<br />
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма <br />
{{---}} это отрезок <tex>[1 .. 4]</tex> (полуинтервал <tex>[1 .. 5)</tex>).<br />
[[Файл:Image_4.png|right|602px|Пример рабoты алгоритма]]<br />
Рассмотрим данный алгоритм на определенных глубинах рекурсии (то есть на разных уровнях дерева):<br />
<br />
* На глубине <tex>0</tex>. (на рисунке глубина обозначена слева от уровня). Текущий полуинтервал <tex>[0 .. 8)</tex> пересекается с <tex>[1 .. 5) \Rightarrow</tex> переходим по рекурсивным вызовам на <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине <tex>1</tex>. <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex> пересекаются с <tex> [1 .. 5) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex>[0 ..<br />
2)</tex>, <tex>[2 .. 4)</tex>, <tex>[4 .. 6)</tex> и <tex>[6 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине <tex>2</tex>. <br />
** <tex>[0 .. 2)</tex> и <tex>[4 .. 6)</tex> пересекаются с <tex>[1 .. 5) \Rightarrow </tex> переходим в листья <tex>0, 1, 4, 5 </tex><br />
** <tex>[2 .. 4) </tex> полностью лежит внутри <tex>[1 .. 5) \Rightarrow </tex> возвращаем сумму на этом отрезке<br />
** <tex>[6 .. 8)</tex> не пересекается с <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
<br />
<br />
* На глубине <tex>3</tex>. <br />
** Листья <tex>1, 4</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них<br />
** Листья <tex>0, 5</tex> лежат вне <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
Таким образом ответ на полуинтервале <tex>[1 .. 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 .. 2)</tex>, <tex>[2 .. 4)</tex> и <tex>[4 .. 5)</tex>.<br />
<br />
==Реализация==<br />
Рассмотрим реализацию задачи о дереве отрезков с произвольной ассоциативной бинарной операцией.<br />
<br />
Пусть в узлах дерева хранятся структуры из трех полей:<br />
* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.<br />
* <tex>right</tex> {{---}} правая граница этого полуинтервала.<br />
* <tex> res</tex> {{---}} сумма на полуинтервале.<br />
<br />
<code><br />
<br />
'''int''' query ('''int''' node, '''int''' a, '''int''' b) <br />
l = tree[node].left<br />
r = tree[node].right <br />
'''if''' [l, r) <tex>\cap </tex> [a, b) == <tex> \varnothing</tex><br />
'''return''' neutral<br />
'''if''' [l, r) <tex>\subset</tex> [a, b)<br />
'''return''' tree[node].res<br />
'''return''' query (node * 2 + 1, a, b) + query (node * 2 + 2, a, b)<br />
</code><br />
<br />
==См. также==<br />
* [[Реализация запроса в дереве отрезков снизу]]<br />
<br />
==Источники информации==<br />
* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]<br />
* [http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Дерево отрезков — Википедия]<br />
<br />
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор дерева отрезков]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Дерево отрезков]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%B2%D0%B5%D1%80%D1%85%D1%83&diff=38999Реализация запроса в дереве отрезков сверху2014-06-13T11:44:09Z<p>Nastya: </p>
<hr />
<div>Данная операция позволяет выполнять запросы на [[Дерево отрезков. Построение|дереве отрезков]], причем алгоритм запускается от корня и рекурсивно идет сверху вниз.<br />
<br />
==Алгоритм==<br />
''Замечание.''<br />
Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая {{---}} нет).<br />
<br />
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на полуинтервале <tex>[a .. b)</tex>.<br />
<br />
В качестве параметров рекурсий передаем следующие переменные:<br />
* <tex>node</tex> {{---}} номер (в массиве с деревом отрезков) текущей вершины дерева.<br />
* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого полуинтервала.<br />
<br />
Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы полуинтервала, за которые "отвечает" наша вершина.<br />
Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).<br />
<br />
Для текущего состояния проверяем следующие условия :<br />
<br />
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.<br />
:''Например'': текущий <tex>[1..3)</tex>, а искомый <tex>[3 .. 5)</tex>;<br />
<br />
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.<br />
:''Например'': текущий <tex>[2..3)</tex>, а искомый <tex>[2..4)</tex>;<br />
<br />
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.<br />
<br />
Так как на каждом уровне дерева рекурсия может дойти до не более, чем двух вершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок, за который отвечает вершина предыдущего уровня), а всего уровней <tex>\log n</tex>, то операция выполняется за <tex>O(\log n)</tex>.<br />
<br />
==Пример==<br />
<br />
Рассмотрим данный алгоритм на примере задачи RSQ (Range Sum Query {{---}} запрос суммы на отрезке).<br />
<br />
При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях.<br />
<br />
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма <br />
{{---}} это отрезок <tex>[1 .. 4]</tex> (полуинтервал <tex>[1 .. 5)</tex>).<br />
[[Файл:Image_4.png|right|602px|Пример рабoты алгоритма]]<br />
Рассмотрим данный алгоритм на определенных глубинах рекурсии (то есть на разных уровнях дерева):<br />
<br />
* На глубине <tex>0</tex>. (на рисунке глубина обозначена слева от уровня). Текущий полуинтервал <tex>[0 .. 8)</tex> пересекается с <tex>[1 .. 5) \Rightarrow</tex> переходим по рекурсивным вызовам на <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине <tex>1</tex>. <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex> пересекаются с <tex> [1 .. 5) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex>[0 ..<br />
2)</tex>, <tex>[2 .. 4)</tex>, <tex>[4 .. 6)</tex> и <tex>[6 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине <tex>2</tex>. <br />
** <tex>[0 .. 2)</tex> и <tex>[4 .. 6)</tex> пересекаются с <tex>[1 .. 5) \Rightarrow </tex> переходим в листья <tex>0, 1, 4, 5 </tex><br />
** <tex>[2 .. 4) </tex> полностью лежит внутри <tex>[1 .. 5) \Rightarrow </tex> возвращаем сумму на этом отрезке<br />
** <tex>[6 .. 8)</tex> не пересекается с <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
<br />
<br />
* На глубине <tex>3</tex>. <br />
** Листья <tex>1, 4</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них<br />
** Листья <tex>0, 5</tex> лежат вне <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
Таким образом ответ на полуинтервале <tex>[1 .. 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 .. 2)</tex>, <tex>[2 .. 4)</tex> и <tex>[4 .. 5)</tex>.<br />
<br />
==Реализация==<br />
Рассмотрим реализацию задачи RSQ.<br />
<br />
Пусть в узлах дерева хранятся структуры из трех полей:<br />
* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.<br />
* <tex>right</tex> {{---}} правая граница этого полуинтервала.<br />
* <tex> sum</tex> {{---}} сумма на полуинтервале.<br />
<br />
<code><br />
<br />
'''int''' get_sum ('''int''' node, '''int''' a, '''int''' b) <br />
l = tree[node].left<br />
r = tree[node].right <br />
'''if''' [l, r) <tex>\cap </tex> [a, b) == <tex> \varnothing</tex><br />
'''return''' 0<br />
'''if''' [l, r) <tex>\subset</tex> [a, b)<br />
'''return''' tree[node].sum<br />
'''return''' get_sum (node * 2 + 1, a, b) + get_sum (node * 2 + 2, a, b)<br />
</code><br />
<br />
==См. также==<br />
* [[Реализация запроса в дереве отрезков снизу]]<br />
<br />
==Источники информации==<br />
* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]<br />
* [http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Дерево отрезков — Википедия]<br />
<br />
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор дерева отрезков]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Дерево отрезков]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%BD%D0%B8%D0%B7%D1%83&diff=38998Реализация запроса в дереве отрезков снизу2014-06-13T11:39:50Z<p>Nastya: </p>
<hr />
<div>==Алгоритм==<br />
<br />
Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее <tex>a \circ b</tex>.<br />
<br />
[[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:<br />
# Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Аналогично с правой границей (является ли она левым сыном). Таким образом мы учтем вклад нужной нам вершины и избавимся от вклада ненужного нам поддерева. <br />
# Устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Повторяем этап 1, пока границы не пересекутся.<br />
# Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат.<br />
<br />
{| cellpadding="10"<br />
| '''Реализация запроса снизу вверх''' || '''Ещё один пример'''<br />
|-<br />
| [[Файл:Запрос снизу №1х1.jpg|550px|]] || [[Файл:Запрос снизу №2х1.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х2.jpg|550px|]] || [[Файл:Запрос снизу №2х2.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х3.jpg|550px|]] || [[Файл:Запрос снизу №2х3.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х4.jpg|550px|]] || [[Файл:Запрос снизу №2х4.jpg|550px]]<br />
|}<br />
<br />
==Псевдокод==<br />
<br />
Пусть результат считаем на отрезке <tex> [left, right] </tex>. При этом значения <tex>left</tex> и <tex>right</tex>, передающиеся в функцию, должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья). Переменные <tex>leftRes</tex> и <tex>rightRes</tex> будут собирать значения на отрезках, отделившихся соответственно слева или справа от рассматриваемого. <br />
<br />
'''int''' query(left : '''int''', right : '''int'''):<br />
leftRes = ''neutral''<br />
rightRes = ''neutral''<br />
'''while''' left < right<br />
'''if''' left '''mod''' 2 == 0<br />
leftRes = leftRes <tex> \circ </tex> data[left]<br />
left = left '''div''' 2 <br />
'''if''' right '''mod''' 2 == 1<br />
rightRes = data[right] <tex> \circ </tex> rightRes<br />
right = (right - 1) '''div''' 2<br />
'''if''' left == right <br />
leftRes = leftRes <tex> \circ </tex> data[left]<br />
'''return''' leftRes <tex> \circ </tex> rightRes<br />
<br />
==См. также==<br />
* [[Реализация запроса в дереве отрезков сверху]]<br />
<br />
==Источники информации==<br />
<br />
* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]<br />
<br />
* [http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Википедия {{---}} Дерево отрезков]<br />
<br />
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор]<br />
<br />
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006/algorithm Алгоритм]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Дерево отрезков]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%BD%D0%B8%D0%B7%D1%83&diff=38997Реализация запроса в дереве отрезков снизу2014-06-13T11:38:08Z<p>Nastya: /* Псевдокод */</p>
<hr />
<div>==Алгоритм==<br />
<br />
Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее <tex>a \circ b</tex>.<br />
<br />
[[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:<br />
# Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Аналогично с правой границей (является ли она левым сыном). Таким образом мы учтем вклад нужной нам вершины и избавимся от вклада ненужного нам поддерева. <br />
# Устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Повторяем этап 1, пока границы не пересекутся.<br />
# Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат.<br />
<br />
{| cellpadding="10"<br />
| '''Реализация запроса снизу вверх''' || '''Ещё один пример'''<br />
|-<br />
| [[Файл:Запрос снизу №1х1.jpg|550px|]] || [[Файл:Запрос снизу №2х1.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х2.jpg|550px|]] || [[Файл:Запрос снизу №2х2.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х3.jpg|550px|]] || [[Файл:Запрос снизу №2х3.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х4.jpg|550px|]] || [[Файл:Запрос снизу №2х4.jpg|550px]]<br />
|}<br />
<br />
==Псевдокод==<br />
<br />
Пусть результат считаем на отрезке <tex> [left, right] </tex>. При этом значения <tex>left</tex> и <tex>right</tex>, передающиеся в функцию, должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья). Переменные <tex>leftRes</tex> и <tex>rightRes</tex> будут собирать значения на отрезках, отделившихся соответственно слева или справа от рассматриваемого. <br />
<br />
'''int''' query(left : '''int''', right : '''int'''):<br />
leftRes = ''neutral''<br />
rightRes = ''neutral''<br />
'''while''' left < right<br />
'''if''' left '''mod''' 2 == 0<br />
leftRes = leftRes <tex> \circ </tex> data[left]<br />
left = left '''div''' 2 <br />
'''if''' right '''mod''' 2 == 1<br />
rightRes = data[right] <tex> \circ </tex> rightRes<br />
right = (right - 1) '''div''' 2<br />
'''if''' left == right <br />
leftRes = leftRes <tex> \circ </tex> data[left]<br />
'''return''' leftRes <tex> \circ </tex> rightRes<br />
<br />
==Источники информации==<br />
<br />
* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]<br />
<br />
* [http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Википедия {{---}} Дерево отрезков]<br />
<br />
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор]<br />
<br />
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006/algorithm Алгоритм]<br />
<br />
==См. также==<br />
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%B2%D0%B5%D1%80%D1%85%D1%83 Реализация запроса в дереве отрезков сверху]<br />
<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Дерево отрезков]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%BD%D0%B8%D0%B7%D1%83&diff=38975Реализация запроса в дереве отрезков снизу2014-06-13T08:34:10Z<p>Nastya: </p>
<hr />
<div>==Алгоритм==<br />
<br />
Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее <tex>a \circ b</tex>.<br />
<br />
[[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:<br />
# Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Аналогично с правой границей (является ли она левым сыном). Таким образом мы учтем вклад нужной нам вершины и избавимся от вклада ненужного нам поддерева. <br />
# Устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Повторяем этап 1, пока границы не пересекутся.<br />
# Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат.<br />
<br />
{| cellpadding="10"<br />
| '''Реализация запроса снизу вверх''' || '''Ещё один пример'''<br />
|-<br />
| [[Файл:Запрос снизу №1х1.jpg|550px|]] || [[Файл:Запрос снизу №2х1.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х2.jpg|550px|]] || [[Файл:Запрос снизу №2х2.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х3.jpg|550px|]] || [[Файл:Запрос снизу №2х3.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х4.jpg|550px|]] || [[Файл:Запрос снизу №2х4.jpg|550px]]<br />
|}<br />
<br />
==Псевдокод==<br />
<br />
Пусть результат считаем на отрезке [<tex> left, right </tex>]. При этом значения <tex>left</tex> и <tex>right</tex>, передающиеся в функцию, должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья). Переменные <tex>leftRes</tex> и <tex>rightRes</tex> будут собирать значения на отрезках, отделившихся соответственно слева или справа от рассматриваемого. <br />
<br />
'''int''' query(left : '''int''', right : '''int'''):<br />
leftRes = ''neutral''<br />
rightRes = ''neutral''<br />
'''while''' left < right<br />
'''if''' left '''mod''' 2 == 0<br />
leftRes = leftRes <tex> \circ </tex> data[left]<br />
left = left '''div''' 2 <br />
'''if''' right '''mod''' 2 == 1<br />
rightRes = data[right] <tex> \circ </tex> rightRes<br />
right = (right - 1) '''div''' 2<br />
'''if''' left == right <br />
leftRes = leftRes <tex> \circ </tex> data[left]<br />
'''return''' leftRes <tex> \circ </tex> rightRes<br />
<br />
==Источники информации==<br />
<br />
* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]<br />
<br />
* [http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Википедия {{---}} Дерево отрезков]<br />
<br />
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор]<br />
<br />
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006/algorithm Алгоритм]<br />
<br />
==См. также==<br />
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%B2%D0%B5%D1%80%D1%85%D1%83 Реализация запроса в дереве отрезков сверху]<br />
<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Дерево отрезков]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:%D0%97%D0%B0%D0%BF%D1%80%D0%BE%D1%81_%D1%81%D0%BD%D0%B8%D0%B7%D1%83_%E2%84%962%D1%854.jpg&diff=38973Файл:Запрос снизу №2х4.jpg2014-06-13T08:27:42Z<p>Nastya: загружена новая версия «Файл:Запрос снизу №2х4.jpg»</p>
<hr />
<div></div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:%D0%97%D0%B0%D0%BF%D1%80%D0%BE%D1%81_%D1%81%D0%BD%D0%B8%D0%B7%D1%83_%E2%84%961%D1%854.jpg&diff=38972Файл:Запрос снизу №1х4.jpg2014-06-13T08:26:34Z<p>Nastya: загружена новая версия «Файл:Запрос снизу №1х4.jpg»</p>
<hr />
<div></div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:%D0%97%D0%B0%D0%BF%D1%80%D0%BE%D1%81_%D1%81%D0%BD%D0%B8%D0%B7%D1%83_%E2%84%962%D1%853.jpg&diff=38971Файл:Запрос снизу №2х3.jpg2014-06-13T08:25:12Z<p>Nastya: загружена новая версия «Файл:Запрос снизу №2х3.jpg»</p>
<hr />
<div></div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:%D0%97%D0%B0%D0%BF%D1%80%D0%BE%D1%81_%D1%81%D0%BD%D0%B8%D0%B7%D1%83_%E2%84%961%D1%853.jpg&diff=38970Файл:Запрос снизу №1х3.jpg2014-06-13T08:23:50Z<p>Nastya: загружена новая версия «Файл:Запрос снизу №1х3.jpg»</p>
<hr />
<div></div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:%D0%97%D0%B0%D0%BF%D1%80%D0%BE%D1%81_%D1%81%D0%BD%D0%B8%D0%B7%D1%83_%E2%84%962%D1%852.jpg&diff=38969Файл:Запрос снизу №2х2.jpg2014-06-13T08:22:29Z<p>Nastya: загружена новая версия «Файл:Запрос снизу №2х2.jpg»</p>
<hr />
<div></div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:%D0%97%D0%B0%D0%BF%D1%80%D0%BE%D1%81_%D1%81%D0%BD%D0%B8%D0%B7%D1%83_%E2%84%961%D1%852.jpg&diff=38968Файл:Запрос снизу №1х2.jpg2014-06-13T08:20:40Z<p>Nastya: загружена новая версия «Файл:Запрос снизу №1х2.jpg»</p>
<hr />
<div></div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:%D0%97%D0%B0%D0%BF%D1%80%D0%BE%D1%81_%D1%81%D0%BD%D0%B8%D0%B7%D1%83_%E2%84%962%D1%851.jpg&diff=38967Файл:Запрос снизу №2х1.jpg2014-06-13T08:17:06Z<p>Nastya: загружена новая версия «Файл:Запрос снизу №2х1.jpg»</p>
<hr />
<div></div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:%D0%97%D0%B0%D0%BF%D1%80%D0%BE%D1%81_%D1%81%D0%BD%D0%B8%D0%B7%D1%83_%E2%84%961%D1%851.jpg&diff=38966Файл:Запрос снизу №1х1.jpg2014-06-13T08:14:06Z<p>Nastya: загружена новая версия «Файл:Запрос снизу №1х1.jpg»</p>
<hr />
<div></div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:%D0%97%D0%B0%D0%BF%D1%80%D0%BE%D1%81_%D1%81%D0%BD%D0%B8%D0%B7%D1%83_%E2%84%961%D1%851.jpg&diff=38965Файл:Запрос снизу №1х1.jpg2014-06-13T07:56:15Z<p>Nastya: загружена новая версия «Файл:Запрос снизу №1х1.jpg»</p>
<hr />
<div></div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%BD%D0%B8%D0%B7%D1%83&diff=38964Реализация запроса в дереве отрезков снизу2014-06-13T07:49:34Z<p>Nastya: /* Псевдокод */</p>
<hr />
<div>==Алгоритм==<br />
<br />
Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее <tex>a \circ b</tex>.<br />
<br />
[[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:<br />
# Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Аналогично с правой границей (является ли она левым сыном). Таким образом мы учтем вклад нужной нам вершины и избавимся от вклада ненужного нам поддерева. <br />
# Устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Повторяем этап 1, пока границы не пересекутся.<br />
# Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат.<br />
<br />
{| cellpadding="10"<br />
| '''Реализация запроса снизу вверх''' || '''Ещё один пример'''<br />
|-<br />
| [[Файл:Запрос снизу №1х1.jpg|550px|]] || [[Файл:Запрос снизу №2х1.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х2.jpg|550px|]] || [[Файл:Запрос снизу №2х2.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х3.jpg|550px|]] || [[Файл:Запрос снизу №2х3.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х4.jpg|550px|]] || [[Файл:Запрос снизу №2х4.jpg|550px]]<br />
|}<br />
<br />
==Псевдокод==<br />
<br />
Пусть результат считаем на отрезке [<tex> left, right </tex>]. При этом значения <tex>left</tex> и <tex>right</tex>, передающиеся в функцию, должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья). Переменные <tex>leftRes</tex> и <tex>rightRes</tex> будут собирать значения на отрезках, отделившихся соответственно слева или справа от рассматриваемого. <br />
<br />
'''int''' query(left : '''int''', right : '''int'''):<br />
leftRes = ''neutral''<br />
rightRes = ''neutral''<br />
'''while''' left < right<br />
'''if''' left '''mod''' 2 == 0<br />
leftRes = leftRes <tex> \circ </tex> data[left]<br />
left = left '''div''' 2 <br />
'''if''' right '''mod''' 2 == 1<br />
rightRes = data[right] <tex> \circ </tex> rightRes<br />
right = (right - 1) '''div''' 2<br />
'''if''' left == right <br />
leftRes = leftRes <tex> \circ </tex> data[left]<br />
'''return''' leftRes <tex> \circ </tex> rightRes<br />
<br />
==Ссылки==<br />
<br />
[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]<br />
<br />
[http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Википедия {{---}} Дерево отрезков]<br />
<br />
[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор]<br />
<br />
[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006/algorithm Алгоритм]<br />
<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Дерево отрезков]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%BD%D0%B8%D0%B7%D1%83&diff=38963Реализация запроса в дереве отрезков снизу2014-06-13T07:45:46Z<p>Nastya: </p>
<hr />
<div>==Алгоритм==<br />
<br />
Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее <tex>a \circ b</tex>.<br />
<br />
[[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:<br />
# Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Аналогично с правой границей (является ли она левым сыном). Таким образом мы учтем вклад нужной нам вершины и избавимся от вклада ненужного нам поддерева. <br />
# Устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Повторяем этап 1, пока границы не пересекутся.<br />
# Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат.<br />
<br />
{| cellpadding="10"<br />
| '''Реализация запроса снизу вверх''' || '''Ещё один пример'''<br />
|-<br />
| [[Файл:Запрос снизу №1х1.jpg|550px|]] || [[Файл:Запрос снизу №2х1.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х2.jpg|550px|]] || [[Файл:Запрос снизу №2х2.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х3.jpg|550px|]] || [[Файл:Запрос снизу №2х3.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х4.jpg|550px|]] || [[Файл:Запрос снизу №2х4.jpg|550px]]<br />
|}<br />
<br />
==Псевдокод==<br />
<br />
Пусть результат считаем на отрезке [<tex> left, right </tex>]. При этом значения <tex>left</tex> и <tex>right</tex>, передающиеся в функцию, должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья). Переменные <tex>left</tex>_<tex>res</tex> и <tex>right</tex>_<tex>res</tex> будут собирать значения на отрезках, отделившихся соответственно слева или справа от рассматриваемого. <br />
<br />
'''int''' query(left : '''int''', right : '''int'''):<br />
left_res = ''neutral''<br />
right_res = ''neutral''<br />
'''while''' left < right<br />
'''if''' left '''mod''' 2 == 0<br />
left_res = left_res <tex> \circ </tex> data[left]<br />
left = left '''div''' 2 <br />
'''if''' right '''mod''' 2 == 1<br />
right_res = data[right] <tex> \circ </tex> right_res<br />
right = (right - 1) '''div''' 2<br />
'''if''' left == right <br />
left_res = left_res <tex> \circ </tex> data[left]<br />
'''return''' left_res <tex> \circ </tex> right_res<br />
<br />
==Ссылки==<br />
<br />
[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]<br />
<br />
[http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Википедия {{---}} Дерево отрезков]<br />
<br />
[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор]<br />
<br />
[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006/algorithm Алгоритм]<br />
<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Дерево отрезков]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%BD%D0%B8%D0%B7%D1%83&diff=38962Реализация запроса в дереве отрезков снизу2014-06-13T07:41:57Z<p>Nastya: /* Псевдокод */</p>
<hr />
<div>==Алгоритм==<br />
<br />
Реализация запроса снизу вверх в дереве отрезков является, в отличие от [[Реализация запроса в дереве отрезков сверху| реализации запроса сверху вниз]], итеративным методом. Будем рассматривать абстрактную операцию, обладающую свойством ассоциативности, и обозначать ее a <tex> \circ </tex> b.<br />
<br />
[[Дерево отрезков. Построение|Построим дерево отрезков]] и установим границы отрезка на соответствующие им листья. Будем действовать в 3 этапа:<br />
# Если элемент, попавший на левую границу, является правым сыном, то запишем в результат значение, полученное после выполнения нашей операции над предыдущим результатом и значением этого элемента, а левую границу перемещаем на один элемент вправо. Аналогично с правой границей (является ли она левым сыном). Таким образом мы учтем вклад нужной нам вершины и избавимся от вклада ненужного нам поддерева. <br />
# Устанавливаем границы отрезка на родительские элементы текущих границ. Это позволит узнать, входит ли полученный отрезок в искомый или нет. Повторяем этап 1, пока границы не пересекутся.<br />
# Если после завершения цикла границы совпадут, значит полученный отрезок входит в искомый, и надо пересчитать результат.<br />
<br />
{| cellpadding="10"<br />
| '''Реализация запроса снизу вверх''' || '''Ещё один пример'''<br />
|-<br />
| [[Файл:Запрос снизу №1х1.jpg|550px|]] || [[Файл:Запрос снизу №2х1.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х2.jpg|550px|]] || [[Файл:Запрос снизу №2х2.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х3.jpg|550px|]] || [[Файл:Запрос снизу №2х3.jpg|550px]]<br />
|-<br />
| [[Файл:Запрос снизу №1х4.jpg|550px|]] || [[Файл:Запрос снизу №2х4.jpg|550px]]<br />
|}<br />
<br />
==Псевдокод==<br />
<br />
Пусть результат считаем на отрезке [left, right]. При этом значения left и right, передающиеся в функцию, должны указывать на листья дерева (необходимо увеличить значение на индекс массива, с которого начинаются листья). Переменные left_res и right_res будут собирать значения на отрезках, отделившихся соответственно слева или справа от рассматриваемого. <br />
<br />
'''int''' query(left : '''int''', right : '''int'''):<br />
left_res = ''neutral''<br />
right_res = ''neutral''<br />
'''while''' left < right<br />
'''if''' left '''mod''' 2 == 0<br />
left_res = left_res <tex> \circ </tex> data[left]<br />
left = left '''div''' 2 <br />
'''if''' right '''mod''' 2 == 1<br />
right_res = data[right] <tex> \circ </tex> right_res<br />
right = (right - 1) '''div''' 2<br />
'''if''' left == right <br />
left_res = left_res <tex> \circ </tex> data[left]<br />
'''return''' left_res <tex> \circ </tex> right_res<br />
<br />
==Ссылки==<br />
<br />
[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]<br />
<br />
[http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Википедия {{---}} Дерево отрезков]<br />
<br />
[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор]<br />
<br />
[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006/algorithm Алгоритм]<br />
<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Дерево отрезков]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%B2%D0%B5%D1%80%D1%85%D1%83&diff=38961Реализация запроса в дереве отрезков сверху2014-06-13T07:31:17Z<p>Nastya: /* Смотри также */</p>
<hr />
<div>Данная операция позволяет выполнять запросы на [[Дерево отрезков. Построение|дереве отрезков]], причем алгоритм запускается от корня и рекурсивно идет сверху вниз.<br />
<br />
==Алгоритм==<br />
''Замечание.''<br />
Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая {{---}} нет).<br />
<br />
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на полуинтервале <tex>[a .. b)</tex>.<br />
<br />
В качестве параметров рекурсий передаем следующие переменные:<br />
* <tex>node</tex> {{---}} номер (в массиве с деревом отрезков) текущей вершины дерева.<br />
* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого полуинтервала.<br />
<br />
Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы полуинтервала, за которые "отвечает" наша вершина.<br />
Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).<br />
<br />
Для текущего состояния проверяем следующие условия :<br />
<br />
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.<br />
:''Например'': текущий <tex>[1..3)</tex>, а искомый <tex>[3 .. 5)</tex>;<br />
<br />
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.<br />
:''Например'': текущий <tex>[2..3)</tex>, а искомый <tex>[2..4)</tex>;<br />
<br />
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.<br />
<br />
Так как на каждом уровне дерева рекурсия может дойти до не более, чем двух вершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок, за который отвечает вершина предыдущего уровня), а всего уровней <tex>\log n</tex>, то операция выполняется за <tex>O(\log n)</tex>.<br />
<br />
==Пример==<br />
<br />
Рассмотрим данный алгоритм на примере задачи RSQ (Range Sum Query {{---}} запрос суммы на отрезке).<br />
<br />
При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях.<br />
<br />
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма <br />
{{---}} это отрезок <tex>[1 .. 4]</tex> (полуинтервал <tex>[1 .. 5)</tex>).<br />
[[Файл:Image_4.png|right|602px|Пример рабoты алгоритма]]<br />
Рассмотрим данный алгоритм на определенных глубинах рекурсии (то есть на разных уровнях дерева):<br />
<br />
* На глубине 0. (на рисунке глубина обозначена слева от уровня). Текущий полуинтервал <tex>[0 .. 8)</tex> пересекается с <tex>[1 .. 5) \Rightarrow</tex> переходим по рекурсивным вызовам на <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине 1. <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex> пересекаются с <tex> [1 .. 5) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex>[0 ..<br />
2)</tex>, <tex>[2 .. 4)</tex>, <tex>[4 .. 6)</tex> и <tex>[6 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине 2. <br />
** <tex>[0 .. 2)</tex> и <tex>[4 .. 6)</tex> пересекаются с <tex>[1 .. 5) \Rightarrow </tex> переходим в листья <tex>0, 1, 4, 5 </tex><br />
** <tex>[2 .. 4) </tex> полностью лежит внутри <tex>[1 .. 5) \Rightarrow </tex> возвращаем сумму на этом отрезке<br />
** <tex>[6 .. 8)</tex> не пересекается с <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
<br />
<br />
* На глубине 3. <br />
** Листья <tex>1, 4</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них<br />
** Листья <tex>0, 5</tex> лежат вне <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
Таким образом ответ на полуинтервале <tex>[1 .. 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 .. 2)</tex>, <tex>[2 .. 4)</tex> и <tex>[4 .. 5)</tex>.<br />
<br />
==Реализация==<br />
Рассмотрим реализацию задачи RSQ.<br />
<br />
Пусть в узлах дерева хранятся структуры из трех полей:<br />
* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.<br />
* <tex>right</tex> {{---}} правая граница этого полуинтервала.<br />
* <tex> sum</tex> {{---}} сумма на полуинтервале.<br />
<br />
<code><br />
<br />
'''int''' get_sum ('''int''' node, '''int''' a, '''int''' b) <br />
l = tree[node].left<br />
r = tree[node].right <br />
'''if''' [l, r) <tex>\cap </tex> [a, b) == <tex> \varnothing</tex><br />
'''return''' 0<br />
'''if''' [l, r) <tex>\subset</tex> [a, b)<br />
'''return''' tree[node].sum<br />
'''return''' get_sum (node * 2 + 1, a, b) + get_sum (node * 2 + 2, a, b)<br />
</code><br />
<br />
==Источники информации==<br />
<br />
* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]<br />
<br />
* [http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Дерево отрезков — Википедия]<br />
<br />
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор дерева отрезков]<br />
<br />
==См. также==<br />
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%BD%D0%B8%D0%B7%D1%83 Реализация запроса в дереве отрезков снизу]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Дерево отрезков]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%B2%D0%B5%D1%80%D1%85%D1%83&diff=38960Реализация запроса в дереве отрезков сверху2014-06-13T07:30:49Z<p>Nastya: </p>
<hr />
<div>Данная операция позволяет выполнять запросы на [[Дерево отрезков. Построение|дереве отрезков]], причем алгоритм запускается от корня и рекурсивно идет сверху вниз.<br />
<br />
==Алгоритм==<br />
''Замечание.''<br />
Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая {{---}} нет).<br />
<br />
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на полуинтервале <tex>[a .. b)</tex>.<br />
<br />
В качестве параметров рекурсий передаем следующие переменные:<br />
* <tex>node</tex> {{---}} номер (в массиве с деревом отрезков) текущей вершины дерева.<br />
* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого полуинтервала.<br />
<br />
Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы полуинтервала, за которые "отвечает" наша вершина.<br />
Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).<br />
<br />
Для текущего состояния проверяем следующие условия :<br />
<br />
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.<br />
:''Например'': текущий <tex>[1..3)</tex>, а искомый <tex>[3 .. 5)</tex>;<br />
<br />
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.<br />
:''Например'': текущий <tex>[2..3)</tex>, а искомый <tex>[2..4)</tex>;<br />
<br />
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.<br />
<br />
Так как на каждом уровне дерева рекурсия может дойти до не более, чем двух вершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок, за который отвечает вершина предыдущего уровня), а всего уровней <tex>\log n</tex>, то операция выполняется за <tex>O(\log n)</tex>.<br />
<br />
==Пример==<br />
<br />
Рассмотрим данный алгоритм на примере задачи RSQ (Range Sum Query {{---}} запрос суммы на отрезке).<br />
<br />
При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях.<br />
<br />
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма <br />
{{---}} это отрезок <tex>[1 .. 4]</tex> (полуинтервал <tex>[1 .. 5)</tex>).<br />
[[Файл:Image_4.png|right|602px|Пример рабoты алгоритма]]<br />
Рассмотрим данный алгоритм на определенных глубинах рекурсии (то есть на разных уровнях дерева):<br />
<br />
* На глубине 0. (на рисунке глубина обозначена слева от уровня). Текущий полуинтервал <tex>[0 .. 8)</tex> пересекается с <tex>[1 .. 5) \Rightarrow</tex> переходим по рекурсивным вызовам на <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине 1. <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex> пересекаются с <tex> [1 .. 5) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex>[0 ..<br />
2)</tex>, <tex>[2 .. 4)</tex>, <tex>[4 .. 6)</tex> и <tex>[6 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине 2. <br />
** <tex>[0 .. 2)</tex> и <tex>[4 .. 6)</tex> пересекаются с <tex>[1 .. 5) \Rightarrow </tex> переходим в листья <tex>0, 1, 4, 5 </tex><br />
** <tex>[2 .. 4) </tex> полностью лежит внутри <tex>[1 .. 5) \Rightarrow </tex> возвращаем сумму на этом отрезке<br />
** <tex>[6 .. 8)</tex> не пересекается с <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
<br />
<br />
* На глубине 3. <br />
** Листья <tex>1, 4</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них<br />
** Листья <tex>0, 5</tex> лежат вне <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
Таким образом ответ на полуинтервале <tex>[1 .. 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 .. 2)</tex>, <tex>[2 .. 4)</tex> и <tex>[4 .. 5)</tex>.<br />
<br />
==Реализация==<br />
Рассмотрим реализацию задачи RSQ.<br />
<br />
Пусть в узлах дерева хранятся структуры из трех полей:<br />
* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.<br />
* <tex>right</tex> {{---}} правая граница этого полуинтервала.<br />
* <tex> sum</tex> {{---}} сумма на полуинтервале.<br />
<br />
<code><br />
<br />
'''int''' get_sum ('''int''' node, '''int''' a, '''int''' b) <br />
l = tree[node].left<br />
r = tree[node].right <br />
'''if''' [l, r) <tex>\cap </tex> [a, b) == <tex> \varnothing</tex><br />
'''return''' 0<br />
'''if''' [l, r) <tex>\subset</tex> [a, b)<br />
'''return''' tree[node].sum<br />
'''return''' get_sum (node * 2 + 1, a, b) + get_sum (node * 2 + 2, a, b)<br />
</code><br />
<br />
==Источники информации==<br />
<br />
* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]<br />
<br />
* [http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Дерево отрезков — Википедия]<br />
<br />
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор дерева отрезков]<br />
<br />
==Смотри также==<br />
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%BD%D0%B8%D0%B7%D1%83 Реализация запроса в дереве отрезков снизу]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Дерево отрезков]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%B2%D0%B5%D1%80%D1%85%D1%83&diff=38959Реализация запроса в дереве отрезков сверху2014-06-13T07:28:20Z<p>Nastya: /* Ссылки */</p>
<hr />
<div>Данная операция позволяет выполнять запросы на [[Дерево отрезков. Построение|дереве отрезков]], причем алгоритм запускается от корня и рекурсивно идет сверху вниз.<br />
<br />
==Алгоритм==<br />
''Замечание.''<br />
Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая {{---}} нет).<br />
<br />
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на полуинтервале <tex>[a .. b)</tex>.<br />
<br />
В качестве параметров рекурсий передаем следующие переменные:<br />
* <tex>node</tex> {{---}} номер (в массиве с деревом отрезков) текущей вершины дерева.<br />
* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого полуинтервала.<br />
<br />
Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы полуинтервала, за которые "отвечает" наша вершина.<br />
Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).<br />
<br />
Для текущего состояния проверяем следующие условия :<br />
<br />
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.<br />
:''Например'': текущий <tex>[1..3)</tex>, а искомый <tex>[3 .. 5)</tex>;<br />
<br />
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.<br />
:''Например'': текущий <tex>[2..3)</tex>, а искомый <tex>[2..4)</tex>;<br />
<br />
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.<br />
<br />
Так как на каждом уровне дерева рекурсия может дойти до не более, чем двух вершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок, за который отвечает вершина предыдущего уровня), а всего уровней <tex>\log n</tex>, то операция выполняется за <tex>O(\log n)</tex>.<br />
<br />
==Пример==<br />
<br />
Рассмотрим данный алгоритм на примере задачи RSQ (Range Sum Query {{---}} запрос суммы на отрезке).<br />
<br />
При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях.<br />
<br />
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма <br />
{{---}} это отрезок <tex>[1 .. 4]</tex> (полуинтервал <tex>[1 .. 5)</tex>).<br />
[[Файл:Image_4.png|right|602px|Пример рабoты алгоритма]]<br />
Рассмотрим данный алгоритм на определенных глубинах рекурсии (то есть на разных уровнях дерева):<br />
<br />
* На глубине 0. (на рисунке глубина обозначена слева от уровня). Текущий полуинтервал <tex>[0 .. 8)</tex> пересекается с <tex>[1 .. 5) \Rightarrow</tex> переходим по рекурсивным вызовам на <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине 1. <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex> пересекаются с <tex> [1 .. 5) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex>[0 ..<br />
2)</tex>, <tex>[2 .. 4)</tex>, <tex>[4 .. 6)</tex> и <tex>[6 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине 2. <br />
** <tex>[0 .. 2)</tex> и <tex>[4 .. 6)</tex> пересекаются с <tex>[1 .. 5) \Rightarrow </tex> переходим в листья <tex>0, 1, 4, 5 </tex><br />
** <tex>[2 .. 4) </tex> полностью лежит внутри <tex>[1 .. 5) \Rightarrow </tex> возвращаем сумму на этом отрезке<br />
** <tex>[6 .. 8)</tex> не пересекается с <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
<br />
<br />
* На глубине 3. <br />
** Листья <tex>1, 4</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них<br />
** Листья <tex>0, 5</tex> лежат вне <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
Таким образом ответ на полуинтервале <tex>[1 .. 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 .. 2)</tex>, <tex>[2 .. 4)</tex> и <tex>[4 .. 5)</tex>.<br />
<br />
==Реализация==<br />
Рассмотрим реализацию задачи RSQ.<br />
<br />
Пусть в узлах дерева хранятся структуры из трех полей:<br />
* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.<br />
* <tex>right</tex> {{---}} правая граница этого полуинтервала.<br />
* <tex> sum</tex> {{---}} сумма на полуинтервале.<br />
<br />
<code><br />
<br />
'''int''' get_sum ('''int''' node, '''int''' a, '''int''' b) <br />
l = tree[node].left<br />
r = tree[node].right <br />
'''if''' [l, r) <tex>\cap </tex> [a, b) == <tex> \varnothing</tex><br />
'''return''' 0<br />
'''if''' [l, r) <tex>\subset</tex> [a, b)<br />
'''return''' tree[node].sum<br />
'''return''' get_sum (node * 2 + 1, a, b) + get_sum (node * 2 + 2, a, b)<br />
</code><br />
<br />
==Источники информации==<br />
<br />
* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]<br />
<br />
* [http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Дерево отрезков — Википедия]<br />
<br />
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор дерева отрезков]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Дерево отрезков]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%B2%D0%B5%D1%80%D1%85%D1%83&diff=38958Реализация запроса в дереве отрезков сверху2014-06-13T07:26:22Z<p>Nastya: </p>
<hr />
<div>Данная операция позволяет выполнять запросы на [[Дерево отрезков. Построение|дереве отрезков]], причем алгоритм запускается от корня и рекурсивно идет сверху вниз.<br />
<br />
==Алгоритм==<br />
''Замечание.''<br />
Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая {{---}} нет).<br />
<br />
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на полуинтервале <tex>[a .. b)</tex>.<br />
<br />
В качестве параметров рекурсий передаем следующие переменные:<br />
* <tex>node</tex> {{---}} номер (в массиве с деревом отрезков) текущей вершины дерева.<br />
* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого полуинтервала.<br />
<br />
Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы полуинтервала, за которые "отвечает" наша вершина.<br />
Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).<br />
<br />
Для текущего состояния проверяем следующие условия :<br />
<br />
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.<br />
:''Например'': текущий <tex>[1..3)</tex>, а искомый <tex>[3 .. 5)</tex>;<br />
<br />
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.<br />
:''Например'': текущий <tex>[2..3)</tex>, а искомый <tex>[2..4)</tex>;<br />
<br />
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.<br />
<br />
Так как на каждом уровне дерева рекурсия может дойти до не более, чем двух вершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок, за который отвечает вершина предыдущего уровня), а всего уровней <tex>\log n</tex>, то операция выполняется за <tex>O(\log n)</tex>.<br />
<br />
==Пример==<br />
<br />
Рассмотрим данный алгоритм на примере задачи RSQ (Range Sum Query {{---}} запрос суммы на отрезке).<br />
<br />
При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях.<br />
<br />
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма <br />
{{---}} это отрезок <tex>[1 .. 4]</tex> (полуинтервал <tex>[1 .. 5)</tex>).<br />
[[Файл:Image_4.png|right|602px|Пример рабoты алгоритма]]<br />
Рассмотрим данный алгоритм на определенных глубинах рекурсии (то есть на разных уровнях дерева):<br />
<br />
* На глубине 0. (на рисунке глубина обозначена слева от уровня). Текущий полуинтервал <tex>[0 .. 8)</tex> пересекается с <tex>[1 .. 5) \Rightarrow</tex> переходим по рекурсивным вызовам на <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине 1. <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex> пересекаются с <tex> [1 .. 5) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex>[0 ..<br />
2)</tex>, <tex>[2 .. 4)</tex>, <tex>[4 .. 6)</tex> и <tex>[6 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине 2. <br />
** <tex>[0 .. 2)</tex> и <tex>[4 .. 6)</tex> пересекаются с <tex>[1 .. 5) \Rightarrow </tex> переходим в листья <tex>0, 1, 4, 5 </tex><br />
** <tex>[2 .. 4) </tex> полностью лежит внутри <tex>[1 .. 5) \Rightarrow </tex> возвращаем сумму на этом отрезке<br />
** <tex>[6 .. 8)</tex> не пересекается с <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
<br />
<br />
* На глубине 3. <br />
** Листья <tex>1, 4</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них<br />
** Листья <tex>0, 5</tex> лежат вне <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
Таким образом ответ на полуинтервале <tex>[1 .. 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 .. 2)</tex>, <tex>[2 .. 4)</tex> и <tex>[4 .. 5)</tex>.<br />
<br />
==Реализация==<br />
Рассмотрим реализацию задачи RSQ.<br />
<br />
Пусть в узлах дерева хранятся структуры из трех полей:<br />
* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.<br />
* <tex>right</tex> {{---}} правая граница этого полуинтервала.<br />
* <tex> sum</tex> {{---}} сумма на полуинтервале.<br />
<br />
<code><br />
<br />
'''int''' get_sum ('''int''' node, '''int''' a, '''int''' b) <br />
l = tree[node].left<br />
r = tree[node].right <br />
'''if''' [l, r) <tex>\cap </tex> [a, b) == <tex> \varnothing</tex><br />
'''return''' 0<br />
'''if''' [l, r) <tex>\subset</tex> [a, b)<br />
'''return''' tree[node].sum<br />
'''return''' get_sum (node * 2 + 1, a, b) + get_sum (node * 2 + 2, a, b)<br />
</code><br />
<br />
==Ссылки==<br />
<br />
[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]<br />
<br />
[http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Дерево отрезков — Википедия]<br />
<br />
[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор дерева отрезков]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Дерево отрезков]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%B2%D0%B5%D1%80%D1%85%D1%83&diff=38957Реализация запроса в дереве отрезков сверху2014-06-13T07:24:28Z<p>Nastya: /* Реализация */</p>
<hr />
<div>Данная операция позволяет выполнять запросы на [[Дерево отрезков. Построение|дереве отрезков]], причем алгоритм запускается от корня и рекурсивно идет сверху вниз.<br />
<br />
==Алгоритм==<br />
''Замечание.''<br />
Используем в алгоритме не отрезки, а полуинтервалы (левая граница включительно, а правая - нет).<br />
<br />
Пусть есть уже [[Дерево отрезков. Построение|построенное дерево отрезков]] и идет запрос на полуинтервале <tex>[a .. b)</tex>.<br />
<br />
В качестве параметров рекурсий передаем следующие переменные:<br />
* <tex>node</tex> {{---}} номер (в массиве с деревом отрезков) текущей вершины дерева.<br />
* <tex>a</tex>, <tex>b</tex> {{---}} левая и правая границы запрашиваемого полуинтервала.<br />
<br />
Пусть <tex>l</tex>, <tex>r</tex> {{---}} это левая и правая границы полуинтервала, за которые "отвечает" наша вершина.<br />
Запустим рекурсивную процедуру от всего полуинтервала (то есть от корневой вершины).<br />
<br />
Для текущего состояния проверяем следующие условия :<br />
<br />
* Если текущий полуинтервал не пересекается с искомым, то возвращаем нейтральный элемент.<br />
:''Например'': текущий <tex>[1..3)</tex>, а искомый <tex>[3 .. 5)</tex>;<br />
<br />
* Если текущий полуинтервал лежит внутри запрашиваемого полуинтервала, то возвращаем значение в текущей вершине.<br />
:''Например'': текущий <tex>[2..3)</tex>, а искомый <tex>[2..4)</tex>;<br />
<br />
* Иначе переходим к рекурсивным вызовам функций от детей вершины. При этом возвращаем значение на текущем полуинтервале, как функцию (соответствующую типу нашего запроса) от результатов выполнения на детях.<br />
<br />
Так как на каждом уровне дерева рекурсия может дойти до не более, чем двух вершин (иначе бы нашлось две рядом стоящие вершины одного уровня, объединение которых дало отрезок, за который отвечает вершина предыдущего уровня), а всего уровней <tex>\log n</tex>, то операция выполняется за <tex>O(\log n)</tex>.<br />
<br />
==Пример==<br />
<br />
Рассмотрим данный алгоритм на примере задачи RSQ (Range Sum Query {{---}} запрос суммы на отрезке).<br />
<br />
При этом сумма на текущем полуинтервале (в случае вызова рекурсий от детей) равна сумме результатов выполнения операции на этих детях.<br />
<br />
Пусть дерево содержит <tex>8</tex> листьев и запрашиваемая сумма <br />
{{---}} это отрезок <tex>[1 .. 4]</tex> (полуинтервал <tex>[1 .. 5)</tex>).<br />
[[Файл:Image_4.png|right|602px|Пример рабoты алгоритма]]<br />
Рассмотрим данный алгоритм на определенных глубинах рекурсии (то есть на разных уровнях дерева):<br />
<br />
* На глубине 0. (на рисунке глубина обозначена слева от уровня). Текущий полуинтервал <tex>[0 .. 8)</tex> пересекается с <tex>[1 .. 5) \Rightarrow</tex> переходим по рекурсивным вызовам на <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине 1. <tex>[0 .. 4)</tex> и <tex>[4 .. 8)</tex> пересекаются с <tex> [1 .. 5) \Rightarrow </tex> переходим по рекурсивным вызовам на полуинтервалах <tex>[0 ..<br />
2)</tex>, <tex>[2 .. 4)</tex>, <tex>[4 .. 6)</tex> и <tex>[6 .. 8)</tex><br />
<br />
<br />
<br />
* На глубине 2. <br />
** <tex>[0 .. 2)</tex> и <tex>[4 .. 6)</tex> пересекаются с <tex>[1 .. 5) \Rightarrow </tex> переходим в листья <tex>0, 1, 4, 5 </tex><br />
** <tex>[2 .. 4) </tex> полностью лежит внутри <tex>[1 .. 5) \Rightarrow </tex> возвращаем сумму на этом отрезке<br />
** <tex>[6 .. 8)</tex> не пересекается с <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
<br />
<br />
* На глубине 3. <br />
** Листья <tex>1, 4</tex> лежат в запрашиваемом интервале <tex>\Rightarrow </tex> возвращаем значения в них<br />
** Листья <tex>0, 5</tex> лежат вне <tex>[1 .. 5) \Rightarrow </tex> возвращаем нулевое значение<br />
<br />
Таким образом ответ на полуинтервале <tex>[1 .. 5)</tex> равен сумме значений в вершинах, отвечающих за полуинтервалы <tex>[1 .. 2)</tex>, <tex>[2 .. 4)</tex> и <tex>[4 .. 5)</tex>.<br />
<br />
==Реализация==<br />
Рассмотрим реализацию задачи RSQ.<br />
<br />
Пусть в узлах дерева хранятся структуры из трех полей:<br />
* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.<br />
* <tex>right</tex> {{---}} правая граница этого полуинтервала.<br />
* <tex> sum</tex> {{---}} сумма на полуинтервале.<br />
<br />
<code><br />
<br />
'''int''' get_sum ('''int''' node, '''int''' a, '''int''' b) <br />
l = tree[node].left<br />
r = tree[node].right <br />
'''if''' [l, r) <tex>\cap </tex> [a, b) == <tex> \varnothing</tex><br />
'''return''' 0<br />
'''if''' [l, r) <tex>\subset</tex> [a, b)<br />
'''return''' tree[node].sum<br />
'''return''' get_sum (node * 2 + 1, a, b) + get_sum (node * 2 + 2, a, b)<br />
</code><br />
<br />
==Ссылки==<br />
<br />
[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]<br />
<br />
[http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Дерево отрезков — Википедия]<br />
<br />
[http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Визуализатор дерева отрезков]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Дерево отрезков]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%9D%D0%9C_(%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8)&diff=38956СНМ (наивные реализации)2014-06-13T07:12:54Z<p>Nastya: /* С помощью списка */</p>
<hr />
<div>'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами. <br />
__TOC__<br />
== Описание ==<br />
Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1 </tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.<br />
<br />
Определены две операции:<br />
* <math> \mathrm{union(x, y)} </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y </tex><br />
* <math> \mathrm{find (x)} </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x </tex><br />
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.<br />
<br />
[[Файл:DSU_1_Example.png|500px|center|Пример работы СНМ]]<br />
<br />
== Реализации ==<br />
=== С помощью массива ===<br />
<br />
<!--<br />
'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|<tex>O(n)</tex><br />
|}<br />
--><br />
<br />
Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.<br />
<br />
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда <math> \mathrm{union} </math> работает за <tex>O(n)</tex>.<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве </font><br />
</code><br />
<code> <br />
'''int''' find(k):<br />
'''return''' s[k]<br />
</code><br />
<code> <br />
'''func''' union(x, y):<br />
'''if''' s[x] == s[y]<br />
'''return'''<br />
'''else'''<br />
t = s[y]<br />
'''for''' i = 0 '''to''' n - 1<br />
'''if''' s[i] == t<br />
s[i] = s[x]<br />
</code><br />
<br />
=== С помощью списка ===<br />
<!--'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|}--><br />
<br />
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head </tex>. Значит <math> \mathrm{find} </math> работает за <tex> O(1) </tex>.<br />
<br />
Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head </tex>. Таким образом, <math> \mathrm{union} </math> работает за <tex> O(n) </tex>.<br />
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.<br />
<br />
<code><br />
'''srtruct''' nameOfStruct <br />
int head<br />
*nameOfStruct next<br />
int data<br />
<br />
nameOFStruct s[n]<br />
<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i].data = i<br />
s[i].next = null<br />
s[i].head = s[i]<br />
</code> <br />
<code><br />
'''int''' find(nameOfStruct x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font><br />
'''return''' x.head.data<br />
</code> <br />
<code><br />
'''func''' union(nameOfStruct x, nameOfStruct y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font><br />
x = x.head<br />
y = y.head<br />
'''if''' x == y<br />
'''return'''<br />
x.tail.next = y <font color=green> // соединим списки </font><br />
x.tail = y.tail <font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font><br />
'''while''' y <tex> \neq </tex> null <font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font><br />
y.head = x<br />
y = y.next<br />
</code><br />
[[Файл:DSU_list_example.png|800px|center|Пример объединения двух множеств (union)]]<br />
<br />
== Другие реализации ==<br />
* [[СНМ (списки с весовой эвристикой)]]<br />
* [[СНМ (реализация с помощью леса корневых деревьев)]]<br />
<br />
== Источники информации ==<br />
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.<br />
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%9D%D0%9C_(%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8)&diff=38955СНМ (наивные реализации)2014-06-13T07:07:55Z<p>Nastya: /* С помощью списка */</p>
<hr />
<div>'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами. <br />
__TOC__<br />
== Описание ==<br />
Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1 </tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.<br />
<br />
Определены две операции:<br />
* <math> \mathrm{union(x, y)} </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y </tex><br />
* <math> \mathrm{find (x)} </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x </tex><br />
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.<br />
<br />
[[Файл:DSU_1_Example.png|500px|center|Пример работы СНМ]]<br />
<br />
== Реализации ==<br />
=== С помощью массива ===<br />
<br />
<!--<br />
'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|<tex>O(n)</tex><br />
|}<br />
--><br />
<br />
Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.<br />
<br />
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда <math> \mathrm{union} </math> работает за <tex>O(n)</tex>.<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве </font><br />
</code><br />
<code> <br />
'''int''' find(k):<br />
'''return''' s[k]<br />
</code><br />
<code> <br />
'''func''' union(x, y):<br />
'''if''' s[x] == s[y]<br />
'''return'''<br />
'''else'''<br />
t = s[y]<br />
'''for''' i = 0 '''to''' n - 1<br />
'''if''' s[i] == t<br />
s[i] = s[x]<br />
</code><br />
<br />
=== С помощью списка ===<br />
<!--'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|}--><br />
<br />
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head </tex>. Значит <math> \mathrm{find} </math> работает за <tex> O(1) </tex>.<br />
<br />
Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head </tex>. Таким образом, <math> \mathrm{union} </math> работает за <tex> O(n) </tex>.<br />
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.<br />
<br />
<code><br />
'''srtruct''' nameOfStruct <br />
int head<br />
*nameOfStruct next<br />
int data<br />
<br />
nameOFStruct s[n]<br />
<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i].data = i<br />
s[i].next = null<br />
s[i].head = s[i]<br />
</code> <br />
<code><br />
'''int''' find(nameOfStruct x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font><br />
'''return''' x.head.data<br />
</code> <br />
<code><br />
'''func''' union(nameOfStruct x, nameOfStruct y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font><br />
x = x.head<br />
y = y.head<br />
'''if''' x == y<br />
'''return'''<br />
x.tail.next = y <font color=green> // соединим списки </font><br />
x.tail = y.tail <font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font><br />
'''while''' y <tex> \neq </tex> null <font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font><br />
y.head = x<br />
y = y.next<br />
</code><br />
[[Файл:DSU_list_example.png|800px|center|Пример объединения двух множеств (union)]]<br />
<br />
== Другие реализации ==<br />
* [[СНМ (списки с весовой эвристикой)]]<br />
* [[СНМ (реализация с помощью леса корневых деревьев)]]<br />
<br />
== Источники информации ==<br />
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.<br />
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%9D%D0%9C_(%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8)&diff=38954СНМ (наивные реализации)2014-06-13T07:07:03Z<p>Nastya: /* С помощью списка */</p>
<hr />
<div>'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами. <br />
__TOC__<br />
== Описание ==<br />
Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1 </tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.<br />
<br />
Определены две операции:<br />
* <math> \mathrm{union(x, y)} </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y </tex><br />
* <math> \mathrm{find (x)} </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x </tex><br />
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.<br />
<br />
[[Файл:DSU_1_Example.png|500px|center|Пример работы СНМ]]<br />
<br />
== Реализации ==<br />
=== С помощью массива ===<br />
<br />
<!--<br />
'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|<tex>O(n)</tex><br />
|}<br />
--><br />
<br />
Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.<br />
<br />
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда <math> \mathrm{union} </math> работает за <tex>O(n)</tex>.<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве </font><br />
</code><br />
<code> <br />
'''int''' find(k):<br />
'''return''' s[k]<br />
</code><br />
<code> <br />
'''func''' union(x, y):<br />
'''if''' s[x] == s[y]<br />
'''return'''<br />
'''else'''<br />
t = s[y]<br />
'''for''' i = 0 '''to''' n - 1<br />
'''if''' s[i] == t<br />
s[i] = s[x]<br />
</code><br />
<br />
=== С помощью списка ===<br />
<!--'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|}--><br />
<br />
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head </tex>. Значит <math> \mathrm{find} </math> работает за <tex> O(1) </tex>.<br />
<br />
Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head </tex>. Таким образом, <math> \mathrm{union} </math> работает за <tex> O(n) </tex>.<br />
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.<br />
<br />
<code><br />
'''srtruct''' nameOfStruct <br />
int head<br />
*nameOfStruct next<br />
int data<br />
<br />
nameOFStruct s[n]<br />
<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i].data = i<br />
s[i].next = null<br />
s[i].head = s[i]<br />
</code> <br />
<code><br />
'''int''' find(x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font><br />
'''return''' x.head.data<br />
</code> <br />
<code><br />
'''func''' union(nameOfStruct x, nameOfStruct y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font><br />
x = x.head<br />
y = y.head<br />
'''if''' x == y<br />
'''return'''<br />
x.tail.next = y <font color=green> // соединим списки </font><br />
x.tail = y.tail <font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font><br />
'''while''' y <tex> \neq </tex> null <font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font><br />
y.head = x<br />
y = y.next<br />
</code><br />
[[Файл:DSU_list_example.png|800px|center|Пример объединения двух множеств (union)]]<br />
<br />
== Другие реализации ==<br />
* [[СНМ (списки с весовой эвристикой)]]<br />
* [[СНМ (реализация с помощью леса корневых деревьев)]]<br />
<br />
== Источники информации ==<br />
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.<br />
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%83%D1%87%D0%B0_%D0%91%D1%80%D0%BE%D0%B4%D0%B0%D0%BB%D0%B0-%D0%9E%D0%BA%D0%B0%D1%81%D0%B0%D0%BA%D0%B8&diff=38742Куча Бродала-Окасаки2014-06-12T07:12:48Z<p>Nastya: /* Структура */</p>
<hr />
<div>'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping. Первое позволяет делать <math>\mathrm{insert}</math> за <tex>O(1)</tex>, второе позволяет получать минимальный элемент за <tex>O(1)</tex>, а третье {{---}} позволяющей выполнить <math>\mathrm{merge}</math> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.<br />
<br />
== Структура ==<br />
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping. <br />
{{Определение<br />
|neat = 0<br />
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <math>\mathrm{merge}</math> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.<br />
}}<br />
<br />
<br />
<br />
<br />
<br />
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:<br />
<br />
<tex> BPQ \left ( T_{min}, PQ \right) = \langle T_{min}, PQ \left (BPQ \left \langle T_{min}, PQ\right \rangle \right)\rangle</tex><br />
<br />
Куча из одного элемента будет выглядеть так:<br />
<br />
<math> \mathrm{create} </math><tex>(x) = BPQ \left \langle x, null\right \rangle</tex><br />
<br />
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex><br />
<br />
== Операции ==<br />
=== Merge ===<br />
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго <tex> BPQ </tex>.<br />
<code><br />
'''BPQ''' merge(<tex> \langle </tex>x:'''int''', q:'''BPQ'''<tex> \rangle </tex>, <tex> \langle </tex>y:'''int''', r:'''BPQ'''<tex> \rangle </tex>):<br />
'''if''' x < y<br />
'''return''' (x, insert(q, <tex> \langle </tex>y, r<tex> \rangle </tex>))<br />
'''else'''<br />
'''return''' (y, insert(r, <tex> \langle </tex>x, q<tex> \rangle </tex>))<br />
</code><br />
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== Insert ===<br />
Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом.<br />
<code><br />
'''<tex> \langle </tex>int, BPQ<tex> \rangle </tex>''' insert(<tex> \langle </tex>x:'''int''', q:'''BPQ'''<tex> \rangle </tex>, y:'''BPQ'''):<br />
'''return''' merge(<tex> \langle </tex>x, q<tex> \rangle </tex>, create(y))<br />
</code><br />
Создание и <math>\mathrm{merge}</math> выполняются за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== getMin ===<br />
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.<br />
<code><br />
'''int''' getMin(<tex> \langle </tex>x:'''int''', q:'''BPQ'''<tex> \rangle </tex>):<br />
'''return''' x<br />
</code><br />
Очевидно, работает за <tex>O(1)</tex>.<br />
<br />
=== extractMin ===<br />
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди, состоящей из <tex> BPQ</tex>. <br />
<code><br />
'''<tex> \langle </tex>int, BPQ<tex> \rangle </tex>''' extractMin(<tex> \langle </tex>x:'''int''', q:'''BPQ'''<tex> \rangle </tex>):<br />
<tex> \langle </tex><tex> \langle </tex>y, r<tex> \rangle </tex>, t<tex> \rangle </tex> = extractMin(q)<br />
'''return''' <tex> \langle </tex>y, merge(r, t)<tex> \rangle </tex><br />
</code><br />
Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <math>\mathrm{merge}</math> функция, выполняющая слияние двух приоритетных очередей.<br />
<br />
Возвращаем <tex> BPQ </tex>, где <tex>y</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}</math> приоритетная очередь без элемента <tex>y</tex>.<br />
<br />
Так как <math>\mathrm{extractMin}</math> и <math>\mathrm{merge}</math> выполняются за <tex>O(\log N)</tex>, тогда <math>\mathrm{extractMin}</math> выполняется за <tex>O(\log N)</tex>.<br />
<br />
== Смотри также ==<br />
* [[Биномиальная куча]]<br />
* [[Очередь]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== Источники информации ==<br />
* [http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]<br />
<br />
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%9D%D0%9C_(%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8)&diff=38741СНМ (наивные реализации)2014-06-12T06:38:29Z<p>Nastya: </p>
<hr />
<div>'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами. <br />
__TOC__<br />
== Описание ==<br />
Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1 </tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.<br />
<br />
Определены две операции:<br />
* <math> \mathrm{union(x, y)} </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y </tex><br />
* <math> \mathrm{find (x)} </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x </tex><br />
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.<br />
<br />
[[Файл:DSU_1_Example.png|500px|center|Пример работы СНМ]]<br />
<br />
== Реализации ==<br />
=== С помощью массива ===<br />
<br />
<!--<br />
'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|<tex>O(n)</tex><br />
|}<br />
--><br />
<br />
Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.<br />
<br />
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда <math> \mathrm{union} </math> работает за <tex>O(n)</tex>.<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве </font><br />
</code><br />
<code> <br />
'''int''' find(k):<br />
'''return''' s[k]<br />
</code><br />
<code> <br />
'''func''' union(x, y):<br />
'''if''' s[x] == s[y]<br />
'''return'''<br />
'''else'''<br />
t = s[y]<br />
'''for''' i = 0 '''to''' n - 1<br />
'''if''' s[i] == t<br />
s[i] = s[x]<br />
</code><br />
<br />
=== С помощью списка ===<br />
<!--'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|}--><br />
<br />
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head </tex>. Значит <math> \mathrm{find} </math> работает за <tex> O(1) </tex>.<br />
<br />
Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head </tex>. Таким образом, <math> \mathrm{union} </math> работает за <tex> O(n) </tex>.<br />
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.<br />
<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i].data = i<br />
s[i].next = null<br />
s[i].head = s[i]<br />
</code> <br />
<code><br />
'''int''' find(x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font><br />
'''return''' x.head.data<br />
</code> <br />
<code><br />
'''func''' union('''int''' x, '''int''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font><br />
x = x.head<br />
y = y.head<br />
'''if''' x == y<br />
'''return'''<br />
x.tail.next = y <font color=green> // соединим списки </font><br />
x.tail = y.tail <font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font><br />
'''while''' y <tex> \neq </tex> null <font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font><br />
y.head = x<br />
y = y.next<br />
</code><br />
[[Файл:DSU_list_example.png|800px|center|Пример объединения двух множеств (union)]]<br />
<br />
== Другие реализации ==<br />
* [[СНМ (списки с весовой эвристикой)]]<br />
* [[СНМ (реализация с помощью леса корневых деревьев)]]<br />
<br />
== Источники информации ==<br />
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.<br />
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%83%D1%87%D0%B0_%D0%91%D1%80%D0%BE%D0%B4%D0%B0%D0%BB%D0%B0-%D0%9E%D0%BA%D0%B0%D1%81%D0%B0%D0%BA%D0%B8&diff=38740Куча Бродала-Окасаки2014-06-12T06:15:51Z<p>Nastya: </p>
<hr />
<div>'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping. Первое позволяет делать <math>\mathrm{insert}</math> за <tex>O(1)</tex>, второе позволяет получать минимальный элемент за <tex>O(1)</tex>, а третье {{---}} позволяющей выполнить <math>\mathrm{merge}</math> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.<br />
<br />
== Структура ==<br />
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping. <br />
{{Определение<br />
|neat = 0<br />
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <math>\mathrm{merge}</math> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.<br />
}}<br />
<br />
<br />
<br />
<br />
<br />
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:<br />
<br />
<tex> BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)</tex><br />
<br />
Куча из одного элемента будет выглядеть так:<br />
<br />
<math> \mathrm{create} </math><tex>(x) = BPQ \left \langle x, null\right \rangle</tex><br />
<br />
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex><br />
<br />
== Операции ==<br />
=== Merge ===<br />
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго <tex> BPQ </tex>.<br />
<code><br />
'''BPQ''' merge(<tex> \langle </tex>x:'''int''', q:'''BPQ'''<tex> \rangle </tex>, <tex> \langle </tex>y:'''int''', r:'''BPQ'''<tex> \rangle </tex>):<br />
'''if''' x < y<br />
'''return''' (x, insert(q, <tex> \langle </tex>y, r<tex> \rangle </tex>))<br />
'''else'''<br />
'''return''' (y, insert(r, <tex> \langle </tex>x, q<tex> \rangle </tex>))<br />
</code><br />
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== Insert ===<br />
Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом.<br />
<code><br />
'''<tex> \langle </tex>int, BPQ<tex> \rangle </tex>''' insert(<tex> \langle </tex>x:'''int''', q:'''BPQ'''<tex> \rangle </tex>, y:'''BPQ'''):<br />
'''return''' merge(<tex> \langle </tex>x, q<tex> \rangle </tex>, create(y))<br />
</code><br />
Создание и <math>\mathrm{merge}</math> выполняются за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== getMin ===<br />
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.<br />
<code><br />
'''int''' getMin(<tex> \langle </tex>x:'''int''', q:'''BPQ'''<tex> \rangle </tex>):<br />
'''return''' x<br />
</code><br />
Очевидно, работает за <tex>O(1)</tex>.<br />
<br />
=== extractMin ===<br />
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди, состоящей из <tex> BPQ</tex>. <br />
<code><br />
'''<tex> \langle </tex>int, BPQ<tex> \rangle </tex>''' extractMin(<tex> \langle </tex>x:'''int''', q:'''BPQ'''<tex> \rangle </tex>):<br />
<tex> \langle </tex><tex> \langle </tex>y, r<tex> \rangle </tex>, t<tex> \rangle </tex> = extractMin(q)<br />
'''return''' <tex> \langle </tex>y, merge(r, t)<tex> \rangle </tex><br />
</code><br />
Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <math>\mathrm{merge}</math> функция, выполняющая слияние двух приоритетных очередей.<br />
<br />
Возвращаем <tex> BPQ </tex>, где <tex>y</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}</math> приоритетная очередь без элемента <tex>y</tex>.<br />
<br />
Так как <math>\mathrm{extractMin}</math> и <math>\mathrm{merge}</math> выполняются за <tex>O(\log N)</tex>, тогда <math>\mathrm{extractMin}</math> выполняется за <tex>O(\log N)</tex>.<br />
<br />
== Смотри также ==<br />
* [[Биномиальная куча]]<br />
* [[Очередь]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== Источники информации ==<br />
* [http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]<br />
<br />
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%83%D1%87%D0%B0_%D0%91%D1%80%D0%BE%D0%B4%D0%B0%D0%BB%D0%B0-%D0%9E%D0%BA%D0%B0%D1%81%D0%B0%D0%BA%D0%B8&diff=38739Куча Бродала-Окасаки2014-06-12T05:03:23Z<p>Nastya: /* Insert */</p>
<hr />
<div>'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping. Первое позволяет делать <math>\mathrm{insert}</math> за <tex>O(1)</tex>, второе позволяет получать минимальный элемент за <tex>O(1)</tex>, а третье {{---}} позволяющей выполнить <math>\mathrm{merge}</math> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.<br />
<br />
== Структура ==<br />
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping. <br />
{{Определение<br />
|neat = 0<br />
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <math>\mathrm{merge}</math> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.<br />
}}<br />
<br />
<br />
<br />
<br />
<br />
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:<br />
<br />
<tex> BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)</tex><br />
<br />
Куча из одного элемента будет выглядеть так:<br />
<br />
<math> \mathrm{create} </math><tex>(x) = BPQ \left \langle x, null\right \rangle</tex><br />
<br />
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex><br />
<br />
== Операции ==<br />
=== Merge ===<br />
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго <tex> BPQ </tex>.<br />
<code><br />
'''BPQ''' merge(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>, <tex> \langle </tex>y:'''int''', r:'''bpq'''<tex> \rangle </tex>):<br />
'''if''' x < y<br />
'''return''' (x, insert(q, <tex> \langle </tex>y, r<tex> \rangle </tex>))<br />
'''else'''<br />
'''return''' (y, insert(r, <tex> \langle </tex>x, q<tex> \rangle </tex>))<br />
</code><br />
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== Insert ===<br />
Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом.<br />
<code><br />
'''<tex> \langle </tex>int, bpq<tex> \rangle </tex>''' insert(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>, y:'''bpq'''):<br />
'''return''' merge(<tex> \langle </tex>x, q<tex> \rangle </tex>, create(y))<br />
</code><br />
Создание и <math>\mathrm{merge}</math> выполняются за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== getMin ===<br />
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.<br />
<code><br />
'''int''' getMin(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>):<br />
'''return''' x<br />
</code><br />
Очевидно, работает за <tex>O(1)</tex>.<br />
<br />
=== extractMin ===<br />
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди, состоящей из <tex> BPQ</tex>. <br />
<code><br />
'''<tex> \langle </tex>int, bpq<tex> \rangle </tex>''' extractMin(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>):<br />
<tex> \langle </tex><tex> \langle </tex>y, r<tex> \rangle </tex>, t<tex> \rangle </tex> = extractMin(q)<br />
'''return''' <tex> \langle </tex>y, merge(r, t)<tex> \rangle </tex><br />
</code><br />
Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <math>\mathrm{merge}</math> функция, выполняющая слияние двух приоритетных очередей.<br />
<br />
Возвращаем <tex> BPQ </tex>, где <tex>y</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}</math> приоритетная очередь без элемента <tex>y</tex>.<br />
<br />
Так как <math>\mathrm{extractMin}</math> и <math>\mathrm{merge}</math> выполняются за <tex>O(\log N)</tex>, тогда <math>\mathrm{extractMin}</math> выполняется за <tex>O(\log N)</tex>.<br />
<br />
== Смотри также ==<br />
* [[Биномиальная куча]]<br />
* [[Очередь]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== Источники информации ==<br />
* [http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]<br />
<br />
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%83%D1%87%D0%B0_%D0%91%D1%80%D0%BE%D0%B4%D0%B0%D0%BB%D0%B0-%D0%9E%D0%BA%D0%B0%D1%81%D0%B0%D0%BA%D0%B8&diff=38738Куча Бродала-Окасаки2014-06-12T05:02:56Z<p>Nastya: /* getMin */</p>
<hr />
<div>'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping. Первое позволяет делать <math>\mathrm{insert}</math> за <tex>O(1)</tex>, второе позволяет получать минимальный элемент за <tex>O(1)</tex>, а третье {{---}} позволяющей выполнить <math>\mathrm{merge}</math> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.<br />
<br />
== Структура ==<br />
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping. <br />
{{Определение<br />
|neat = 0<br />
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <math>\mathrm{merge}</math> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.<br />
}}<br />
<br />
<br />
<br />
<br />
<br />
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:<br />
<br />
<tex> BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)</tex><br />
<br />
Куча из одного элемента будет выглядеть так:<br />
<br />
<math> \mathrm{create} </math><tex>(x) = BPQ \left \langle x, null\right \rangle</tex><br />
<br />
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex><br />
<br />
== Операции ==<br />
=== Merge ===<br />
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго <tex> BPQ </tex>.<br />
<code><br />
'''BPQ''' merge(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>, <tex> \langle </tex>y:'''int''', r:'''bpq'''<tex> \rangle </tex>):<br />
'''if''' x < y<br />
'''return''' (x, insert(q, <tex> \langle </tex>y, r<tex> \rangle </tex>))<br />
'''else'''<br />
'''return''' (y, insert(r, <tex> \langle </tex>x, q<tex> \rangle </tex>))<br />
</code><br />
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== Insert ===<br />
Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом.<br />
<code><br />
'''<tex> \langle </tex>int, bpq<tex> \rangle </tex>''' insert(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>, y:'''bpq'''):<br />
return merge(<tex> \langle </tex>x, q<tex> \rangle </tex>, create(y))<br />
</code><br />
Создание и <math>\mathrm{merge}</math> выполняются за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== getMin ===<br />
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.<br />
<code><br />
'''int''' getMin(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>):<br />
'''return''' x<br />
</code><br />
Очевидно, работает за <tex>O(1)</tex>.<br />
<br />
=== extractMin ===<br />
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди, состоящей из <tex> BPQ</tex>. <br />
<code><br />
'''<tex> \langle </tex>int, bpq<tex> \rangle </tex>''' extractMin(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>):<br />
<tex> \langle </tex><tex> \langle </tex>y, r<tex> \rangle </tex>, t<tex> \rangle </tex> = extractMin(q)<br />
'''return''' <tex> \langle </tex>y, merge(r, t)<tex> \rangle </tex><br />
</code><br />
Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <math>\mathrm{merge}</math> функция, выполняющая слияние двух приоритетных очередей.<br />
<br />
Возвращаем <tex> BPQ </tex>, где <tex>y</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}</math> приоритетная очередь без элемента <tex>y</tex>.<br />
<br />
Так как <math>\mathrm{extractMin}</math> и <math>\mathrm{merge}</math> выполняются за <tex>O(\log N)</tex>, тогда <math>\mathrm{extractMin}</math> выполняется за <tex>O(\log N)</tex>.<br />
<br />
== Смотри также ==<br />
* [[Биномиальная куча]]<br />
* [[Очередь]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== Источники информации ==<br />
* [http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]<br />
<br />
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%83%D1%87%D0%B0_%D0%91%D1%80%D0%BE%D0%B4%D0%B0%D0%BB%D0%B0-%D0%9E%D0%BA%D0%B0%D1%81%D0%B0%D0%BA%D0%B8&diff=38737Куча Бродала-Окасаки2014-06-12T04:49:58Z<p>Nastya: /* Merge */</p>
<hr />
<div>'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping. Первое позволяет делать <math>\mathrm{insert}</math> за <tex>O(1)</tex>, второе позволяет получать минимальный элемент за <tex>O(1)</tex>, а третье {{---}} позволяющей выполнить <math>\mathrm{merge}</math> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.<br />
<br />
== Структура ==<br />
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping. <br />
{{Определение<br />
|neat = 0<br />
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <math>\mathrm{merge}</math> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.<br />
}}<br />
<br />
<br />
<br />
<br />
<br />
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:<br />
<br />
<tex> BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)</tex><br />
<br />
Куча из одного элемента будет выглядеть так:<br />
<br />
<math> \mathrm{create} </math><tex>(x) = BPQ \left \langle x, null\right \rangle</tex><br />
<br />
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex><br />
<br />
== Операции ==<br />
=== Merge ===<br />
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго <tex> BPQ </tex>.<br />
<code><br />
'''BPQ''' merge(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>, <tex> \langle </tex>y:'''int''', r:'''bpq'''<tex> \rangle </tex>):<br />
'''if''' x < y<br />
'''return''' (x, insert(q, <tex> \langle </tex>y, r<tex> \rangle </tex>))<br />
'''else'''<br />
'''return''' (y, insert(r, <tex> \langle </tex>x, q<tex> \rangle </tex>))<br />
</code><br />
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== Insert ===<br />
Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом.<br />
<code><br />
'''<tex> \langle </tex>int, bpq<tex> \rangle </tex>''' insert(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>, y:'''bpq'''):<br />
return merge(<tex> \langle </tex>x, q<tex> \rangle </tex>, create(y))<br />
</code><br />
Создание и <math>\mathrm{merge}</math> выполняются за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== getMin ===<br />
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.<br />
<code><br />
'''int''' getMin(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>):<br />
return x<br />
</code><br />
Очевидно, работает за <tex>O(1)</tex>.<br />
<br />
=== extractMin ===<br />
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди, состоящей из <tex> BPQ</tex>. <br />
<code><br />
'''<tex> \langle </tex>int, bpq<tex> \rangle </tex>''' extractMin(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>):<br />
<tex> \langle </tex><tex> \langle </tex>y, r<tex> \rangle </tex>, t<tex> \rangle </tex> = extractMin(q)<br />
'''return''' <tex> \langle </tex>y, merge(r, t)<tex> \rangle </tex><br />
</code><br />
Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <math>\mathrm{merge}</math> функция, выполняющая слияние двух приоритетных очередей.<br />
<br />
Возвращаем <tex> BPQ </tex>, где <tex>y</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}</math> приоритетная очередь без элемента <tex>y</tex>.<br />
<br />
Так как <math>\mathrm{extractMin}</math> и <math>\mathrm{merge}</math> выполняются за <tex>O(\log N)</tex>, тогда <math>\mathrm{extractMin}</math> выполняется за <tex>O(\log N)</tex>.<br />
<br />
== Смотри также ==<br />
* [[Биномиальная куча]]<br />
* [[Очередь]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== Источники информации ==<br />
* [http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]<br />
<br />
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%83%D1%87%D0%B0_%D0%91%D1%80%D0%BE%D0%B4%D0%B0%D0%BB%D0%B0-%D0%9E%D0%BA%D0%B0%D1%81%D0%B0%D0%BA%D0%B8&diff=38736Куча Бродала-Окасаки2014-06-12T04:46:17Z<p>Nastya: /* extractMin */</p>
<hr />
<div>'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping. Первое позволяет делать <math>\mathrm{insert}</math> за <tex>O(1)</tex>, второе позволяет получать минимальный элемент за <tex>O(1)</tex>, а третье {{---}} позволяющей выполнить <math>\mathrm{merge}</math> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.<br />
<br />
== Структура ==<br />
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping. <br />
{{Определение<br />
|neat = 0<br />
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <math>\mathrm{merge}</math> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.<br />
}}<br />
<br />
<br />
<br />
<br />
<br />
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:<br />
<br />
<tex> BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)</tex><br />
<br />
Куча из одного элемента будет выглядеть так:<br />
<br />
<math> \mathrm{create} </math><tex>(x) = BPQ \left \langle x, null\right \rangle</tex><br />
<br />
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex><br />
<br />
== Операции ==<br />
=== Merge ===<br />
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго <tex> BPQ </tex>.<br />
<code><br />
'''BPQ''' merge(<tex> \langle </tex>x : '''int''', q : '''BPQ'''<tex> \rangle </tex>, <tex> \langle </tex>y:'''int''', r:'''bpq'''<tex> \rangle </tex>:'''pair'''):<br />
'''if''' x < y<br />
'''return''' (x, insert(q, <tex> \langle </tex>y, r<tex> \rangle </tex>))<br />
'''else'''<br />
'''return''' (y, insert(r, <tex> \langle </tex>x, q<tex> \rangle </tex>))<br />
</code><br />
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== Insert ===<br />
Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом.<br />
<code><br />
'''<tex> \langle </tex>int, bpq<tex> \rangle </tex>''' insert(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>, y:'''bpq'''):<br />
return merge(<tex> \langle </tex>x, q<tex> \rangle </tex>, create(y))<br />
</code><br />
Создание и <math>\mathrm{merge}</math> выполняются за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== getMin ===<br />
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.<br />
<code><br />
'''int''' getMin(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>):<br />
return x<br />
</code><br />
Очевидно, работает за <tex>O(1)</tex>.<br />
<br />
=== extractMin ===<br />
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди, состоящей из <tex> BPQ</tex>. <br />
<code><br />
'''<tex> \langle </tex>int, bpq<tex> \rangle </tex>''' extractMin(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>):<br />
<tex> \langle </tex><tex> \langle </tex>y, r<tex> \rangle </tex>, t<tex> \rangle </tex> = extractMin(q)<br />
'''return''' <tex> \langle </tex>y, merge(r, t)<tex> \rangle </tex><br />
</code><br />
Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <math>\mathrm{merge}</math> функция, выполняющая слияние двух приоритетных очередей.<br />
<br />
Возвращаем <tex> BPQ </tex>, где <tex>y</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}</math> приоритетная очередь без элемента <tex>y</tex>.<br />
<br />
Так как <math>\mathrm{extractMin}</math> и <math>\mathrm{merge}</math> выполняются за <tex>O(\log N)</tex>, тогда <math>\mathrm{extractMin}</math> выполняется за <tex>O(\log N)</tex>.<br />
<br />
== Смотри также ==<br />
* [[Биномиальная куча]]<br />
* [[Очередь]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== Источники информации ==<br />
* [http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]<br />
<br />
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%83%D1%87%D0%B0_%D0%91%D1%80%D0%BE%D0%B4%D0%B0%D0%BB%D0%B0-%D0%9E%D0%BA%D0%B0%D1%81%D0%B0%D0%BA%D0%B8&diff=38735Куча Бродала-Окасаки2014-06-12T04:20:36Z<p>Nastya: /* getMin */</p>
<hr />
<div>'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping. Первое позволяет делать <math>\mathrm{insert}</math> за <tex>O(1)</tex>, второе позволяет получать минимальный элемент за <tex>O(1)</tex>, а третье {{---}} позволяющей выполнить <math>\mathrm{merge}</math> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.<br />
<br />
== Структура ==<br />
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping. <br />
{{Определение<br />
|neat = 0<br />
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <math>\mathrm{merge}</math> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.<br />
}}<br />
<br />
<br />
<br />
<br />
<br />
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:<br />
<br />
<tex> BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)</tex><br />
<br />
Куча из одного элемента будет выглядеть так:<br />
<br />
<math> \mathrm{create} </math><tex>(x) = BPQ \left \langle x, null\right \rangle</tex><br />
<br />
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex><br />
<br />
== Операции ==<br />
=== Merge ===<br />
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго <tex> BPQ </tex>.<br />
<code><br />
'''BPQ''' merge(<tex> \langle </tex>x : '''int''', q : '''BPQ'''<tex> \rangle </tex>, <tex> \langle </tex>y:'''int''', r:'''bpq'''<tex> \rangle </tex>:'''pair'''):<br />
'''if''' x < y<br />
'''return''' (x, insert(q, <tex> \langle </tex>y, r<tex> \rangle </tex>))<br />
'''else'''<br />
'''return''' (y, insert(r, <tex> \langle </tex>x, q<tex> \rangle </tex>))<br />
</code><br />
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== Insert ===<br />
Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом.<br />
<code><br />
'''<tex> \langle </tex>int, bpq<tex> \rangle </tex>''' insert(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>, y:'''bpq'''):<br />
return merge(<tex> \langle </tex>x, q<tex> \rangle </tex>, create(y))<br />
</code><br />
Создание и <math>\mathrm{merge}</math> выполняются за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== getMin ===<br />
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.<br />
<code><br />
'''int''' getMin(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>):<br />
return x<br />
</code><br />
Очевидно, работает за <tex>O(1)</tex>.<br />
<br />
=== extractMin ===<br />
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди <tex> BPQ</tex>ов. <br />
<code><br />
'''pair (int, bpq)''' extractMin((x:'''int''', q:'''bpq'''):'''pair'''):<br />
((y, r), t) = extractMin(q)<br />
'''return''' (y, merge(r, t))<br />
</code><br />
Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <math>\mathrm{merge}</math> функция, выполняющая слияние двух приоритетных очередей.<br />
<br />
Возвращаем <tex> BPQ </tex>, где <tex>y</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}</math> приоритетная очередь без элемента <tex>y</tex>.<br />
<br />
Так как <math>\mathrm{extractMin}</math> и <math>\mathrm{merge}</math> выполняются за <tex>O(\log N)</tex>, тогда <math>\mathrm{extractMin}</math> выполняется за <tex>O(\log N)</tex>.<br />
<br />
== Смотри также ==<br />
* [[Биномиальная куча]]<br />
* [[Очередь]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== Источники информации ==<br />
* [http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]<br />
<br />
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%83%D1%87%D0%B0_%D0%91%D1%80%D0%BE%D0%B4%D0%B0%D0%BB%D0%B0-%D0%9E%D0%BA%D0%B0%D1%81%D0%B0%D0%BA%D0%B8&diff=38734Куча Бродала-Окасаки2014-06-12T04:19:40Z<p>Nastya: /* Insert */</p>
<hr />
<div>'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping. Первое позволяет делать <math>\mathrm{insert}</math> за <tex>O(1)</tex>, второе позволяет получать минимальный элемент за <tex>O(1)</tex>, а третье {{---}} позволяющей выполнить <math>\mathrm{merge}</math> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.<br />
<br />
== Структура ==<br />
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping. <br />
{{Определение<br />
|neat = 0<br />
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <math>\mathrm{merge}</math> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.<br />
}}<br />
<br />
<br />
<br />
<br />
<br />
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:<br />
<br />
<tex> BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)</tex><br />
<br />
Куча из одного элемента будет выглядеть так:<br />
<br />
<math> \mathrm{create} </math><tex>(x) = BPQ \left \langle x, null\right \rangle</tex><br />
<br />
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex><br />
<br />
== Операции ==<br />
=== Merge ===<br />
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго <tex> BPQ </tex>.<br />
<code><br />
'''BPQ''' merge(<tex> \langle </tex>x : '''int''', q : '''BPQ'''<tex> \rangle </tex>, <tex> \langle </tex>y:'''int''', r:'''bpq'''<tex> \rangle </tex>:'''pair'''):<br />
'''if''' x < y<br />
'''return''' (x, insert(q, <tex> \langle </tex>y, r<tex> \rangle </tex>))<br />
'''else'''<br />
'''return''' (y, insert(r, <tex> \langle </tex>x, q<tex> \rangle </tex>))<br />
</code><br />
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== Insert ===<br />
Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом.<br />
<code><br />
'''<tex> \langle </tex>int, bpq<tex> \rangle </tex>''' insert(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>, y:'''bpq'''):<br />
return merge(<tex> \langle </tex>x, q<tex> \rangle </tex>, create(y))<br />
</code><br />
Создание и <math>\mathrm{merge}</math> выполняются за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== getMin ===<br />
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.<br />
<code><br />
'''int''' getMin((x:'''int''', q:'''bpq'''):'''pair'''):<br />
return x;<br />
</code><br />
Очевидно, работает за <tex>O(1)</tex>.<br />
<br />
=== extractMin ===<br />
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди <tex> BPQ</tex>ов. <br />
<code><br />
'''pair (int, bpq)''' extractMin((x:'''int''', q:'''bpq'''):'''pair'''):<br />
((y, r), t) = extractMin(q)<br />
'''return''' (y, merge(r, t))<br />
</code><br />
Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <math>\mathrm{merge}</math> функция, выполняющая слияние двух приоритетных очередей.<br />
<br />
Возвращаем <tex> BPQ </tex>, где <tex>y</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}</math> приоритетная очередь без элемента <tex>y</tex>.<br />
<br />
Так как <math>\mathrm{extractMin}</math> и <math>\mathrm{merge}</math> выполняются за <tex>O(\log N)</tex>, тогда <math>\mathrm{extractMin}</math> выполняется за <tex>O(\log N)</tex>.<br />
<br />
== Смотри также ==<br />
* [[Биномиальная куча]]<br />
* [[Очередь]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== Источники информации ==<br />
* [http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]<br />
<br />
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%83%D1%87%D0%B0_%D0%91%D1%80%D0%BE%D0%B4%D0%B0%D0%BB%D0%B0-%D0%9E%D0%BA%D0%B0%D1%81%D0%B0%D0%BA%D0%B8&diff=38733Куча Бродала-Окасаки2014-06-12T04:13:58Z<p>Nastya: /* Merge */</p>
<hr />
<div>'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping. Первое позволяет делать <math>\mathrm{insert}</math> за <tex>O(1)</tex>, второе позволяет получать минимальный элемент за <tex>O(1)</tex>, а третье {{---}} позволяющей выполнить <math>\mathrm{merge}</math> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.<br />
<br />
== Структура ==<br />
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping. <br />
{{Определение<br />
|neat = 0<br />
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <math>\mathrm{merge}</math> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.<br />
}}<br />
<br />
<br />
<br />
<br />
<br />
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:<br />
<br />
<tex> BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)</tex><br />
<br />
Куча из одного элемента будет выглядеть так:<br />
<br />
<math> \mathrm{create} </math><tex>(x) = BPQ \left \langle x, null\right \rangle</tex><br />
<br />
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex><br />
<br />
== Операции ==<br />
=== Merge ===<br />
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго <tex> BPQ </tex>.<br />
<code><br />
'''BPQ''' merge(<tex> \langle </tex>x : '''int''', q : '''BPQ'''<tex> \rangle </tex>, <tex> \langle </tex>y:'''int''', r:'''bpq'''<tex> \rangle </tex>:'''pair'''):<br />
'''if''' x < y<br />
'''return''' (x, insert(q, <tex> \langle </tex>y, r<tex> \rangle </tex>))<br />
'''else'''<br />
'''return''' (y, insert(r, <tex> \langle </tex>x, q<tex> \rangle </tex>))<br />
</code><br />
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== Insert ===<br />
Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом.<br />
<code><br />
'''pair(int, bpq)''' insert((x:'''int''', q:'''bpq'''):'''pair''', y:'''bpq'''):<br />
return merge((x, q), create(y))<br />
</code><br />
Создание и <math>\mathrm{merge}</math> выполняются за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== getMin ===<br />
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.<br />
<code><br />
'''int''' getMin((x:'''int''', q:'''bpq'''):'''pair'''):<br />
return x;<br />
</code><br />
Очевидно, работает за <tex>O(1)</tex>.<br />
<br />
=== extractMin ===<br />
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди <tex> BPQ</tex>ов. <br />
<code><br />
'''pair (int, bpq)''' extractMin((x:'''int''', q:'''bpq'''):'''pair'''):<br />
((y, r), t) = extractMin(q)<br />
'''return''' (y, merge(r, t))<br />
</code><br />
Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <math>\mathrm{merge}</math> функция, выполняющая слияние двух приоритетных очередей.<br />
<br />
Возвращаем <tex> BPQ </tex>, где <tex>y</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}</math> приоритетная очередь без элемента <tex>y</tex>.<br />
<br />
Так как <math>\mathrm{extractMin}</math> и <math>\mathrm{merge}</math> выполняются за <tex>O(\log N)</tex>, тогда <math>\mathrm{extractMin}</math> выполняется за <tex>O(\log N)</tex>.<br />
<br />
== Смотри также ==<br />
* [[Биномиальная куча]]<br />
* [[Очередь]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== Источники информации ==<br />
* [http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]<br />
<br />
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%83%D1%87%D0%B0_%D0%91%D1%80%D0%BE%D0%B4%D0%B0%D0%BB%D0%B0-%D0%9E%D0%BA%D0%B0%D1%81%D0%B0%D0%BA%D0%B8&diff=38732Куча Бродала-Окасаки2014-06-12T04:09:19Z<p>Nastya: </p>
<hr />
<div>'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping. Первое позволяет делать <math>\mathrm{insert}</math> за <tex>O(1)</tex>, второе позволяет получать минимальный элемент за <tex>O(1)</tex>, а третье {{---}} позволяющей выполнить <math>\mathrm{merge}</math> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.<br />
<br />
== Структура ==<br />
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping. <br />
{{Определение<br />
|neat = 0<br />
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <math>\mathrm{merge}</math> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.<br />
}}<br />
<br />
<br />
<br />
<br />
<br />
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:<br />
<br />
<tex> BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)</tex><br />
<br />
Куча из одного элемента будет выглядеть так:<br />
<br />
<math> \mathrm{create} </math><tex>(x) = BPQ \left \langle x, null\right \rangle</tex><br />
<br />
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex><br />
<br />
== Операции ==<br />
=== Merge ===<br />
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго <tex> BPQ </tex>.<br />
<code><br />
'''BPQ''' merge(<tex> \langle </tex>x : '''int''', q : '''BPQ'''<tex> \rangle </tex>, (y:'''int''', r:'''bpq'''):'''pair'''):<br />
'''if''' x < y<br />
'''return''' (x, insert(q, (y, r)))<br />
'''else'''<br />
'''return''' (y, insert(r, (x, q)))<br />
</code><br />
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== Insert ===<br />
Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом.<br />
<code><br />
'''pair(int, bpq)''' insert((x:'''int''', q:'''bpq'''):'''pair''', y:'''bpq'''):<br />
return merge((x, q), create(y))<br />
</code><br />
Создание и <math>\mathrm{merge}</math> выполняются за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== getMin ===<br />
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.<br />
<code><br />
'''int''' getMin((x:'''int''', q:'''bpq'''):'''pair'''):<br />
return x;<br />
</code><br />
Очевидно, работает за <tex>O(1)</tex>.<br />
<br />
=== extractMin ===<br />
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди <tex> BPQ</tex>ов. <br />
<code><br />
'''pair (int, bpq)''' extractMin((x:'''int''', q:'''bpq'''):'''pair'''):<br />
((y, r), t) = extractMin(q)<br />
'''return''' (y, merge(r, t))<br />
</code><br />
Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <math>\mathrm{merge}</math> функция, выполняющая слияние двух приоритетных очередей.<br />
<br />
Возвращаем <tex> BPQ </tex>, где <tex>y</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}</math> приоритетная очередь без элемента <tex>y</tex>.<br />
<br />
Так как <math>\mathrm{extractMin}</math> и <math>\mathrm{merge}</math> выполняются за <tex>O(\log N)</tex>, тогда <math>\mathrm{extractMin}</math> выполняется за <tex>O(\log N)</tex>.<br />
<br />
== Смотри также ==<br />
* [[Биномиальная куча]]<br />
* [[Очередь]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== Источники информации ==<br />
* [http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]<br />
<br />
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%83%D1%87%D0%B0_%D0%91%D1%80%D0%BE%D0%B4%D0%B0%D0%BB%D0%B0-%D0%9E%D0%BA%D0%B0%D1%81%D0%B0%D0%BA%D0%B8&diff=38731Куча Бродала-Окасаки2014-06-12T03:41:45Z<p>Nastya: </p>
<hr />
<div>'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и на идеи Data-structural bootstrapping. Первое позволяет делать <math>\mathrm{insert}</math> за <tex>O(1)</tex>, второе позволяет получать минимальный элемент за <tex>O(1)</tex>, а третье {{---}} позволяющей выполнить <math>\mathrm{merge}</math> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.<br />
<br />
== Структура ==<br />
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping. <br />
{{Определение<br />
|neat = 0<br />
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <math>\mathrm{merge}</math> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.<br />
}}<br />
<br />
<br />
<br />
<br />
<br />
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:<br />
<br />
<tex> BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)</tex><br />
<br />
Куча из одного элемента будет выглядеть так:<br />
<br />
<math> \mathrm{create} </math><tex>(x) = BPQ \left \langle x, null\right \rangle</tex><br />
<br />
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex><br />
<br />
== Операции ==<br />
=== Merge ===<br />
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго ''BPQ''.<br />
<code><br />
'''BPQ''' merge(<tex> \langle </tex>x : '''int''', q : '''BPQ'''<tex> \rangle </tex>, (y:'''int''', r:'''bpq'''):'''pair'''):<br />
'''if''' x < y<br />
'''return''' (x, insert(q, (y, r)))<br />
'''else'''<br />
'''return''' (y, insert(r, (x, q)))<br />
</code><br />
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== Insert ===<br />
Это создание нового ''BPQ'' и <math>\mathrm{merge}</math> его с основным деревом.<br />
<code><br />
'''pair(int, bpq)''' insert((x:'''int''', q:'''bpq'''):'''pair''', y:'''bpq'''):<br />
return merge((x, q), create(y))<br />
</code><br />
Создание и <math>\mathrm{merge}</math> выполняются за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== getMin ===<br />
Выполняется просто, так как ''BPQ'' хранит минимум.<br />
<code><br />
'''int''' getMin((x:'''int''', q:'''bpq'''):'''pair'''):<br />
return x;<br />
</code><br />
Очевидно, работает за <tex>O(1)</tex>.<br />
<br />
=== extractMin ===<br />
Минимальный элемент хранится в верхнем ''BPQ'', по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди ''BPQ'''ов. <br />
<code><br />
'''pair (int, bpq)''' extractMin((x:'''int''', q:'''bpq'''):'''pair'''):<br />
((y, r), t) = extractMin(q)<br />
'''return''' (y, merge(r, t))<br />
</code><br />
Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа ''BPQ'' из приоритетной очереди, она возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа ''BPQ'' и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <math>\mathrm{merge}</math> функция, выполняющая слияние двух приоритетных очередей.<br />
<br />
Возвращаем ''BPQ'', где <tex>y</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}</math> приоритетная очередь без элемента <tex>y</tex>.<br />
<br />
Так как <math>\mathrm{extractMin}</math> и <math>\mathrm{merge}</math> выполняются за <tex>O(\log N)</tex>, тогда <math>\mathrm{extractMin}</math> выполняется за <tex>O(\log N)</tex>.<br />
<br />
== Смотри также ==<br />
* [[Биномиальная куча]]<br />
* [[Очередь]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== Источники информации ==<br />
* [http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]<br />
<br />
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%83%D1%87%D0%B0_%D0%91%D1%80%D0%BE%D0%B4%D0%B0%D0%BB%D0%B0-%D0%9E%D0%BA%D0%B0%D1%81%D0%B0%D0%BA%D0%B8&diff=38549Куча Бродала-Окасаки2014-06-11T09:08:42Z<p>Nastya: /* Операции */</p>
<hr />
<div>'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, что позволяет делать <math>\mathrm{insert}</math> за <tex>O(1)</tex>, добавлении минимального элемента, позволяет получать минимальный элемент за <tex>O(1)</tex>, и идеи Data-structural bootstrapping, позволяющей выполнить <math>\mathrm{merge}</math> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.<br />
<br />
== Структура ==<br />
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping. <br />
{{Определение<br />
|neat = 0<br />
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <math>\mathrm{merge}</math> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.<br />
}}<br />
<br />
<br />
<br />
<br />
<br />
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:<br />
<br />
<tex> BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)</tex><br />
<br />
Куча из одного элемента будет выглядеть так:<br />
<br />
<math> \mathrm{create} </math><tex>(x) = BPQ \left \langle x, null\right \rangle</tex><br />
<br />
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex><br />
<br />
== Операции ==<br />
=== Merge ===<br />
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго ''BPQ''.<br />
<code><br />
'''pair(int, bpq)''' merge((x:'''int''', q:'''bpq'''):'''pair''', (y:'''int''', r:'''bpq'''):'''pair'''):<br />
'''if''' x < y<br />
'''return''' (x, insert(q, (y, r)))<br />
'''else'''<br />
'''return''' (y, insert(r, (x, q)))<br />
</code><br />
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== Insert ===<br />
Это создание нового ''BPQ'' и <math>\mathrm{merge}</math> его с основным деревом.<br />
<code><br />
'''pair(int, bpq)''' insert((x:'''int''', q:'''bpq'''):'''pair''', y:'''bpq'''):<br />
return merge((x, q), create(y))<br />
</code><br />
Создание и <math>\mathrm{merge}</math> выполняются за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== getMin ===<br />
Выполняется просто, так как ''BPQ'' хранит минимум.<br />
<code><br />
'''int''' getMin((x:'''int''', q:'''bpq'''):'''pair'''):<br />
return x;<br />
</code><br />
Очевидно, работает за <tex>O(1)</tex>.<br />
<br />
=== extractMin ===<br />
Минимальный элемент хранится в верхнем ''BPQ'', по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди ''BPQ'''ов. <br />
<code><br />
'''pair (int, bpq)''' extractMin((x:'''int''', q:'''bpq'''):'''pair'''):<br />
((y, r), t) = extractMin(q)<br />
'''return''' (y, merge(r, t))<br />
</code><br />
Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа ''BPQ'' из приоритетной очереди, она возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа ''BPQ'' и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <math>\mathrm{merge}</math> функция, выполняющая слияние двух приоритетных очередей.<br />
<br />
Возвращаем ''BPQ'', где <tex>y</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}</math> приоритетная очередь без элемента <tex>y</tex>.<br />
<br />
Так как <math>\mathrm{extractMin}</math> и <math>\mathrm{merge}</math> выполняются за <tex>O(\log N)</tex>, тогда <math>\mathrm{extractMin}</math> выполняется за <tex>O(\log N)</tex>.<br />
<br />
== Смотри также ==<br />
* [[Биномиальная куча]]<br />
* [[Очередь]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== Источники информации ==<br />
* [http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]<br />
<br />
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9A%D1%83%D1%87%D0%B0_%D0%91%D1%80%D0%BE%D0%B4%D0%B0%D0%BB%D0%B0-%D0%9E%D0%BA%D0%B0%D1%81%D0%B0%D0%BA%D0%B8&diff=38547Куча Бродала-Окасаки2014-06-11T08:52:19Z<p>Nastya: </p>
<hr />
<div>'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, что позволяет делать <math>\mathrm{insert}</math> за <tex>O(1)</tex>, добавлении минимального элемента, позволяет получать минимальный элемент за <tex>O(1)</tex>, и идеи Data-structural bootstrapping, позволяющей выполнить <math>\mathrm{merge}</math> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.<br />
<br />
== Структура ==<br />
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping. <br />
{{Определение<br />
|neat = 0<br />
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <math>\mathrm{merge}</math> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.<br />
}}<br />
<br />
<br />
<br />
<br />
<br />
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:<br />
<br />
<tex> BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)</tex><br />
<br />
Куча из одного элемента будет выглядеть так:<br />
<br />
<math> \mathrm{create} </math><tex>(x) = BPQ \left \langle x, null\right \rangle</tex><br />
<br />
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex><br />
<br />
== Операции ==<br />
=== Merge ===<br />
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго BPQ.<br />
<code><br />
'''pair(int, bpq)''' merge((x : '''int''', q : '''bpq''') : '''pair''', (y : '''int''', r : '''bpq''') : '''pair'''):<br />
'''if''' x < y<br />
'''return''' (x, insert(q, (y, r)))<br />
'''else'''<br />
'''return''' (y, insert(r, (x, q)))<br />
</code><br />
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== Insert ===<br />
Это создание нового BPQ и <math>\mathrm{merge}</math> его с основным деревом.<br />
<code><br />
'''pair(int, bpq)''' insert((x : '''int''', q : '''bpq'''), y : '''bpq'''):<br />
return merge((x,q), create(y))<br />
</code><br />
Создание и <math>\mathrm{merge}</math> выполняются за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает за <tex>O(1)</tex>.<br />
<br />
=== getMin ===<br />
Выполняется просто, так как BPQ хранит минимум.<br />
<code><br />
'''int''' getMin((x : '''int''', q : '''bpq''')):<br />
return x;<br />
</code><br />
Очевидно, работает за <tex>O(1)</tex>.<br />
<br />
=== extractMin ===<br />
Минимальный элемент хранится в верхнем BPQ, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди BPQ'ов. <br />
<code><br />
'''pair (int, bpq)''' extractMin('''pair'''(x : '''int''', q : '''bpq''')):<br />
((y,r), t) = extractMin(q)<br />
'''return''' (y, merge(r, t))<br />
</code><br />
Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа BPQ из приоритетной очереди, она возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа BPQ и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <math>\mathrm{merge}</math> функция, выполняющая слияние двух приоритетных очередей.<br />
<br />
Возвращаем BPQ, где <tex>y</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}</math> приоритетная очередь без элемента <tex>y</tex>.<br />
<br />
Так как <math>\mathrm{extractMin}</math> и <math>\mathrm{merge}</math> выполняются за <tex>O(\log N)</tex>, тогда <math>\mathrm{extractMin}</math> выполняется за <tex>O(\log N)</tex>.<br />
<br />
== Смотри также ==<br />
* [[Биномиальная куча]]<br />
* [[Очередь]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентная приоритетная очередь]]<br />
<br />
== Источники информации ==<br />
* [http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]<br />
<br />
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Приоритетные очереди]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%9D%D0%9C_(%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8)&diff=38536СНМ (наивные реализации)2014-06-11T07:44:32Z<p>Nastya: /* С помощью массива */</p>
<hr />
<div>'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами. <br />
__TOC__<br />
== Описание ==<br />
Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1 </tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.<br />
<br />
Определены две операции:<br />
* <math> \mathrm{union(x, y)} </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y </tex><br />
* <math> \mathrm{find (x)} </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x </tex><br />
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.<br />
<br />
[[Файл:DSU_1_Example.png|500px|left|Пример работы СНМ]]<br />
<br clear="all"/><br />
<br />
== Реализации ==<br />
=== С помощью массива ===<br />
<br />
<!--<br />
'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|<tex>O(n)</tex><br />
|}<br />
--><br />
<br />
Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.<br />
<br />
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда <math> \mathrm{union} </math> работает за <tex>O(n)</tex>.<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве </font><br />
</code><br />
<code> <br />
'''int''' find(k):<br />
'''return''' s[k]<br />
</code><br />
<code> <br />
'''func''' union(x, y):<br />
'''if''' s[x] == s[y]<br />
'''return'''<br />
'''else'''<br />
t = s[y]<br />
'''for''' i = 0 '''to''' n - 1<br />
'''if''' s[i] == t<br />
s[i] = s[x]<br />
</code><br />
<br />
=== С помощью списка ===<br />
<!--'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|}--><br />
<br />
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head </tex>. Значит <math> \mathrm{find} </math> работает за <tex> O(1) </tex>.<br />
<br />
Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head </tex>. Таким образом, <math> \mathrm{union} </math> работает за <tex> O(n) </tex>.<br />
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.<br />
<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i].data = i<br />
s[i].next = null<br />
s[i].head = s[i]<br />
</code> <br />
<code><br />
'''int''' find(x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font><br />
'''return''' x.head.data<br />
</code> <br />
<code><br />
'''func''' union('''int''' x, '''int''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font><br />
x = x.head<br />
y = y.head<br />
'''if''' x == y<br />
'''return'''<br />
x.tail.next = y <font color=green> // соединим списки </font><br />
x.tail = y.tail <font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font><br />
'''while''' y <tex> \neq </tex> null <font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font><br />
y.head = x<br />
y = y.next<br />
</code><br />
[[Файл:DSU_list_example.png|800px|left|Пример объединения двух множеств (union)]]<br />
<br clear="all"/><br />
<br />
== Другие реализации ==<br />
* [[СНМ (списки с весовой эвристикой)]]<br />
* [[СНМ (реализация с помощью леса корневых деревьев)]]<br />
<br />
== Источники информации ==<br />
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.<br />
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%9D%D0%9C_(%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8)&diff=38535СНМ (наивные реализации)2014-06-11T07:39:08Z<p>Nastya: /* С помощью списка */</p>
<hr />
<div>'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами. <br />
__TOC__<br />
== Описание ==<br />
Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1 </tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.<br />
<br />
Определены две операции:<br />
* <math> \mathrm{union(x, y)} </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y </tex><br />
* <math> \mathrm{find (x)} </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x </tex><br />
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.<br />
<br />
[[Файл:DSU_1_Example.png|500px|left|Пример работы СНМ]]<br />
<br clear="all"/><br />
<br />
== Реализации ==<br />
=== С помощью массива ===<br />
<br />
<!--<br />
'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|<tex>O(n)</tex><br />
|}<br />
--><br />
<br />
Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.<br />
<br />
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда union работает за <tex>O(n)</tex>.<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве </font><br />
</code><br />
<code> <br />
'''int''' find(k):<br />
'''return''' s[k]<br />
</code><br />
<code> <br />
'''func''' union(x, y):<br />
'''if''' s[x] == s[y]<br />
'''return'''<br />
'''else'''<br />
t = s[y]<br />
'''for''' i = 0 '''to''' n - 1<br />
'''if''' s[i] == t<br />
s[i] = s[x]<br />
</code><br />
<br />
=== С помощью списка ===<br />
<!--'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|}--><br />
<br />
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head </tex>. Значит <math> \mathrm{find} </math> работает за <tex> O(1) </tex>.<br />
<br />
Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head </tex>. Таким образом, <math> \mathrm{union} </math> работает за <tex> O(n) </tex>.<br />
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.<br />
<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i].data = i<br />
s[i].next = null<br />
s[i].head = s[i]<br />
</code> <br />
<code><br />
'''int''' find(x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font><br />
'''return''' x.head.data<br />
</code> <br />
<code><br />
'''func''' union('''int''' x, '''int''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font><br />
x = x.head<br />
y = y.head<br />
'''if''' x == y<br />
'''return'''<br />
x.tail.next = y <font color=green> // соединим списки </font><br />
x.tail = y.tail <font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font><br />
'''while''' y <tex> \neq </tex> null <font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font><br />
y.head = x<br />
y = y.next<br />
</code><br />
[[Файл:DSU_list_example.png|800px|left|Пример объединения двух множеств (union)]]<br />
<br clear="all"/><br />
<br />
== Другие реализации ==<br />
* [[СНМ (списки с весовой эвристикой)]]<br />
* [[СНМ (реализация с помощью леса корневых деревьев)]]<br />
<br />
== Источники информации ==<br />
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.<br />
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%9D%D0%9C_(%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8)&diff=38534СНМ (наивные реализации)2014-06-11T07:35:12Z<p>Nastya: /* С помощью списка */</p>
<hr />
<div>'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами. <br />
__TOC__<br />
== Описание ==<br />
Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1 </tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.<br />
<br />
Определены две операции:<br />
* <math> \mathrm{union(x, y)} </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y </tex><br />
* <math> \mathrm{find (x)} </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x </tex><br />
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.<br />
<br />
[[Файл:DSU_1_Example.png|500px|left|Пример работы СНМ]]<br />
<br clear="all"/><br />
<br />
== Реализации ==<br />
=== С помощью массива ===<br />
<br />
<!--<br />
'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|<tex>O(n)</tex><br />
|}<br />
--><br />
<br />
Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.<br />
<br />
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда union работает за <tex>O(n)</tex>.<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве </font><br />
</code><br />
<code> <br />
'''int''' find(k):<br />
'''return''' s[k]<br />
</code><br />
<code> <br />
'''func''' union(x, y):<br />
'''if''' s[x] == s[y]<br />
'''return'''<br />
'''else'''<br />
t = s[y]<br />
'''for''' i = 0 '''to''' n - 1<br />
'''if''' s[i] == t<br />
s[i] = s[x]<br />
</code><br />
<br />
=== С помощью списка ===<br />
<!--'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|}--><br />
<br />
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head </tex>. Значит <math> \mathrm{find} </math> работает за <tex> O(1) </tex>.<br />
<br />
Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head </tex>. Таким образом, <math> \mathrm{union} </math> работает за <tex> O(n) </tex>.<br />
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.<br />
<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i].data = i<br />
s[i].next = null<br />
s[i].head = s[i]<br />
</code> <br />
<code><br />
'''int''' find(x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font><br />
'''return''' x.head.data<br />
</code> <br />
<code><br />
'''func''' union('''int''' x, '''int''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font><br />
x = x.head<br />
y = y.head<br />
'''if''' x == y<br />
'''return'''<br />
<font color=green> // соединим списки </font><br />
x.tail.next = y<br />
<font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font><br />
x.tail = y.tail<br />
<font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font><br />
'''while''' y <tex> \neq </tex> null<br />
y.head = x<br />
y = y.next<br />
</code><br />
[[Файл:DSU_list_example.png|800px|left|Пример объединения двух множеств (union)]]<br />
<br clear="all"/><br />
<br />
== Другие реализации ==<br />
* [[СНМ (списки с весовой эвристикой)]]<br />
* [[СНМ (реализация с помощью леса корневых деревьев)]]<br />
<br />
== Источники информации ==<br />
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.<br />
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%9D%D0%9C_(%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8)&diff=38533СНМ (наивные реализации)2014-06-11T07:34:41Z<p>Nastya: /* Описание */</p>
<hr />
<div>'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами. <br />
__TOC__<br />
== Описание ==<br />
Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1 </tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.<br />
<br />
Определены две операции:<br />
* <math> \mathrm{union(x, y)} </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y </tex><br />
* <math> \mathrm{find (x)} </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x </tex><br />
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.<br />
<br />
[[Файл:DSU_1_Example.png|500px|left|Пример работы СНМ]]<br />
<br clear="all"/><br />
<br />
== Реализации ==<br />
=== С помощью массива ===<br />
<br />
<!--<br />
'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|<tex>O(n)</tex><br />
|}<br />
--><br />
<br />
Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.<br />
<br />
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда union работает за <tex>O(n)</tex>.<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве </font><br />
</code><br />
<code> <br />
'''int''' find(k):<br />
'''return''' s[k]<br />
</code><br />
<code> <br />
'''func''' union(x, y):<br />
'''if''' s[x] == s[y]<br />
'''return'''<br />
'''else'''<br />
t = s[y]<br />
'''for''' i = 0 '''to''' n - 1<br />
'''if''' s[i] == t<br />
s[i] = s[x]<br />
</code><br />
<br />
=== С помощью списка ===<br />
<!--'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|}--><br />
<br />
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head </tex>. Значит <math> \mathrm{find} </math> работает за <tex> O(1) </tex>.<br />
<br />
Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head </tex>. Таким образом, <math> \mathrm{union} </math> работает за <tex> O(n) </tex>.<br />
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.<br />
<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i].data = i<br />
s[i].next = null<br />
s[i].head = s[i]<br />
</code> <br />
<code><br />
'''int''' find(x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font><br />
'''return''' x.head.data<br />
</code> <br />
<code><br />
'''func''' union('''int''' x, '''int''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font><br />
x = x.head<br />
y = y.head<br />
'''if''' x == y<br />
'''return'''<br />
<font color=green> // соединим списки </font><br />
x.tail.next = y<br />
<font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font><br />
x.tail = y.tail<br />
<font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font><br />
'''while''' y <tex> \neq </tex> null<br />
y.head = x<br />
y = y.next<br />
</code><br />
[[Файл:DSU_list_example.png|800px|left|thumb|Пример объединения двух множеств (union)]]<br />
<br clear="all"/><br />
<br />
== Другие реализации ==<br />
* [[СНМ (списки с весовой эвристикой)]]<br />
* [[СНМ (реализация с помощью леса корневых деревьев)]]<br />
<br />
== Источники информации ==<br />
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.<br />
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%9D%D0%9C_(%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8)&diff=38532СНМ (наивные реализации)2014-06-11T07:33:19Z<p>Nastya: </p>
<hr />
<div>'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами. <br />
__TOC__<br />
== Описание ==<br />
Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1 </tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.<br />
<br />
Определены две операции:<br />
* <math> \mathrm{union(x, y)} </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y </tex><br />
* <math> \mathrm{find (x)} </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x </tex><br />
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.<br />
<br />
[[Файл:DSU_1_Example.png|500px|left|thumb|Пример работы СНМ]]<br />
<br clear="all"/><br />
<br />
== Реализации ==<br />
=== С помощью массива ===<br />
<br />
<!--<br />
'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|<tex>O(n)</tex><br />
|}<br />
--><br />
<br />
Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.<br />
<br />
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда union работает за <tex>O(n)</tex>.<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве </font><br />
</code><br />
<code> <br />
'''int''' find(k):<br />
'''return''' s[k]<br />
</code><br />
<code> <br />
'''func''' union(x, y):<br />
'''if''' s[x] == s[y]<br />
'''return'''<br />
'''else'''<br />
t = s[y]<br />
'''for''' i = 0 '''to''' n - 1<br />
'''if''' s[i] == t<br />
s[i] = s[x]<br />
</code><br />
<br />
=== С помощью списка ===<br />
<!--'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|}--><br />
<br />
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head </tex>. Значит <math> \mathrm{find} </math> работает за <tex> O(1) </tex>.<br />
<br />
Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head </tex>. Таким образом, <math> \mathrm{union} </math> работает за <tex> O(n) </tex>.<br />
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.<br />
<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i].data = i<br />
s[i].next = null<br />
s[i].head = s[i]<br />
</code> <br />
<code><br />
'''int''' find(x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font><br />
'''return''' x.head.data<br />
</code> <br />
<code><br />
'''func''' union('''int''' x, '''int''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font><br />
x = x.head<br />
y = y.head<br />
'''if''' x == y<br />
'''return'''<br />
<font color=green> // соединим списки </font><br />
x.tail.next = y<br />
<font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font><br />
x.tail = y.tail<br />
<font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font><br />
'''while''' y <tex> \neq </tex> null<br />
y.head = x<br />
y = y.next<br />
</code><br />
[[Файл:DSU_list_example.png|800px|left|thumb|Пример объединения двух множеств (union)]]<br />
<br clear="all"/><br />
<br />
== Другие реализации ==<br />
* [[СНМ (списки с весовой эвристикой)]]<br />
* [[СНМ (реализация с помощью леса корневых деревьев)]]<br />
<br />
== Источники информации ==<br />
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.<br />
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%9D%D0%9C_(%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8)&diff=38531СНМ (наивные реализации)2014-06-11T07:30:17Z<p>Nastya: /* С помощью списка */</p>
<hr />
<div>'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами. <br />
__TOC__<br />
== Описание ==<br />
Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1 </tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.<br />
<br />
Определены две операции:<br />
* <math> \mathrm{union(x, y)} </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y </tex><br />
* <math> \mathrm{find (x)} </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x </tex><br />
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.<br />
<br />
[[Файл:DSU_1_Example.png|500px|left|thumb|Пример работы СНМ]]<br />
<br clear="all"/><br />
<br />
== Реализации ==<br />
=== С помощью массива ===<br />
<br />
<!--<br />
'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|<tex>O(n)</tex><br />
|}<br />
--><br />
<br />
Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.<br />
<br />
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда union работает за <tex>O(n)</tex>.<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве </font><br />
</code><br />
<code> <br />
'''int''' find(k):<br />
'''return''' s[k]<br />
</code><br />
<code> <br />
'''func''' union(x, y):<br />
'''if''' s[x] == s[y]<br />
'''return'''<br />
'''else'''<br />
t = s[y]<br />
'''for''' i = 0 '''to''' n - 1<br />
'''if''' s[i] == t<br />
s[i] = s[x]<br />
</code><br />
<br />
=== С помощью списка ===<br />
<!--'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|}--><br />
<br />
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head </tex>. Значит <math> \mathrm{find} </math> работает за <tex> O(1) </tex>.<br />
<br />
Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head </tex>. Таким образом, <math> \mathrm{union} </math> работает за <tex> O(n) </tex>.<br />
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.<br />
<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i].data = i<br />
s[i].next = null<br />
s[i].head = s[i]<br />
</code> <br />
<code><br />
'''int''' find(x): <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font><br />
'''return''' x.head.data<br />
</code> <br />
<code><br />
'''func''' union('''int''' x, '''int''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font><br />
x = x.head<br />
y = y.head<br />
'''if''' x == y<br />
'''return'''<br />
<font color=green> // соединим списки </font><br />
x.tail.next = y<br />
<font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font><br />
x.tail = y.tail<br />
<font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font><br />
'''while''' y <tex> \neq </tex> null<br />
y.head = x<br />
y = y.next<br />
</code><br />
[[Файл:DSU_list_example.png|800px|left|thumb|Пример объединения двух множеств (union)]]<br />
<br clear="all"/><br />
<br />
== Другие реализации ==<br />
* [[СНМ (списки с весовой эвристикой)]]<br />
* [[СНМ (реализация с помощью леса корневых деревьев)]]<br />
<br />
== Источники ==<br />
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.<br />
<br />
== Ссылки ==<br />
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]</div>Nastyahttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%9D%D0%9C_(%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8)&diff=38525СНМ (наивные реализации)2014-06-11T07:10:57Z<p>Nastya: /* С помощью массива */</p>
<hr />
<div>'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами. <br />
__TOC__<br />
== Описание ==<br />
Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1 </tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.<br />
<br />
Определены две операции:<br />
* <math> \mathrm{union(x, y)} </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y </tex><br />
* <math> \mathrm{find (x)} </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x </tex><br />
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.<br />
<br />
[[Файл:DSU_1_Example.png|500px|left|thumb|Пример работы СНМ]]<br />
<br clear="all"/><br />
<br />
== Реализации ==<br />
=== С помощью массива ===<br />
<br />
<!--<br />
'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|<tex>O(n)</tex><br />
|}<br />
--><br />
<br />
Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</tex>.<br />
<br />
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда union работает за <tex>O(n)</tex>.<br />
<code><br />
'''int''' s[n]<br />
'''func''' init():<br />
'''for''' i = 0 '''to''' n - 1<br />
s[i] = i <font color=green> // сначала каждый элемент лежит в своем множестве </font><br />
</code><br />
<code> <br />
'''int''' find(k):<br />
'''return''' s[k]<br />
</code><br />
<code> <br />
'''func''' union(x, y):<br />
'''if''' s[x] == s[y]<br />
'''return'''<br />
'''else'''<br />
t = s[y]<br />
'''for''' i = 0 '''to''' n - 1<br />
'''if''' s[i] == t<br />
s[i] = s[x]<br />
</code><br />
<br />
=== С помощью списка ===<br />
<!--'''Оценка работы:'''<br />
{| class="wikitable" border="1"<br />
|init<br />
|find<br />
|union<br />
|-<br />
|<tex>O(n)</tex><br />
|<tex>O(n)</tex><br />
|<tex>O(1)</tex><br />
|}--><br />
<br />
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на head, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на head. Значит find работает за <tex> O(1) </tex>.<br />
<br />
Для объединения множеств потребуется объединить два списка и обновить ссылки на head. Таким образом, union работает за <tex> O(n) </tex>.<br />
Чтобы объединить два списка, нужно хранить ссылку на tail. Ее можно хранить в голове списка.<br />
<br />
s[n]<br />
init():<br />
for i = 0 to n - 1:<br />
s[i].data = i<br />
s[i].next = null<br />
s[i].head = s[i]<br />
<br />
find(x): // подразумевается, что x {{ --- }} ссылка на один из элементов<br />
return x.head.data<br />
<br />
union(x, y): // x и y {{ --- }} элементы множеств<br />
x = x.head<br />
y = y.head<br />
if x == y:<br />
return<br />
// соединим списки<br />
x.tail.next = y<br />
// сделаем корректную ссылку на tail в head<br />
x.tail = y.tail<br />
// скорректируем ссылки на head у элементов множества "y"<br />
while y != null:<br />
y.head = x<br />
y = y.next<br />
<br />
[[Файл:DSU_list_example.png|800px|left|thumb|Пример объединения двух множеств (union)]]<br />
<br clear="all"/><br />
<br />
== Другие реализации ==<br />
* [[СНМ (списки с весовой эвристикой)]]<br />
* [[СНМ (реализация с помощью леса корневых деревьев)]]<br />
<br />
== Источники ==<br />
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.<br />
<br />
== Ссылки ==<br />
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]</div>Nastya