§ Биномиальная куча (Binomial heap, пирамида) – это эффективно сливаемая куча (mergeable heap). § В биномиальной куче слияние (merge, union) двух куч выполняется за время O(logn).


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Лекция
6
:
Бин1миа0ьные
к6чи
(Binomial heaps)
К63н1с1в
Михаи0 Ге13гиевич
к.5.н. д1цен5 Кафед3ы вычис0и5е0ьных сис5ем
Сиби3ский г1с6да3с5венный 6ниве3си5е5
5е0ек1мм6никаций и инф13ма5ики
Значение
(Value)
П3и13и5е5
(
Priority
)
С01н
3
Ки5
1
Лев
15
Оче3едь с 23и13и5е51м (
Priority queue)
2

Оче3едь с 23и13и5е51м (
Priority queue)

э51 1че3едь
, в к15131й э0емен5ы имею5 23и13и5е5 (вес
)

П1дде3живаемые 12е3ации
:
o
Insert
(
key
,
value
)

д1бав0яе5 в 1че3едь значение
value
c
23и13и5е51м (
вес1м, к0юч1м)
key
o
DeleteMin
/
DeleteMax

6да0яе5 из 1че3еди э0емен5
с мин.
/
макс.
23и13и5е51м (к0юч1м)
o
Min/Max

в1зв3ащае5 э0емен5 с мин.
/
макс. к0юч1м
o
DecreaseKey

изменяе5 значение к0юча
заданн1г1 э0емен5а
o
Merge
(
q
1
,
q
2
)

с0ивае5 две 1че3еди в 1дн6
Дв1ичная к6ча (
Binary
h
eap
)
3

Дв1ичная к6ча (2и3амида, с135и36ющее де3ев1,
binary heap
)

э51 дв1ичн1е де3ев1, 6д1в0е5в13яющее
с0ед6ющим 6с01виям:
a)
23и13и5е5
(
к0юч) 0юб1й ве3шины не меньше (

),
23и13и5е5а её 2151мк1в
b)
де3ев1 яв0яе5ся
210ным дв1ичным
де3ев1м
(
complete
binary
tree
)

все 631вни за210нены
,
в1зм1жн1
за
иск0ючением
21с0еднег1
Дв1ичная к6ча (
Binary
h
eap
)
4
max
-
heap
П3и13и5е5 0юб1й ве3шины
не меньше (

)
,
23и13и5е5а 2151мк1в
min
-
heap
П3и13и5е5 0юб1й ве3шины
не
б10ьше (≤)
,
23и13и5е5а 2151мк1в
Оче3едь с 23и13и5е51м (
Priority queue)
5

В 5аб0ице 23иведены 536д1емк1с5и 12е3аций 1че3еди
с 23и13и5е51м (в х6дшем с06чае,
worst case
)

Симв101м
‘*’
15мечена ам135изи31ванная с01жн1с5ь 12е3аций
О2е3ация
Binary
heap
Binomial
heap
Fibonacci
heap
Pairing
heap
Brodal
heap
FindMin
Θ
(1)
O
(
log
n
)
Θ
(1)
Θ
(1)
*
Θ
(1)
Θ
(
log
n
)
Θ
(
log
n
)
O
(
log
n
)*
O
(
log
n
)*
O
(
log
n
)
Insert
Θ
(
log
n
)
O
(
log
n
)
Θ
(1)
Θ
(1)*
Θ
(1)
DecreaseKey
Θ
(
log
n
)
Θ
(
log
n
)
Θ
(1)*
O
(
log
n
)*
Θ
(1)
Merge/Union
Θ
(
n
)
Ω(
log
n
)
Θ
(1)
Θ
(1)*
Θ
(1)
Бин1миа0ьные к6чи (
Binomial heaps
)
6

Бин1миа0ьная к6ча
(Binomial
heap
, 2и3амида
)

э51 эффек5ивн1
с0иваемая к6ча
(
mergeable
heap)

В бин1миа0ьн1й к6че с0ияние (
merge, union
)
дв6х к6ч
вы210няе5ся за в3емя
O
(
log
n
)

Бин1миа0ьные к6чи ф13ми36ю5ся на 1сн1ве
бин1миа0ьных
де3евьев
(
binomial trees
)
Бин1миа0ьн1е де3ев1 (
Binomial tree
)
7

Бин1миа0ьн1е де3ев1
B
k
(Binomial tree)

