Introduction to Algorithms, Third Edition



Download 4,84 Mb.
Pdf ko'rish
bet341/618
Sana07.04.2022
Hajmi4,84 Mb.
#534272
1   ...   337   338   339   340   341   342   343   344   ...   618
Bog'liq
Introduction-to-algorithms-3rd-edition

mergeable max-heap
with the operations M
AXIMUM
, E
XTRACT
-M
AX
,
and I
NCREASE
-K
EY
.


506
Chapter 19
Fibonacci Heaps
Binary heap
Fibonacci heap
Procedure
(worst-case)
(amortized)
M
AKE
-H
EAP
‚.1/
‚.1/
I
NSERT
‚.
lg
n/
‚.1/
M
INIMUM
‚.1/
‚.1/
E
XTRACT
-M
IN
‚.
lg
n/
O.
lg
n/
U
NION
‚.n/
‚.1/
D
ECREASE
-K
EY
‚.
lg
n/
‚.1/
D
ELETE
‚.
lg
n/
O.
lg
n/
Figure 19.1
Running times for operations on two implementations of mergeable heaps. The num-
ber of items in the heap(s) at the time of an operation is denoted by
n
.
As the table in Figure 19.1 shows, if we don’t need the U
NION
operation, ordi-
nary binary heaps, as used in heapsort (Chapter 6), work fairly well. Operations
other than U
NION
run in worst-case time
O.
lg
n/
on a binary heap. If we need
to support the U
NION
operation, however, binary heaps perform poorly. By con-
catenating the two arrays that hold the binary heaps to be merged and then running
B
UILD
-M
IN
-H
EAP
(see Section 6.3), the U
NION
operation takes
‚.n/
time in the
worst case.
Fibonacci heaps, on the other hand, have better asymptotic time bounds than
binary heaps for the I
NSERT
, U
NION
, and D
ECREASE
-K
EY
operations, and they
have the same asymptotic running times for the remaining operations. Note, how-
ever, that the running times for Fibonacci heaps in Figure 19.1 are amortized time
bounds, not worst-case per-operation time bounds. The U
NION
operation takes
only constant amortized time in a Fibonacci heap, which is significantly better
than the linear worst-case time required in a binary heap (assuming, of course, that
an amortized time bound suffices).

Download 4,84 Mb.

Do'stlaringiz bilan baham:
1   ...   337   338   339   340   341   342   343   344   ...   618




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish