Кучи с эффективным слиянием

План

Задача и применение

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

Биномиальные кучи

Биномиальная куча: лес, состоящий из биномиальных деревьев

Биномиальные деревья

subgraph k = 2
D(( ))
D --- E(( ))
D --- F(( ))
F --- G(( ))
end

subgraph k = 1
B(( ))
B --- C(( ))
end

subgraph k = 0
A(( ))
end

</figcaption>

Биномиальные деревья

Биномиальное дерево порядка \(0\) состоит из одной вершины, а биномиальное дерево порядка \(k\) является объединением двух деревьев порядка \(k - 1\) так, что корень одного из них является сыном корня другого.

Биномиальные кучи

A --- B(( ))
A --- C(( ))
A --- D(( ))
A --- E(( ))
A --- F(( ))

C --- G(( ))
D --- H(( ))
D --- J(( ))
E --- I(( ))
E --- K(( ))
E --- L(( ))
F --- M(( ))
F --- N(( ))
F --- O(( ))
F --- P(( ))

J --- Q(( ))
K --- R(( ))
L --- S(( ))
L --- T(( ))
N --- U(( ))
O --- V(( ))
O --- W(( ))
P --- X(( ))
P --- Y(( ))
P --- Z(( ))

T --- a(( ))
W --- b(( ))
Y --- c(( ))
Z --- d(( ))
Z --- e(( ))

e --- f(( ))

classDef zero  fill:LightCoral
classDef one   fill:SpringGreen
classDef two   fill:SkyBlue
classDef three fill:MediumPurple
classDef four  fill:#b666d2

class A zero
class B,C,D,E,F one
class G,H,J,I,K,L,M,N,O,P two
class Q,R,S,T,U,V,W,X,Y,Z three
class a,b,c,d,e four

</figcaption>

Хранение и адресация

Хранение в виде массива: корень хранится в нулевом элементе и для \(i\)-го элемента его дети имеют индексы \(i + 2^j\), где \(j < k_i\) степени ветвления вершины \(i\).

Хранение и адресация

A --- B((1))
A --- C((2))
A --- D((4))
A --- E((8))

C --- F((3))
D --- G((5))
D --- H((6))
E --- J((9))
E --- I((10))
E --- K((12))

H --- L((7))
I --- M((11))
K --- N((13))
K --- O((14))

O --- P((15))

classDef zero  fill:LightCoral
classDef one   fill:SpringGreen
classDef two   fill:SkyBlue
classDef three fill:MediumPurple
classDef four  fill:#b666d2

class A zero
class B,C,D,E one
class F,G,H,J,I,K two
class L,M,N,O three
class P four

</figcaption>

Хранение и адресация

Left-Child, Right-Sibling (LCRS)

A --> B(( ))
B -.-> C(( ))
C -.-> D(( ))
D -.-> E(( ))

C --> F(( ))
D --> G(( ))
G -.-> H(( ))
E --> J(( ))
J -.-> I(( ))
I -.-> K(( ))

H --> L(( ))
I --> M(( ))
K --> N(( ))
N -.-> O(( ))

O --> P(( ))

classDef zero  fill:LightCoral
classDef one   fill:SpringGreen
classDef two   fill:SkyBlue
classDef three fill:MediumPurple
classDef four  fill:#b666d2

class A zero
class B,C,D,E one
class F,G,H,J,I,K two
class L,M,N,O three
class P four

</figcaption>

Хранение и адресация

Left-Child, Right-Sibling (LCRS)

A --> B(( ))
B -.-> C(( ))
C -.-> D(( ))
D -.-> A

C --> E(( ))
E -.-> C
D --> F(( ))
F -.-> G(( ))
G -.-> D

G --> H(( ))
H -.-> G

classDef zero  fill:LightCoral
classDef one   fill:SpringGreen
classDef two   fill:SkyBlue
classDef three fill:MediumPurple

class A zero
class B,C,D one
class E,F,G two
class H three

</figcaption>

Биномиальные кучи

</figcaption>

Биномиальные кучи

</figcaption>

Слияние биномиальных куч

</figcaption>

Слияние биномиальных куч

</figcaption>

Слияние биномиальных куч

</figcaption>

Слияние биномиальных куч

</figcaption>

Слияние биномиальных куч

</figcaption>

Слияние биномиальных куч

Результирующий набор деревьев

Слияние биномиальных куч

Слияние двух деревьев операция константной сложности:

выбрать минимум из двух корней;
назначить меньший корень родителем большего;

Слияние двух лесов из \(n\) и \(m\) элементов равна \(O(\log \max (n, m))\).

Учётная стоимость вставки равна \(O(1)\).

Извлечение минимума

</figcaption>

Извлечение минимума

</figcaption>

Левацкие кучи

Ранг вершины: высота полного двоичного поддерева с корнем в этой вершине.

Левацкие кучи

classDef zero opacity:0.3,fill:LightCoral
class O,U,Y,a zero
classDef one   fill:SpringGreen
class G,J,K,M,N,P,Q,R,S,T,V,W,X,Z one
classDef two   fill:SkyBlue
class C,E,F,H,I,L two
classDef three fill:MediumPurple
class A,B,D three

</figcaption>

Левацкие кучи

</figcaption>

Левацкие кучи

Также будем обозначать через \(x(A, B)\) дерево с корнем в вершине \(x\) с двумя поддеревьями: \(A\) и \(B\), левым и правым соответственно.

</figcaption>

Левацкие кучи

\begin{gathered}
    \meld(A, \varnothing) = \meld(\varnothing, A) = A,\\
    \\
    \\
    \meld(x(A, B), y(C, D)) = \begin{cases}
        x(A, \meld(B, y(C, D))), &\text{если } x \leqslant y;\\
        y(C, \meld(D, x(A, B))), &\text{иначе}.
    \end{cases}
\end{gathered}

]

Левацкие кучи

</figcaption>

</figcaption>

Левацкие кучи

</figcaption>

Левацкие кучи

</figcaption>

Левацкие кучи

Осталось развернуть.

Косые кучи

Рандомизированные кучи

Дополнительное чтение

Vuillemin, Jean. “A data structure for manipulating priority queues.” Communications of the ACM. vol. 21, no. 4, 1978, pp. 309–315.
Fredman, Michael L., and al. “The pairing heap: a new form of self-adjusting heap.” Algorithmica. vol. 1, no. 1, 1986, pp. 111–129.
Crane, Clark A. Linear Lists and Priority Queues as Balanced Binary Trees Ph.D. thesis. Department of Computer Science, Stanford University, 1972.

Дополнительное чтение

Sleator, Daniel Dominic and Tarjan, Robert Endre. “Self-Adjusting Heaps.” SIAM Journal on Computing. vol. 15, no. 1, 1986, pp. 52–69.
Gambin, A. and Malinowski, A. “Randomized Meldable Priority Queues.” Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics: Theory and Practice of Informatics (SOFSEM ‘98). Ed. Branislav Rovan, 1998, pp. 344-349.