э51 3ек63сивн1 123еде0яем1е де3ев1
выс15ы
k
, в к15131м:
o
к10ичес5в1 6з01в 3авн1 2
k
o
к10ичес5в1 6з01в на 631вне
i
= 0, 1, …,
k
:


=

!

!



!
(
к10ичес5в1 с1че5аний из
k
21
i
)
o
к13ень имее5
k
д1че3них
6з01в:

2е3вый д1че3ний 6зе0 (самый 0евый)

де3ев1
B
k
-
1

в5131й д1че3ний
6зе0
(в5131й с0ева)

де3ев1
B
k
-
2



k
-
й д1че3ний
6зе0 (самый
23авый)

де3ев1
B
0
Бин1миа0ьн1е де3ев1 (
Binomial tree
)
8
Бин1миа0ьн1е
де3ев1
B
0
(
n
= 2
0
= 1)
Бин1миа0ьн1е
де3ев1
B
1
(
n
=
2
1
=
2)
Бин1миа0ьн1е
де3ев1
B
2
(
n
=
2
2
=
4)
Бин1миа0ьн1е
де3ев1
B
3
(
n
=
2
3
=
8)
B
3
B
0
B
1
B
0
B
2
B
0
B
1
B
0
B
2
B
0
B
1
B
0
B
1
B
0
B
0

Максима0ьная с5е2ень 6з0а
в бин1миа0ьн1м де3еве
с
n
ве3шинами 3авна
O
(
log
n
)
Бин1миа0ьная к6ча (
Binomial heap
)
9

Бин1миа0ьная к6ча
(Binomial heap)

э51 мн1жес5в1 бин1миа0ьных де3евьев, к1513ые
6д1в0е5в13яю5 св1йс5вам бин1миа0ьных к6ч:
1)
кажд1е
бин1миа0ьн1е
де3ев1 6213яд1чен1
(
ordered
)
в с115ве5с5вии с1 св1йс5вами не6бывающей
и0и нев1з3ас5ающей к6чи (
min
-
heap/max
-
heap
)
:
к0юч 6з0а не меньше
/
не б10ьше к0юча ег1 31ди5е0я
2)
д
0я 0юб1г1 це01г1
k
≥ 0
имее5ся
не б10ее 1дн1г1
бин1миа0ьн1г1 де3ева, чей к13ень имее5 с5е2ень
k

Бин1миа0ьная к6ча с1де3жащая
n
6з01в с1с51и5
не б10ее чем из
log
(

)
+
1
бин1миа0ьных де3евьев
Бин1миа0ьная к6ча (
Binomial heap
)
10
6
29
14
38
8
17
11
27
1
25
12
18
10
Бин1миа0ьная к6ча из
13
6з01в
(
6213яд1ченные бин1миа0ьные де3евья
B
0
,
B
2
и
B
3
)
Бин1миа0ьн1е
де3ев1
B
0
(
n
= 2
0
= 1)
Бин1миа0ьн1е
де3ев1
B
2
(
n
=
2
2
=
4)
Бин1миа0ьн1е
де3ев1
B
3
(
n
=
2
3
=
8)
Бин1миа0ьн1е де3ев1 (
Binomial tree
)
11

П6с5ь бин1миа0ьная к6ча с1де3жи5
n
6з01в

Ес0и за2иса5ь
n
в дв1ичн1й сис5еме исчис0ения,
51 н1ме3а нен60евых би51в б6д65 с115ве5с5в1ва5ь
с5е2еням бин1миа0ьных де3евьев, 1б3аз6ющих к6ч6
6
29
14
38
8
17
11
27
1
25
12
18
10
Бин1миа0ьная к6ча из
13
6з01в (де3евья
B
0
,
B
2
и
B
3
)
13
10
= 1101
2
Бин1миа0ьн1е де3ев1 (
Binomial tree
)
12

К13ни бин1миа0ьных де3евьев бин1миа0ьн1й к6чи
х3аня5ся в 1дн1связн1м с2иске

с2иске к13ней
(
root list
)

В с2иске к13ней
6з0ы 6213яд1чены
21 в1з3ас5анию их
с5е2еней (с5е2еней к13ней бин1миа0ьных де3евьев к6чи)
6
29
14
38
8
17
11
27
1
25
12
18
10
Бин1миа0ьная к6ча из
13
6з01в (де3евья
B
0
,
B
2
и
B
3
)
13
10
= 1101
2
Head
Узе0 бин1миа0ьн1й к6чи
13

Каждый 6зе0 бин1миа0ьн1й к6чи
(бин1миа0ьн1г1 де3ева) с1де3жи5 с0ед6ющие 210я:
parent
key
value
degree
child
sibling
o
key

23и13и5е5 6з0а (вес, к0юч
)
o
v
alue

данные
o
degree

к10ичес5в1 д1че3них 6з01в
o
parent

6каза5е0ь на 31ди5е0ьский 6зе0
o
child

6каза5е0ь на
к3айний
0евый
д1че3ний 6зе0
o
sibling

6каза5е0ь
на 23авый
сес53инский 6зе0
П3едс5ав0ение бин1миа0ьных к6ч
14
10
3
29
0
14
1
38
0
8
2
17
0
11
1
27
0
1
2
25
0
12
1
18
0
10
0
Head
Бин1миа0ьная к6ча из
13
6з01в (де3евья
B
0
,
B
2
и
B
3
)
П1иск минима0ьн1г1
6з0а
(
FindMin
)
15

В к13не кажд1г1 бин1миа0ьн1г1 де3ева х3ани5ся
ег1 минима0ьный
/
максима0ьный к0юч

Д0я 21иска минима0ьн1г1
/
максима0ьн1г1 э0емен5а
в бин1миа0ьн1й к6че 53еб6е5ся 231й5и 21 с2иск6
из
log
(

)
+
1
к13ней
6
29
14
38
8
17
11
27
1
25
12
18
10
Head
П1иск минима0ьн1г1
6з0а
(
FindMin
)
16
function
BinomialHeapMin
(heap)
x = heap
min.key
= Infinity
while
x != NULL
do
if
x.key

min.key
then
min = x
x =
x.sibling
end while
min
end function
6
29
14
38
8
17
11
27
1
25
12
18
10
Head
T
Min
=
O
(
log
n
)
function
BinomialHeapMin
(heap)
x = heap
min.key
= Infinity
while
x != NULL
do
if
x.key

min.key
then
min = x
x =
x.sibling
end while
min
end function
П1иск минима0ьн1г1
6з0а
(
FindMin
)
17
6
29
14
38
8
17
11
27
1
25
12
18
10
Head
Как 3еа0из1ва5ь 21иск
минима0ьн1г1
/
максима0ьн1г1 к0юча за в3емя
O
(1)?
П1дде3жива5ь 6каза5е0ь на к13ень де3ева (6зе0),
в к15131м нах1ди5ся экс53ема0ьный к0юч
T
Min
=
O
(
log
n
)
С0ияние к6ч
(Union)
18

Д0я с0ияния
(union, merge)
дв6х к6ч
H
1
и
H
2
в н1в6ю к6ч6
H
не1бх1дим1:
1.
С0и5ь с2иски к13ней
H
1
и
H
2
в 1дин
6213яд1ченный с2ис1к
2.
В1сс5ан1ви5ь св1йс5ва бин1миа0ьн1й к6чи
H

П1с0е с0ияния с2иск1в к13ней извес5н1, ч51 в к6че
H
имее5ся не б10ее дв6х к13ней с 1динак1в1й с5е2енью
и 1ни с1седс5в6ю5
С0ияние с2иск1в к13ней
19
6
44
10
17
29
31
48
50
3
37
18
8
22
23
24
30
32
45
55
H
2
15
33
28
41
7
25
12
H
1

С2иски к13ней
H
1
и
H
2
6213яд1чены 21 в1з3ас5анию
с5е2еней 6з01в

С0ияние вы210няе5ся ана01гичн1 с0иянию 6213яд1ченных
21дмассив1в
в
MergeSort
(
с135и31вке с0иянием
)
С0ияние с2иск1в к13ней
20
6
44
10
17
29
31
48
50
3
37
18
8
22
23
24
30
32
45
55
15
33
28
41
7
25
12
H

С2иски к13ней
H
1
и
H
2
6213яд1чены 21 в1з3ас5анию
с5е2еней 6з01в

С0ияние вы210няе5ся ана01гичн1 с0иянию 6213яд1ченных
21дмассив1в
в
MergeSort
(
с135и31вке с0иянием
)
С0ияние с2иск1в к13ней
function
BinomialHeapListMerge
(h1, h2)
h = NULL
while
h1 != NULL && h2 != NULL
do
if
h1.degree
= h2.degree
then
LinkedList_AddEnd
(h, h1)
h1 = h1.next
else
LinkedList_AddEnd
(h, h2)
h2 = h2.next
end if
end while
while
h1 != NULL
do
LinkedList_AddEnd
(h, h1)
h1 = h1.next
end while
while
h2 != NULL
do
LinkedList_AddEnd
(h, h2)
h2 = h2.next
end while
h
end function
T
Merge
= O
(log(max(
n
1
,
n
2
)))
21
С0ияние
к6ч
(Union)
22
6
44
10
17
29
31
48
50
3
37
18
8
22
23
24
30
32
45
55
15
33
28
41
7
25
12
H
Си56ация 21с0е с0ияния с2иск1в к13ней

Св1йс5в1 1 бин1миа0ьн1й к6чи вы210няе5ся

Св1йс5в1 2
не вы210няе5ся
:
два де3ева
B
0
и два де3ева
B
1
B
0
B
0
B
1
B
1
B
2
B
4
23
С06чай 3
x.degree
=
next
-
x.degree
≠ next
-
x.sibling.degree
x.key

next
-
x.key
a
b
c
prev
-
x
x
next
-
x
d
a
b
c
prev
-
x
x
next
-
x
d
B
k
B
k
B
l
B
k
B
k
B
l
B
k
+1
x.sibling
= next
-
x.sibling
BinomialTreeLink
(next
-
x, x
)
next
-
x =
x.sibling
С06чай 3
24
6
44
10
17
29
31
48
50
3
37
18
8
22
23
24
30
32
45
55
15
33
28
41
7
25
12
H
x.degree
=
next
-
x.degree
≠ next
-
x.sibling.degree
x.key

next
-
x.key

Де3евья
x
и
next
-
x
связываю5ся

Узе0
next
-
x
с5ан1ви5ся
0евым д1че3ним 6з01м
x
x
next
-
x
x.sibling
= next
-
x.sibling
BinomialTreeLink
(next
-
x, x
)
next
-
x =
x.sibling
С06чай 3
25
6
44
10
17
29
31
48
50
3
37
18
8
22
23
24
30
32
45
55
15
33
28
41
7
25
12
H
x
next
-
x
x.degree
=
next
-
x.degree
≠ next
-
x.sibling.degree
x.key

next
-
x.key
Связывание бин1миа0ьных де3евьев
26
function
BinomialTreeLink
(child, parent)
child.parent
=
parent
child.sibling
=
parent.child
parent.child
=
child
parent.degree
=
parent.degree
+ 1
end function
T
TreeLink
= O
(1)
10
0
parent
child
z.child
С06чай 2
27
a
b
c
prev
-
x
x
next
-
x
d
a
b
c
prev
-
x
x
next
-
x
d
B
k
B
k
B
k
B
k
B
k
B
k
x.degree
=
next
-
x.degree
=
next
-
x.sibling.degree
/*
Перемещаем указатели по списку корней
*/
prev
-
x = x
x = next
-
x
next
-
x =
x.sibling
С06чай 2
28
x.degree
=
next
-
x.degree
=
next
-
x.sibling.degree
/*
Перемещаем указатели по списку корней
*/
prev
-
x = x
x = next
-
x
next
-
x =
x.sibling
6
44
10
17
29
31
48
50
3
37
18
8
22
23
24
30
32
45
55
15
33
28
41
7
25
12
H
x
next
-
x
prev
-
x
29
prev
-
x.sibling
= next
-
x
BinomialTreeLink
(x
,
next
-
x)
x
= next
-
x
next
-
x =
x.sibling
С06чай
4
x.degree
=
next
-
x.degree
≠ next
-
x.sibling.degree
x.key

next
-
x.key
a
b
c
prev
-
x
x
next
-
x
d
a
c
b
prev
-
x
x
next
-
x
d
B
k
B
k
B
l
B
k
B
k
B
l
B
k
+1
С06чай
1
30
x.degree

next
-
x.degree

Узе0
x

к13ень де3ева
B
k

Узе0
next
-
x

к13ень де3ева
B
l
,
l

k
/*
Перемещаем указатели по списку корней
*/
prev
-
x = x
x = next
-
x
next
-
x =
x.sibling
a
b
c
prev
-
x
x
next
-
x
d
a
b
c
prev
-
x
x
next
-
x
d
B
k
B
l
B
k
B
l
l

k
С0ияние
бин1миа0ьных к6ч
(Union)
function
BinomialHeapUnion
(h1, h2)
h =
BinomialHeapListMerge
(h1, h2)
prev
-
x = NULL
x = h
next
-
x =
x.sibling
while
next
-
x != NULL
do
if
(
x.degree
!= next
-
x.degree
)
OR
(next
-
x.sibling
!= NULL
AND
next
-
x.sibling.degree
=
x.degree
)
then
prev
-
x = x
/*
Случаи 1 и 2
*
/
x = next
-
x
else if
x.key
= next
-
x.key
then
x.sibling
=
next
-
x.sibling
/*
Случай 3
*/
BinomialTreeLink
(next
-
x, x)
31
С0ияние
бин1миа0ьных к6ч
(Union)
else
/*
Случай
4
*/
if
prev
-
x = NULL
then
h = next
-
x
else
prev
-
x.sibling
= next
-
x
end if
BinomialTreeLink
(x, next
-
x)
x = next
-
x
end if
next
-
x =
x.sibling
end while
h
end function
32
T
Union
= O
(
log
n
)
С0ияние
бин1миа0ьных к6ч
(Union)
33

Вычис0и5е0ьная с01жн1с5ь с0ияния дв6х
бин1миа0ьных к6ч в х6дшем с06чае 3авна
O
(log(
n
))

Д0ина с2иска к13ней не 23евышае5
log(
n
1
) + log(
n
1
) + 2 ≤ log(
n
) + 2 =
O
(log(
n
))

Цик0
while
в ф6нкции
BinomialHeapUnion
вы210няе5ся
не б10ее
O
(log(
n
))
3аз

На кажд1й и5е3ации цик0а 6каза5е0ь 2е3емещае5ся
21 с2иск6 к13ней в23ав1 на 1дн6 21зицию и0и 6да0яе5ся
1дин 6зе0

э51 53еб6е5 в3емени
O
(1)
Вс5авка 6з0а
(Insert)
34

С1здаем бин1миа0ьн6ю к6ч6 из 1дн1г1 6з0а
Z
x

бин1миа0ьн1г1 де3ева
B
0

С0иваем исх1дн6ю к6ч6
H
и к6ч6 из 6з0а
x
function
BinomialHeapInsert
(h, key, value)
x.key
= key
x.value
= value
x.degree
= 0
x.parent
= NULL
x.child
= NULL
x.sibling
= NULL
return
BinomialHeapUnion
(h, x)
end function
T
Insert
= O
(
log
n
)
Уда0ение минима0ьн1г1 6з0а
(
DeleteMin
)
35
1.
В с2иске к13ней к6чи
H
15ыскиваем к13ень
x
с минима0ьным к0юч1м и 6да0яем
x
из с2иска к13ней
(3аз3ывам связь)
2.
Инициа0изи36ем 26с56ю к6ч6
Z
3.
Меняем 213яд1к с0ед1вания д1че3них 6з01в к13ня
х
на 1б3а5ный, 6 кажд1г1 д1че3нег1 6з0а 6с5анав0иваем
210е
parent
в
NULL
4.
Ус5анав0иваем заг101в1к к6чи
Z
на 2е3вый э0емен5
н1в1г1 с2иска к13ней
5.
С0иваем к6чи
H
и
Z
6.
В1зв3ащаем
x
Уда0ение минима0ьн1г1 6з0а
(
DeleteMin
)
36
1
25
12
18
16
33
26
42
37
41
6
29
14
38
8
17
11
27
10
13
28
77
H

В с2иске к13ней к6чи
H
15ыскиваем к13ень
x
с минима0ьным к0юч1м и 6да0яем
x
из с2иска к13ней
(3аз3ывам связь)
x
Уда0ение минима0ьн1г1 6з0а
(
DeleteMin
)
37
1
25
12
18
16
33
26
42
37
41
6
29
14
38
8
17
11
27
10
13
28
77
H

Меняем 213яд1к с0ед1вания д1че3них 6з01в к13ня
х
на 1б3а5ный, 6 кажд1г1 д1че3нег1 6з0а 6с5анав0иваем
210е
parent
в
NULL

Д1че3ние 6з0ы к13ня
x
1б3аз6ю5 бин1миа0ьн6ю к6ч6
Z
x
Уда0ение минима0ьн1г1 6з0а
(
DeleteMin
)
38
25
12
18
16
33
26
42
37
41
6
29
14
38
8
17
11
27
10
13
28
77
H

С0иваем к6чи
H
и
Z
Z
Уда0ение минима0ьн1г1 6з0а
(
DeleteMin
)
function
BinomialHeapDeleteMin
(h)
/* Lookup and unlink min node */
x = h
xmin.key
=
Infinitya
prev
= NULL
while
x != NULL
do
if
x.key

xmin.key
then
xmin
= x
prevmin
=
prev
end if
prev
= x
x =
x.sibling
end while
if
prevmin
!= NULL
then
prevmin.sibling
=
xmin.sibling
else
h =
xmin.sibling
39
Уда0ение минима0ьн1г1 6з0а
(
DeleteMin
)
/* Reverse linked list */
child =
xmin.child
prev
= NULL
while
child != NULL
do
sibling =
child.sibling
child.sibling
=
prev
prev
= child
child = sibling
end while
return
BinomialHeapUnion
(h,
prev
)
end function
40
T
= O
(
log
n
)
Уменьшение к0юча
(
DecreaseKey
)
41
1.
П106чаем 6каза5е0ь на 6зе0
x
и изменяем 6 нег1 к0юч
(
newkey
=
x
.
key
)
2.
П
31ве3яем значение к0юча 31ди5е0ьск1г1 6з0а,
ес0и 1н меньше к0юча
x
, 51 вы210няем 1бмен к0ючей
(
и
данных
)
, 21в513яем 1бмены 21ка не 21днимемся д1 к13ня
5ек6щег1 бин1миа0ьн1г1 де3ева
6
29
14
38
8
17
5
27
1
25
12
18
10
Head
x
p
Уменьшение к0юча
(
DecreaseKey
)
42
function
BinomialHeapDecreaseKey
(h, x, key)
if
x.key
k
then
return
Error
x.key
= key
y = x
z =
y.parent
while
z != NULL
AND
y.key

z.key
do
temp =
y.key
y.key
=
z.key
z.key
= temp
y = z
z =
y.parent
end while
end function
T
DecreaseKey
= O
(
log
n
)
Уда0ение 6з0а
(Delete)
43
function
(h, x)
BinomialHeapDecreaseKey
(h, x,
-
Infinity
)
BinomialHeapDeleteMin
(h)
end function
T
= O
(
log
n
)
Узе0 бин1миа0ьн1г1 де3ева
struct
bmheap
{
int
key;
char
*value;
int
degree;
struct
bmheap
*parent;
struct
bmheap
*child;
struct
bmheap
*sibling;
};
44
П3име3 ис210ьз1вания
bmheap
int
main
()
{
struct
bmheap
*h = NULL, *node;
h =
bmheap_insert
(h, 10,
“10”
);
h =
bmheap_insert
(h, 12,
“12”
);
h =
bmheap_insert
(h, 3,
“3”
);
h =
bmheap_insert
(h, 56,
“56”
);
node =
bmheap_min
(h);
printf
(
"Min = %d
\
n"
, node
-
�key);
h =
(h);
bmheap_free
(h);
0;
}
45
С1здание 6з0а бин1миа0ьн1г1 де3ева
struct
bmheap
*
bmheap_create
(
int
key,
char
*value)
{
struct
bmheap
*h;
h = (
struct
bmheap
*)
malloc
(
sizeof
(*h));
if
(h != NULL) {
h
-
�key = key;
h
-
�value = value;
h
-
�degree = 0;
h
-
�parent = NULL;
h
-
�child = NULL;
h
-
�sibling = NULL;
}
h;
}
46
П1иск минима0ьн1г1 э0емен5а
struct
bmheap
*
bmheap_min
(
struct
bmheap
*h)
{
struct
bmheap
*
minnode
, *node;
int
minkey
= ~0U �� 1;
/* INT_MAX */
for
(node = h; node != NULL;
node = node
-
�sibling)
{
if
(node
-
�key
minkey
) {
minkey
= node
-
�key;
minnode
= node;
}
}
minnode
;
}
47
С0ияние бин1миа0ьных к6ч
struct
bmheap
*
bmheap_union
(
struct
bmheap
*
a,
struct
bmheap
*b)
{
struct
bmheap
*h, *
prevx
, *x, *
nextx
;
h =
bmheap_mergelists
(a, b);
prevx
= NULL;
x = h;
nextx
= h
-
�sibling;
while
(
nextx
!= NULL) {
if
((x
-
�degree !=
nextx
-
�degree) ||
(
nextx
-
�sibling != NULL &&
nextx
-
�sibling
-
�degree == x
-
�degree))
{
/* Cases 1 & 2 */
prevx
= x;
x =
nextx
;
}
48
С0ияние бин1миа0ьных к6ч
else if
(x
-
�key =
nextx
-
�key) {
/* Case 3 */
x
-
�sibling =
nextx
-
�sibling;
bmheap_linktrees
(
nextx
, x);
}
else
{
/* Case 4 */
if
(
prevx
== NULL) {
h =
nextx
;
}
else
{
prevx
-
�sibling =
nextx
;
}
bmheap_linktrees
(x,
nextx
);
x =
nextx
;
}
nextx
= x
-
�sibling;
}
return
h;
}
49
С0ияние с2иск1в к13ней
struct
bmheap
*
bmheap_mergelists
(
struct
bmheap
*
a,
struct
bmheap
*b)
{
struct
bmheap
*head, *sibling, *end;
end = head = NULL;
while
(a != NULL && b != NULL) {
if
(a
-
�degree b
-
�degree) {
sibling = a
-
�sibling;
if
(end == NULL) {
end = a;
head = a;
}
else
{
end
-
�sibling = a
;
/* Add to the end */
end = a;
a
-
�sibling = NULL;
}
a = sibling;
}
50
С0ияние с2иск1в к13ней
else
{
sibling = b
-
�sibling;
if
(end == NULL) {
end = b;
head = b;
}
else
{
end
-
�sibling = b;
/*
Add to the end */
end = b;
b
-
�sibling = NULL;
}
b = sibling;
}
}
51
С0ияние с2иск1в к13ней
while
(a != NULL) {
sibling = a
-
�sibling;
if
(end == NULL) {
end = a;
}
else
{
end
-
�sibling = a;
end = a;
a
-
�sibling = NULL;
}
a = sibling;
}
52
С0ияние с2иск1в к13ней
while
(b != NULL) {
sibling = b
-
�sibling;
if
(end == NULL) {
end = b;
}
else
{
end
-
�sibling = b;
end = b;
b
-
�sibling = NULL;
}
b = sibling;
}
head;
}
53
Связывание де3евьев
void
bmheap_linktrees
(
struct
bmheap
*
y,
struct
bmheap
*z)
{
y
-
�parent = z;
y
-
�sibling = z
-
�child;
z
-
�child = y;
z
-
�degree++;
}
54
Вс5авка э0емен5а в бин1миа0ьн6ю к6ч6
struct
bmheap
*
bmheap_insert
(
struct
bmheap
*h,
int
key,
char
*value)
{
struct
bmheap
*node;
if
((node =
bmheap_create
(key, value)) == NULL)
return
NULL;
if
(h == NULL)
return
node;
bmheap_union
(h, node);
}
55
Уда0ение минима0ьн1г1 э0емен5а
struct
bmheap
*
bmheap_deletemin
(
struct
bmheap
*h)
{
struct
bmheap
*x, *
prev
, *
xmin
, *
prevmin
,
*child, *sibling;
int
minkey
= ~0U �� 1;
/* INT_MAX */
/* Lookup and unlink min node */
x = h;
prev
= NULL;
while
(x != NULL) {
if
(x
-
�key
minkey
) {
minkey
= x
-
�key;
xmin
= x;
prevmin
=
prev
;
}
prev
= x;
x = x
-
�sibling;
}
56
Уда0ение минима0ьн1г1 э0емен5а
if
(
prevmin
!= NULL)
prevmin
-
�sibling =
xmin
-
�sibling;
else
h =
xmin
-
�sibling;
/* Reverse linked list */
child =
xmin
-
�child;
prev
= NULL;
while
(child != NULL) {
sibling = child
-
�sibling;
child
-
�sibling =
prev
;
prev
= child;
child = sibling;
}
free(
xmin
);
bmheap_union
(h,
prev
);
}
57
Задания
58

П31чи5а5ь 1 0ев1с5131нней 1че3еди (
Leftist heap
)

П31чи5а5ь 1 ск1шенн1й 1че3еди (
Skew heap
)

П31чи5а5ь 1
к6че
Б31да0а
(
Brodal
heap)

Приложенные файлы

  • pdf 3187681
    Размер файла: 781 kB Загрузок: 0

Добавить комментарий