> n:.i!bRPNG
IHDR7 pHYstIME
$tEXtCommentCreated with The GIMPd%nPLTEٟIDATh1k0p_ CںGh!:@C.dxCפSə,cŪ}MOzC&KLx,H%2Q
x7퓖[Jͽ^somcOg{
=;Za:fT<>]nSo6!eZL\ȫ)hS^LuĞ/52"ڑ<@ov\R3RϹ)ruşMro;}.kXL:cTPQ^NPa&K
irǁϿn,SH"`q9::rP埽J{Qn?ꯗw}˻R~ΩN:(\=e(hH⽤aB,x)XI<=yP{HAUc'QN*R>ΐ_QSF[1MΊ;%
˨J)Z Z8hrVyP
70eY(SۇG 8hro*($g=ſL"ERʹ`ʉ!Qʢuqv*dTq1o/'6JnSYBh %J
VA72.։2KY'gHHʓ6TVifAY&XwlH3՝MM ,.֨O:4i",%nzybr枩D)9KHqIFUr?Q&WgT4oUB5D*3f%Q6}!]1UA5O
&g)%PNBi_8vFG3v/Rw+o,fYwV)`ղKrL9~`,F+ML~R(~p}5NJejEB)09k):=9LEJDuF2O(
PTD %P.+_2IL3o)
pFUK5 uvyOw4ӝ9 BĻN
@!`or9::::ƨ`vPJDIENDB`nPBw_=vV)#PNG
IHDRFQEU pHYstIME/ GtEXtCommentCreated with The GIMPd%n PLTEǯ{
RIDATx(@iRu/+2O#)W."0ȴg{+g&˘g A2}~Z^n_A%5?4XDkhyhxI
L05puq؍@f4ra*@¥Q4_f`p5⓭hk4_fl6߸qQPgOh)ƥz:Yᗃrwu=H}~H "4Y+ &%.iPrF$yH2dRܬxS6>]7J2jTƽ9XlDFQ1)):fn U%[ڜA9EgaVx
e?Yйo.
e&.W!1$+y)݃ADzBW8SA2Lt!WIH Kt:Յ_Z5P.ɧ@T<NFׁs
L
Eks.HX{=HsAhʠ)h̥ Yu "Pk@Yo$ٖ236;.2hmق@tZAa~stc2yeRHjj SwXlqZ
s@;vɂŠuUY7!N+e2)e
R5B5Tid?CgAX +H@%
N۹<hxH4q1A&FwsPF5byŠ\r<ye{ƻFw1xNuK@۟$Ηd;twiAdY8A֚+9n ,;Y~ԈAMY@qd*ndIu<
b)5܄zo=H4bN)5ٺ
d^RЭ`2$oi]r v"d~#U$`0<`IR#ʟC3uE
p%DE7r;݆M;Uwu$6iTu&&5Cte@uq
@$9.]ImZ+n W%?7φ*Q.'ۃ\XnA&ddoă'_G2Au` 7^@7~{.8ZR(hY[Ӡrx9Vnݜ0ߦ\pl244'?@c.80WTo 5֏mM!94et@eօ(3bĎ@8D$"d28@.ɲ5rQ.l \yY%3M$Z,I<\&*HՎZsAXBh #_9m(H :$)P7^*AtR:%vH$/vDڈ
d2Gȁt[E肄v unP2ys@@i#=b0H@i#% (HA^ݎi#^9l>JRkԁ73&@Jv؊S#LHnaJ;or u@$h#<4:#и"hlIR%i=H
,z=HVXܺ*n=x'W#(h!zmG(*=Kŋz'NBS@ZVA2˃P#eA%ӛ7Mbp+Yѕ!x .=+q(_고Xpvxv)'ʂ BvcKh3^v\djPVx
%l@Y_*>#q#(>]( glC,s+'(gYArh`Ay^07}zI_hA!(cZa(~n\@odH@kAok(?DНD$r,ȉ>4Tt{
w+[h#{ `[/[էVkedC7H]u.&ceo}ˍT5+c[4!o@\I@rF;#Wvu'#G8ǣ)Q;xx3(iS>oѢ
AՀ!$\#PJp0s(QbzTW< bq{TywFJ3
`=4T돇A
Ƙ$ 4tɘ7VA6Qϴء*mjOzXqo@io,v.Pt:i
$AngڝҶ~PCbw߷HtΜ6r9v[WuLhpTTZbYA@NFncuh3thEa%
\˹
2hB}g9>GQ%rBޏ[':A¯Fx(ڻ)B\sc 3' XQ2h:ϣ@e&3A+TvlQd="mYvv/KrAJ^I_R[hÝNstVeճ*2M;R'm`3gY%RfuOn˃fu4oܒIc,ѯ,rrRc2.'(٤{th<j8F7$hdE>3AsI.P~
40
pZ3AOT
?
e"!q$tj+
ڿ¡7+H~rz]%Yb"AP#
\\\\\Fzs1vǃ^}`¼(IENDB`nOO/@Ady} PNG
IHDR;+ pHYstIME
1.g<tEXtCommentCreated with The GIMPd%nPLTEٟPIDAThڽF` *Tu<9kp\!ʉ`GPG0,X^"NWH
rR"I'vvF
H#6:wG?uwЀh3VNbbuz7;6
vbumKxԆL<u݂Oa؆]nACdsA[+Q qTE:{rWVT%tO*ݽx1,Vh5GDMS>$>t7'ՀZ7~Gć[WQy3`D%&
ccSǞz1S9Q$Q
!O6($;+;
sZLc{G[Xe3۩}Dp&[Aǰ0#mV:
J"BpFD8Qd
6@dHX!"1J((#F9D''>Q
?IjIO@ǉrR2"bQQID]~((Q%
QKDPQBD)Fm1ʉ$"(DIB&QDID8QNcQQFD[r"*0*H'J!Elh.e
ʆ揱}$kU6Ga@vt0Ȕ
7_S6]~Fl ;lHZ.d
a.#S6LoNӵK(2xbdëʆՕ;9{xzY9QQDKJPaKH N3dO9܃';܈}U
E{z{lH DeC63X[$䫯j}rB/]
ɵV}FՈHԽɀ4
h@~ЌiHW6m#ˆ$$}#&ypQ+8T8e.ٛ9 ]Z~ڟ\e7DߩYDDt@͛/Kgby늆8B?#uQGszo أ
rЗAo[< eY+N(̆l'DdYB4YFm@7<_YIENDB`nYL2.1aPNG
IHDR͌) pHYstIME
tEXtCommentCreated with The GIMPd%nPLTEٟIDATh?o8p2jC9kQ {plQuxMEQAƌw[ACd&TG;5?X %e$dtKtZ>Ik[%G?yP1nNDMWT!+6%~3S)Jt&"AΫ1Zj漻_8ۈc^Θ@8[ziDʼSVm`@!C)ЉjK9(`[>$Oxu/]M5ﾹ[FŮ]n閃ls+lxlB%Xd5d.Ɏ][Zen;ڿg\͆``)3M3V3L}{1Rܮ)So)!r6.vlq_4亞Μ\?2}Z(YGnbцXʑih@
=SaSHJ}R8#ru]~1lFyTNg3~Y;Wuװ푺,Qy?]UU0ۗ=c7[`
&voЌNMh¨f#dfln66vſ8[Z[Z4&6B!6vf3lc7[`
͒:Glmln66v, 4@V2Y`{!+loln66vVtXuqd2/r=Fzqj9]GzEfߜܸss㲞8˝9k!Q9o\GZNr=8g\;yWdhsNfч[䀇muO4qs:@n[Jk[ֶmcȑ9uɍ9VwuI͇L~`͇&J>Oe9ʠxgjL_
]vjZ9[u]2Ѵto)(F{'ߞ~ŜLoF,r:xs:?h:YtZm椵'KkMtIENDB`nS˫[8ŗtc'PNG
IHDRFO pHYstIME
(ԏHrtEXtCommentCreated with The GIMPd%n PLTEǯ{gIDATxMn* RH,NM3R>ȫOX!N]);E1+pAsO/Ʋ/<~~1ށћ(LBwq}o^~`'Fޘ1knoP:@M}B3\E ͝NuQ'^}
&<2BbOXS7"^L.,'adɦ}cLXԷэonǶsuY'݂036]Ǹ=b܌#WԼPX[qˠtx:j3ځu724^[_(`\8=;#EmLӎT`Ĥ(M{O*0r'eZExSfteK{7v`Hg
@Ex$/³t0Swwb@X0:,(D9'0 @L?1r`N``ʁH0QD+DX3P9g0r`ݰQ$ͨH9 ƒ1r`Na ir`2bd
(($FU
cU,IV99FI"fXnXa8Q,
S14r`֘QU1Y+`Z9kDZ9`T`1TJ9
zXFKfXSakY^,yݜ}nb>O+=Ж3I0vmkԶ0m?Ǘv"l`wg?KBM˸gG5bo(7;FhcԶ,
L1m6uN>oFc%oycۯG<0Nc8`6
7n7q>"0b#1ah1A+4+X'K⨕1_ xL{,%L4h7ԠӬ('=aGcWl
w>eL!Y% a[L/7=8}Lqåi
,'+>=,3vJ\;I?ʒg2ߟlAv5lʡ=3oUoT: D&l^#fP>bjf0s#v1ܕku7ku
&L0ƒNV61:LyY0iZe5ɮR:ԕ \=:Z$ϳE:"2t b@.=Pa,ߎ&ءO0qd ;^v";86E
< m08tqF']ekeofee7KI0dq!F1ݎ``(^v(K1s,#`H۫s4LkmO$oL5"P:Lv&)2}6n@Ďw}ݨ9&pg何5*4yo.gY
{/%Gۏ"(QJ:hk< Vy@cVv4 98H3trű/iT=M5,1}yEyM0!CXt´~vִc1gL_<g0W`ݘIu~}ԠOa_`do 4Fw7a\V+9 Kޏ5&C=لOF
ztSȄq_3Fk͕l++XZcߕ&`r.`q)w._(1N57o7/0a.~1Q{9pڂ_6W?IENDB`n
_1(
`/0DArialw(0(B 0 DSymbolw(0(B 0 @.
@n?" dd@ @@``4,?!!>bQZ !"#%&'
(, ./2$$$$b$:.i!bRb$?.y+kioZ b$PBw_=vV)#
b$OO/@Ady} b$YL2.1a b$S˫[8ŗtc'%0AA0@3ʚ;ʚ;g4BdBd@B 0(ppp@<4ddddlpC 0\w80___PPT10
pp?,O
=)Twotier relaxed heaps lPresented by Claus Jensen
Joint work with Amr Elmasry and Jyrki Katajainen
Slides available at
www.cphstl.dkmPm*
Heaps
Our focus has been on the worstcase comparison complexity of the heap operations:
Findmin
Insert
Decrease(key)
Delete
The following heaps support decrease at O(1) cost in the worst case:
Runrelaxed heaps (Driscoll et al. 1988)
Fat heaps (Kaplan and Tarjan 1999)TS&EMS&EM&
Worstcase complexity bounds >The number of element comparisons performed in the worstcase
>?? Our twotier relaxed heaps =A twotier relaxed heap has the following complexity bounds.
=>> Twotier relaxed heaps A twotier relaxed heap is composed of two runrelaxed heaps relying on a redundant zeroless representation
Next: Number representations vs. data structures&l +A binomial heap using binary representation,,(+ M = 111two Digits = {0, 1}
A binomial heap storing 7 integers which are kept in 3 binomial trees and stored in heap order within the trees
The rank of a binomial tree is equal to the number of children of the rootrZ
MC 6 A binomial heap using redundant binary representation"7(6(6 XM = 202redundant two Digits = {0, 1, 2}
A binomial heap storing 10 integers @Y
&Y 7A binomial heap using redundant zeroless representation88(7 [M = 214redundant four Digits = {1, 2, 3, 4}
A binomial heap storing 14 integers8\Z%\ Zeroless number system $Addition
M + 1
Corresponds to inserting a node into the binomial heap
Subtraction
M 1
Corresponds to extracting a node from the binomial heapT Z?ZZ?Z ?? Insert and extract dUsing functionality which incrementally handles carries and borrows in the zeroless number system, both addition and subtraction can be accomplished at constant cost
When using a carry/borrow stack to provide this functionality in the context of binomial heaps, both insert and extract can be performed at constant worstcase cost
Next: Runrelaxed heaps^ePDle Runrelaxed heaps A runrelaxed heap is composed of relaxed binomial trees which are almost heapordered binomial trees
Some nodes can be marked active indicating that there may be a heaporder violation
The maximum number of active nodes is lg n (Driscoll et al. 1988)
A singleton is an active node which has no active siblings
A run is a sequence of consecutive active siblingsnP")
5 2.& Runrelaxed heaps A series of run/singleton transformations is used to reduce the number of active nodes
Illustrated with one of the singleton transformations0WZZ6Z A runrelaxed heap
A run relaxed heap storing 10 integers. The relaxed binomial trees are drawn in schematic form and active nodes are drawn in greyZ Twotier relaxed heap components!!(! A twotier relaxed heap has the following components:
An upper store which contains pointers to roots and active nodes held in the lower store
A lower store which contains the elements of the heap
The two components are runrelaxed heaps using the redundant zeroless number system6T6>T A twotier relaxed heap 3
A twotier relaxed heap storing 12 integers, &Extra functionality at the upper store''(' Lazy deletions: Nodes in the upper store are marked instead of being deleted
When the number of marked nodes reaches half of the total number of nodes, the marked nodes are removed by an incremental global rebuildingHN<n Heap operations Findmin:
The upper store findmin operation is called, and this operation returns either one of the roots or one of the active nodes
6 Heap operations Insert:
The lower store insert operation is called which adds a new node to the lower store
A pointer to that node is inserted into the upper store
If due to a join of two trees a node is no longer a root, the pointer in the upper store associated with that node are marked*
Heap operations Decrease:
After the element replacement the node is made active
If the number of active nodes has become too large, a constant number of transformations (singleton or run) is performed
A pointer to the node is inserted into the upper store
* Heap operations \Delete:
Lower store: The node is removed. A node is extracted, and this node and the roots of the former subtrees are joined together into a new tree
If deletion involves an internal node, the new root of the subtree is made active
Upper store: A pointer to the new root is inserted. If there exists a pointer to the removed node, it is deleted.
. PTP T] New contribution XThe introduction of extract
Improved constant factors for delete
The multitier concept
Y
Open problems Constant factors for the findmin, insert, and decrease operations should be improved
Can the bound for delete be improved to log n + O(1)? (this can be obtained when decrease is not supported)
Related work
#Amr Elmasry, Claus Jensen, and Jyrki Katajainen. Relaxed weak queues: an alternative to runrelaxed heaps. CPH STL Report 20052
Amr Elmasry, Claus Jensen, and Jyrki Katajainen. On the power of structural violations in priority queues. CPH STL Report 20053
Both available at www.cphstl.dk
P$Z18I8
R
d
/T!
` 33` Sf3f` 33g` f` www3PP` ZXdbmo` \ғ3y`Ӣ` 3f3ff` 3f3FKf` hk]wwwfܹ` ff>>\`Y{ff` R>& {p_/̴>?" dd@,?" dd@ " @ ` n?" dd@ @@``PR @ ` `p>>H@(
6 `}
b.Klik for at redigere titeltypografi i masteren/
/,
0Xŭ `
hKlik for at redigere teksttypografierne i masteren
Andet niveau
Tredje niveau
Fjerde niveau
Femte niveau3
i
04̭ ^ `
X*
0Э ^
Z*
0ԭ ^ `
Z*H
0h ? 3380___PPT10.@ڵ Standarddesign
0P (
0' P
P*
0
R*
d
c$ ?
,
0<(
0
hKlik for at redigere teksttypografierne i masteren
Andet niveau
Tredje niveau
Fjerde niveau
Femte niveau3
i
684 _P
P*
6x9 _
R*
H
0h ? 3380___PPT10.w`[} $(
r
S>
r
Sp `
H
0h ? 33___PPT10i.Vܵ+D=' =
@B +}
l$(
lr
l ST `}
r
l S S `
H
l0h ? 33___PPT10i.fœ@+D=' =
@B +M
d\Pd(
dx
d c$j `}
~
d s*m
'
Pd#"&s[Z[v'
)d
<v ?

`O(1) @`
'd
< ?
`O(1) @`
%d
<, ?'
bDecrease @`
d
<ؐ ?
j2.6lg n + O(1) @`
d
< ?
h3lg n + O(1)
@`
d
<衅 ?'
`Delete @`
d
< ?

`O(1) @`
d
<ز ?

`O(1) @`
d
< ?'

`Insert @`
d
<
?
x
`O(1) @`
d
<ʅ ?x
`O(1) @`
d
<h̅ ?'x
bFindmin @`
d
<Յ ?
x
e Fat heaps
@`
d
<݅ ?
x
mRunrelaxed heaps @`
d
< ?'x
T @`fB
d
6o?'`B
d
01?'x x `B
d
01?'
`B
d
01?'fB
d
6o?'fB
d
6o?''`B
d
01?`B
d
01?
fB
d
6o?ZB
&d
s*1
?'
H
d0h ? 33___PPT10i.0o+D=' =
@B +
Yhl(
hx
h c$ `}
~
h s*4
. '",
Yh#"&hz]{P"',
h
< ?&a
`O(1) @`
h
< ?a&
`O(1) @`
h
< ?'a
bDecrease @`
h
<p ?&
,
qO(lg n) @`;
h
< ?
&,
lg n + 3lglg n + O(1)^ @`
h
<! ?'
,
`Delete @`
h
<l< ?&a
`O(1) @`
h
<D ?&a
`O(1) @`
h
<0M ?'a
`Insert @`
h
<G ?&
`O(1) @`
h
<\ ? &
`O(1) @`
h
<^ ?'
bFindmin @`
h
<hg ?&"
kWorstcase
cost @`
h
<4p ?"&
yNumber of element comparisons @`
h
<x ?'"
T @`fB
h
6o?'""`B
h
01?' `B
h
01?'`B
h
01?'aafB
h
6o?',,fB
h
6o?'"',`B
h
01?",`B
h
01?&"&,fB
h
6o?",ZB
!h
s*1
?'
H
h0h ? 33___PPT10i.0o+D=' =
@B +}
x$(
xr
x S( `}
r
x S% `
H
x0h ? 33___PPT10i.{[+D=' =
@B +/
F>0(
r
Sx `}
x
c$L w
dAbinomial_fig3mH
0h ? 33___PPT10i.V`z+D=' =
@B +3
JB(
r
 S `}
x
 c$ I

hA bredundant_fig3zH
0h ? 33___PPT10i.L+D=' =
@B +9
PH(
r
Sɮ `}
x
c$ɮ
nA &zero_binomial_fig2"{H
0h ? 33___PPT10i.0&o+D=' =
@B +}
$(
r
Stڮ `}
r
SHۮ `
H
0h ? 33___PPT10i.Lg+D=' =
@B +}
$(
r
S `}
r
Sl `
H
0h ? 33___PPT10i.+D=' =
@B +}
p\$(
\r
\ S `}
r
\ SL `
H
\0h ? 33___PPT10i.P+D=' =
@B +E
\T(
r
S `}
x
c$
zA2transformation_fig_ISAACH
0h ? 33___PPT10i.F +D=' =
@B +1
H@(
x
c$ `}
~
s* Y
ZA
run_fig3/6H
0h ? 33___PPT10i.0&o+D=' =
@B +}
0$(
r
S( `}
r
S) `
H
0h ? 33___PPT10i.Br+D=' =
@B +#
:2 (
r
S/ `}
x
c$2 YY
XAtt_fig2zH
0h ? 33___PPT10i.
+D=' =
@B +}
<$(
<r
< S; `}
r
< S; `
H
<0h ? 33___PPT10i.g+D=' =
@B +#
:2(
r
SA `}
x
c$0D
XAtt_fig2p`f
H
0h ? 33___PPT10i.q`+D=' =
@B +#
:2@(
@r
@ SJ `}
x
@ c$J
@
XAtt_fig2p`f
H
@0h ? 33___PPT10i.@U+D=' =
@B +#
:2`(
`r
` Sp\ `}
x
` c$0]
`
XAtt_fig2p`f
H
`0h ? 33___PPT10i.*`hl+D=' =
@B +#
:2D(
Dr
D Sh `}
x
D c$m
D
XAtt_fig2p`f
H
D0h ? 33___PPT10i.\w+D=' =
@B +}
$(
r
Sx `}
r
Sly `
H
0h ? 33___PPT10i.`0N+D=' =
@B +}
p$(
pr
p S `}
r
p S `
H
p0h ? 33___PPT10i.UX+D=' =
@B +}
PT$(
Tr
T S@݀ `}
r
T Sހ `
H
T0h ? 33___PPT10i.H\+D=' =
@B +
0` (
X
C
S
0
" H
0h ? 3380___PPT10.wb0
0p@(
X
C
S
0
BHeap ordered H
0h ? 3380___PPT10.w
0 (
X
C
SF
0
H
0h ? 3380___PPT10.r@1A<0
'1ǘF"[HDouxtr;Ĩq'~!e!1(
er relaxed heapsTwotier relaxed heaps,A binomial heap using binary representation7 A binomial heap using redundant binary representation8A binomial heap using redundant zeroless representationZeroless number systemInsert and extractRunrelaxed heapsRunrelaxed heapsA runrelaxed heap!Twotier relaxed heap componentsA twotier relaxed heap'Extra functionality at the upper storeHeap operationsHeap operationsHeap operationsHeap operationsNew contributionOpen problems
Related workBenyttede skrifttyperDesignskabelonerDiastitler@Arial. 2
61.@Arial. "2
64tier relaxed heaps.`/0DArial6T00LLvԖT0ԖDSymbol6T00LLvԖT0Ԗ@.
@n?" dd@ @@``4,?!!>bQZ !"#%&'
(, ./2$$$$b$:.i!bRb$?.y+kioZ b$PBw_=vV)#
b$OO/@Ady} b$YL2.1a b$S˫[8ŗtc'%0AA0@3ʚ;ʚ;g4kdkdĂT0ppp@<4dddd!0Lu80___PPT10
pp?,O
=)Twotier relaxed heaps lPresented by Claus Jensen
Joint work with Amr Elmasry and Jyrki Katajainen
Slides available at
www.cphstl.dkmPm*
Heaps
Our focus has been on the worstcase comparison complexity of the heap operations:
Findmin
Insert
Decrease(key)
Delete
The following heaps support decrease at O(1) cost in the worst case:
Runrelaxed heaps (Driscoll et al. 1988)
Fat heaps (Kaplan and Tarjan 1999)TS&EMS&EM&
Worstcase complexity bounds >The number of element comparisons performed in the worst case
>?? Our twotier relaxed heaps =A twotier relaxed heap has the following complexity bounds.
=>> Twotier relaxed heaps A twotier relaxed heap is composed of two runrelaxed heaps relying on a redundant zeroless representation
Next: Number representations vs. data structures&l +A binomial heap using binary representation,,(+ M = 111two Digits = {0, 1}
A binomial heap storing 7 integers which are kept in 3 binomial trees and stored in heap order within the trees
The rank of a binomial tree is equal to the number of children of the rootrZ
MC 6 A binomial heap using redundant binary representation"7(6(6 XM = 202redundant two Digits = {0, 1, 2}
A binomial heap storing 10 integers @Y
&Y 7A binomial heap using redundant zeroless representation88(7 [M = 214redundant four Digits = {1, 2, 3, 4}
A binomial heap storing 14 integers8\Z%\ Zeroless number system $Addition
M + 1
Corresponds to inserting a node into the binomial heap
Subtraction
M 1
Corresponds to extracting a node from the binomial heapT Z?ZZ?Z ?? Insert and extract dUsing functionality which incrementally handles carries and borrows in the zeroless number system, both addition and subtraction can be accomplished at constant cost
When using a carry/borrow stack to provide this functionality in the context of binomial heaps, both insert and extract can be performed at constant worstcase cost
Next: Runrelaxed heaps^ePDle Runrelaxed heaps A runrelaxed heap is composed of relaxed binomial trees which are almost heapordered binomial trees
Some nodes can be marked active indicating that there may be a heaporder violation
The maximum number of active nodes is lg n (Driscoll et al. 1988)
A singleton is an active node which has no active siblings
A run is a sequence of consecutive active siblingsnP")
5`/0DArial6T00LLvԖT0ԖDSymbol6T00LLvԖT0Ԗ@.
@n?" dd@ @@``4,?!!>bQZ !"#%&'
(, ./2$$$$b$:.i!bRb$?.y+kioZ b$PBw_=vV)#
b$OO/@Ady} b$YL2.1a b$S˫[8ŗtc'%0AA0@3ʚ;ʚ;g4kdkdĂT0ppp@<4dddd!0Lu80___PPT10
pp?,O
=)Twotier relaxed heaps lPresented by Claus Jensen
Joint work with Amr Elmasry and Jyrki Katajainen
Slides available at
www.cphstl.dkmPm*
Heaps
Our focus has been on the worstcase comparison complexity of the heap operations:
Findmin
Insert
Decrease(key)
Delete
The following heaps support decrease at O(1) cost in the worst case:
Runrelaxed heaps (Driscoll et al. 1988)
Fat heaps (Kaplan and Tarjan 1999)TS&EMS&EM&
Worstcase complexity bounds >The number of element comparisons performed in the worst case
>?? Our twotier relaxed heaps =A twotier relaxed heap has the following complexity bounds.
=>> Twotier relaxed heaps A twotier relaxed heap is composed of two runrelaxed heaps relying on a redundant zeroless representation
Next: Number representations vs. data structures&l +A binomial heap using binary representation,,(+ M = 111two Digits = {0, 1}
A binomial heap storing 7 integers which are kept in 3 binomial trees and stored in heap order within the trees
The rank of a binomial tree is equal to the number of children of the rootrZ
MC 6 A binomial heap using redundant binary representation"7(6(6 XM = 202redundant two Digits = {0, 1, 2}
A binomial heap storing 10 integers @Y
&Y 7A binomial heap using redundant zeroless representation88(7 [M = 214redundant four Digits = {1, 2, 3, 4}
A binomial heap storing 14 integers8\Z%\ Zeroless number system $Addition
M + 1
Corresponds to inserting a node into the binomial heap
Subtraction
M 1
Corresponds to extracting a node from the binomial heapT Z?ZZ?Z ?? Insert and extractPowerPoint Document(/DocumentSummaryInformation8)hJ:EPNG
IHDRB pHYstIME
tEXtCommentCreated with The GIMPd%n PLTEǯ{
2IDATxn RGg>SU@^!Sn5'gL5EQ@Qa?9=9BS?8߇3oƙ,UsqPJlИ,4;q/e#(80@G?=1`q&5d%'ѣGewgzqV}l/clWɌd?=©ٝ{q95OKٜ0gsAw
pl`d#褙ls bG8V
C(&!plRddD
%@G7q`#9*uMAm/v=0#ipߙ??@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklm~oqrstuvwxyz{}_ÑGɳc[{9yA'G!Ύq&b;jANp{Ch
9z
mҷs}#}8~c48Lx+Ӷq3GomSZNt9snѸB}tq̕{8^bdط{(g=`m+8w6sQwpg9m dN2risSX)~{s<߇yXNds9]9,q~IA6O'??J*s)qGnQ;":h6N~N{9YSNEtjҷ6
r089<uQ=1NI :~?CS7 MZg_R" 1Ǯ<~y/Ø xT]?~e,(Φ?\>#^gsXc?jaJr,q}*rּ+oW=NsQ3Q=Zr$Vv9ǉA&q9+z<:71g8挞#/2+gr32q$7YHr!G#=hXkr^s8i֢â5N?l9, 4o[i*ͯP.u(ku>7s/]#̪5QBE\oBIwD:ejF{qɕ}xf;S
u.T˅㒜hq@'6z8xA21rDW3␁sr}~('GNN.EH
!g@p`If8>'a Ao dUsing functionality which incrementally handles carries and borrows in the zeroless number system, both addition and subtraction can be accomplished at constant cost
When using a carry/borrow stack to provide this functionality in the context of binomial heaps, both insert and extract can be performed at constant worstcase cost
Next: Runrelaxed heaps^ePDle Runrelaxed heaps A runrelaxed heap is composed of relaxed binomial trees which are almost heapordered binomial trees
Some nodes can be marked active indicating that there may be a heaporder violation
The maximum number of active nodes is lg n (Driscoll et al. 1988)
A singleton is an active node which has no active siblings
A run is a sequence of consecutive active siblingsnP")
5 2.& Runrelaxed heaps A series of run/singleton transformations is used to reduce the number of active nodes
Illustrated with one of the singleton transformations0WZZ6Z A runrelaxed heap
A runrelaxed heap storing 10 integers. The relaxed binomial trees are drawn in schematic form and active nodes are drawn in greyZ Twotier relaxed heap components!!(! A twotier relaxed heap has the following components:
An upper store which contains pointers to roots and active nodes held in the lower store
A lower store which contains the elements of the heap
The two components are runrelaxed heaps using the redundant zeroless number system6T6>T A twotier relaxed heap 3
A twotier relaxed heap storing 12 integers, &Extra functionality at the upper store''(' Lazy deletions: Sometimes nodes in the upper store are marked instead of being deleted
When the number of marked nodes reaches half of the total number of nodes, the marked nodes are removed by an incremental global rebuildingHXFn& Heap operations Findmin:
The upper store findmin operation is called, and this operation returns either one of the roots or one of the active nodes
6 Heap operations Insert:
The lower store insert operation is called which adds a new node to the lower store
A pointer to that node is inserted into the upper store
If due to a join of two trees a node is no longer a root, the pointer in the upper store associated with that node are marked*
Heap operations Decrease:
After the element replacement the node is made active
If the number of active nodes has become too large, a constant number of transformations (singleton or run) is performed
A pointer to the node is inserted into the upper store
* Heap operations \Delete:
Lower store: The node is removed. A node is extracted, and this node and the roots of the former subtrees are joined together into a new tree
If deletion involves an internal node, the new root of the subtree is made active
Upper store: A pointer to the new root is inserted. If there exists a pointer to the removed node, it is deleted.
. PTP T] New contribution XThe introduction of extract
Improved constant factors for delete
The multitier concept
Y
Open problems Constant factors for the findmin, insert, and decrease operations should be improved
Can the bound for delete be improved to log n + O(1)? (this can be obtained when decrease is not supported)
Related work
#Amr Elmasry, Claus Jensen, and Jyrki Katajainen. Relaxed weak queues: an alternative to runrelaxed heaps. CPH STL Report 20052
Amr Elmasry, Claus Jensen, and Jyrki Katajainen. On the power of structural violations in priority queues. CPH STL Report 20053
Both available at www.cphstl.dk
P$Z18I8
R
d
/T!K
0bZPd(
dx
d c$L{: `}
:
~
d s*$: :
'
Pd#"&s[Z[v':
)d
<: ?

`O(1) @`
'd
<: ?
`O(1) @`
%d
<: ?'
bDecrease @`
d
<: ?
j2.6lg n + O(1) @`
d
<X: ?
h3lg n + O(1)
@`
d
<: ?'
`Delete @`
d
<\: ?

`O(1) @`
d
< : ?

`O(1) @`
d
<t: ?'

`Insert @`
d
<: ?
x
`O(1) @`
d
<: ?x
`O(1) @`
d
<p: ?'x
bFindmin @`
d
<p: ?
x
e Fat heaps
@`
d
<: ?
x
mRunrelaxed heaps @`
d
<d: ?'x
R @`fB
d
6o?'`B
d
01?'x x `B
d
01?'
`B
d
01?'fB
d
6o?'fB
d
6o?''`B
d
01?`B
d
01?
fB
d
6o?ZB
&d
s*1
?'
H
d0h ? 33___PPT10i.0o+D=' k=
@B +1
0H@(
x
c$ܘe `}
e
~
s*@e Ye
ZA
run_fig3/6eH
0h ? 33___PPT10i.0&o+D=' k=
@B +}
0<$(
<r
< Se `}
e
r
< Spe `e
H
<0h ? 33___PPT10i.g+D=' k=
@B +r ĭ
uX!11(
$'@Arial. 2
PTwo&+"."System@Arial. 2
P0.@Arial. "2
PDtier relaxed heaps""""""""".@Arial. 2
IPresented by Claus Jensen
.@Arial. 2
Joint work with .@Arial. 2
Amr .@Arial. 2
Elmasry
.@Arial.
2
)and .@Arial. 2
`Jyrkir
.@Arial. 2
Katajainen.@Arial. $2
Slides available at
.@Arial. 2
(
www.cphstl.dkt.՜.+,08
Skrmshowojen inc:
ArialSymbolStandarddesignTwotier relaxed heapsHeapsWorstcase complexity boundsOur twoti 2.& Runrelaxed heaps A series of run/singleton transformations is used to reduce the number of active nodes
Illustrated with one of the singleton transformations0WZZ6Z A runrelaxed heap
A runrelaxed heap storing 10 integers. The relaxed binomial trees are drawn in schematic form and active nodes are drawn in greyZ Twotier relaxed heap components!!(! A twotier relaxed heap has the following components:
An upper store which contains pointers to roots and active nodes held in the lower store
A lower store which contains the elements of the heap
The two components are runrelaxed heaps using the redundant zeroless number system6T6>T A twotier relaxed heap 3
A twotier relaxed heap storing 12 integers, &Extra functionality at the upper store''(' Lazy deletions: Sometimes nodes in the upper store are marked instead of being deleted
When the number of marked nodes reaches half of the total number of nodes, the marked nodes are removed by an incremental global rebuildingHXFn Heap operations Findmin:
The upperstore findmin operation is called, and this operation returns either one of the roots or one of the active nodes
6 Heap operations Insert:
The lowerstore insert operation is called which adds a new node to the lower store
A pointer to that node is inserted into the upper store
If due to a join of two trees a node is no longer a root, the pointer in the upper store associated with that node is marked* &
Heap operations Decrease:
After the element replacement the node is made active
If the number of active nodes has become too large, a constant number of transformations (singleton or run) is performed
A pointer to the node is inserted into the upper store
* Heap operations \Delete:
Lower store: The node is removed. A node is extracted, and this node and the roots of the former subtrees are joined together into a new tree
If deletion involves an internal node, the new root of the subtree is made active
Upper store: A pointer to the new root is inserted. If there exists a pointer to the removed node, it is deleted.
. PTP T] New contribution XThe introduction of extract
Improved constant factors for delete
The multitier concept
Y
Open problems Constant factors for the findmin, insert, and decrease operations should be improved
Can the bound for delete be improved to log n + O(1)? (this can be obtained when decrease is not supported)
Related work
#Amr Elmasry, Claus Jensen, and Jyrki Katajainen. Relaxed weak queues: an alternative to runrelaxed heaps. CPH STL Report 20052
Amr Elmasry, Claus Jensen, and Jyrki Katajainen. On the power of structural violations in priority queues. CPH STL Report 20053
Both available at www.cphstl.dk
P$Z18I8
R
d
/T!#
0:2(
r
SbQZ !"#%&'
(, ./2$$$$b$:.i!bRb$?.y+kioZ b$PBw_=vV)#
b$OO/@Ady} b$YL2.1a b$S˫[8ŗtc'%0AA0@3ʚ;ʚ;g4kdkdĂT0ppp@<4dddd!0Lu80___PPT10
pp?,O
=)Twotier relaxed heaps lPresented by Claus Jensen
Joint work with Amr Elmasry and Jyrki Katajainen
Slides available at
www.cphstl.dkmPm*
Heaps
Our focus has been on the worstcase comparison complexity of the heap operations:
Findmin
Insert
Decrease(key)
Delete
The following heaps support decrease at O(1) cost in the worst case:
Runrelaxed heaps (Driscoll et al. 1988)
Fat heaps (Kaplan and Tarjan 1999)TS&EMS&EM&
Worstcase complexity bounds >The number of element comparisons performed in the worst case
>?? Our twotier relaxed heaps =A twotier relaxed heap has the following complexity bounds.
=>> Twotier relaxed heaps A twotier relaxed heap is composed of two runrelaxed heaps relying on a redundant zeroless representation
Next: Number representations vs. data structures&l +A binomial heap using binary representation,,(+ M = 111two Digits = {0, 1}
A binomial heap storing 7 integers which are kept in 3 binomial trees and stored in heap order within the trees
The rank of a binomial tree is equal to the number of children of the rootrZ
MC 6 A binomial heap using redundant binary representation"7(6(6 XM = 202redundant two Digits = {0, 1, 2}
A binomial heap storing 10 integers @Y
&Y 7A binomial heap using redundant zeroless representation88(7 [M = 214redundant four Digits = {1, 2, 3, 4}
A binomial heap storing 14 integers8\Z%\ Zeroless number system $Addition
M + 1
Corresponds to inserting a node into the binomial heap
Subtraction
M 1
Corresponds to extracting a node from the binomial heapT Z?ZZ?Z ?? Insert and extract dUsing functionality which incrementally handles carries and borrows in the zeroless number system, both addition and subtraction can be accomplished at constant cost
When using a carry/borrow stack to provide this functionality in the context of binomial heaps, both insert and extract can be performed at constant worstcase cost
Next: Runrelaxed heaps^ePDle Runrelaxed heaps A runrelaxed heap is composed of relaxed binomial trees which are almost heapordered binomial trees
Some nodes can be marked active indicating that there may be a heaporder violation
The maximum number of active nodes is lg n (Driscoll et al. 1988)
A singleton is an active node which has no active siblings
A run is a sequence of consecutive active siblingsnP")
5 2.& Runrelaxed heaps A series of run/singleton transformations is used to reduce the number of active nodes
Illustrated with one of the singleton transformations0WZZ6Z A runrelaxed heap
A runrelaxed heap storing 10 integers. The relaxed binomial trees are drawn in schematic form and active nodes are drawn in greyZ Twotier relaxed heap components!!(! A twotier relaxed heap has the following components:
An upper store which contains pointers to roots and active nodes held in the lower store
A lower store which contains the elements of the heap
The two components are runrelaxed heaps using the redundant zeroless number system6T6>T A twotier relaxed heap 3
A twotier relaxed heap storing 12 integers, &Extra functionality at the upper store''(' Lazy deletions: Sometimes nodes in the upper store are marked instead of being deleted
When the number of marked nodes reaches half of the total number of nodes, the marked nodes are removed by an incremental global rebuildingHXFn Heap operations Findmin:
The upperstore findmin operation is called, and this operation returns either one of the roots or one of the active nodes
6 Heap operations Insert:
The lowerstore insert operation is called which adds a new node to the lower store
A pointer to that node is inserted into the upper store
If due to a join of two trees a node is no longer a root, the pointer in the upper store associated with that node is marked*
Heap operations Decrease:
After the element replacement the node is made active
If the number of active nodes has become too large, a constant number of transformations (singleton or run) is performed
A pointer to the node is inserted into the upper store
* Heap operations \Delete:
Lower store: The node is removed. A node is extracted, and this node and the roots of the former subtrees are joined together into a new tree
If deletion involves an internal node, the new root of the subtree is made active
Upper store: A pointer to the new root is inserted. If there exists a pointer to the removed node, it is deleted.
. PTP T] New contribution AThe introduction of extract
Improved constant factors for delete
ABB
Open problems Constant factors for the findmin, insert, and decrease operations should be improved
Can the bound for delete be improved to log n + O(1)? (this can be obtained when decrease is not supported)
Related work
#Amr Elmasry, Claus Jensen, and Jyrki Katajainen. Relaxed weak queues: an alternative to runrelaxed heaps. CPH STL Report 20052
Amr Elmasry, Claus Jensen, and Jyrki Katajainen. On the power of structural violations in priority queues. CPH STL Report 20053
Both available at www.cphstl.dk
P$Z18I8
R
d
/T!}
0$(
r
Sk `}
k
r
S
k `k
H
0h ? 33___PPT10i.`0N+D=' k=
@B +r2cX1Ff!11(
`/0DArial6T00LLvԖT0ԖDSymbol6T00LLvԖT0Ԗ@.
@n?" dd@ @@``4,?!!>bQZ !"#%&'
(, ./2$$$$b$:.i!bRb$?.y+kioZ b$PBw_=vV)#
b$OO/@Ady} b$YL2.1a b$S˫[8ŗtc'%0AA0@3ʚ;ʚ;g4kdkdĂT0ppp@<4dddd!0Lu80___PPT10
pp?,O
=)Twotier relaxed heaps lPresented by Claus Jensen
Joint work with Amr Elmasry and Jyrki Katajainen
Slides available at
www.cphstl.dkmPm*
Heaps
Our focus has been on the worstcase comparison complexity of the heap operations:
Findmin
Insert
Decrease(key)
Delete
The following heaps support decrease at O(1) cost in the worst case:
Runrelaxed heaps (Driscoll et al. 1988)
Fat heaps (Kaplan and Tarjan 1999)TS&EMS&EM&
Worstcase complexity bounds >The number of element comparisons performed in the worst case
>?? Our twotier relaxed heaps =A twotier relaxed heap has the following complexity bounds.
=>> Twotier relaxed heaps A twotier relaxed heap is composed of two runrelaxed heaps relying on a redundant zeroless representation
Next: Number representations vs. data structures&l +A binomial heap using binary representation,,(+ M = 111two Digits = {0, 1}
A binomial heap storing 7 integers which are kept in 3 binomial trees and stored in heap order within the trees
The rank of a binomial tree is equal to the number of children of the rootrZ
MC 6 A binomial heap using redundant binary representation"7(6(6 XM = 202redundant two Digits = {0, 1, 2}
A binomial heap storing 10 integers @Y
&Y 7A binomial heap using redundant zeroless representation88(7 [M = 214redundant four Digits = {1, 2, 3, 4}
A binomial heap storing 14 integers8\Z%\ Zeroless number system $Addition
M + 1
Corresponds to inserting a node into the binomial heap
Subtraction
M 1
Corresponds to extracting a node from the binomial heapT Z?ZZ?Z ?? Insert and extract dUsing functionality which incrementally handles carries and borrows in the zeroless number system, both addition and subtraction can be accomplished at constant cost
When using a carry/borrow stack to provide this functionality in the context of binomial heaps, both insert and extract can be performed at constant worstcase cost
Next: Runrelaxed heaps^ePDle Runrelaxed heaps A runrelaxed heap is composed of relaxed binomial trees which are almost heapordered binomial trees
Some nodes can be marked active indicating that there may be a heaporder violation
The maximum number of active nodes is lg n (Driscoll et al. 1988)
A singleton is an active node which has no active siblings
A run is a sequence of consecutive active siblingsnP")
5 2.& Runrelaxed heaps A series of run/singleton transformations is used to reduce the number of active nodes
Illustrated with one of the singleton transformations0WZZ6Z A runrelaxed heap
A runrelaxed heap storing 10 integers. The relaxed binomial trees are drawn in schematic form and active nodes are drawn in greyZ Twotier relaxed heap components!!(! A twotier relaxed heap has the following components:
An upper store which contains pointers to roots and active nodes held in the lower store
A lower store which contains the elements of the heap
The two components are runrelaxed heaps using the redundant zeroless number system6T6>T A twotier relaxed heap 3
A twotier relaxed heap storing 12 integers, &Extra functionality at the upper store''(' Lazy deletions: Sometimes nodes in the upper store are marked instead of being deleted
When the number of marked nodes reaches half of the total number of nodes, the marked nodes are removed by an incremental global rebuildingHXFn Heap operations Findmin:
The upperstore findmin operation is called, and this operation returns either one of the roots or one of the active nodes
6 Heap operations Insert:
The lowerstore insert operation is called which adds a new node to the lower store
A pointer to that node is inserted into the upper store
If due to a join of two trees a node is no longer a root, the pointer in the upper store associated with that node is marked*
Heap operations Decrease:
After the element replacement the node is made active
If the number of active nodes has become too large, a constant number of transformations (singleton or run) is performed
A pointer to the node is inserted into the upper store
* Heap operations \Delete:
Lower store: The node is removed. A node is extracted, and this node and the roots of the former subtrees are joined together into a new tree
If deletion involves an internal node, the new root of the subtree is made active
Upper store: A pointer to the new root is inserted. If there exists a pointer to the removed node, it is deleted.
. PTP T] New contribution AThe introduction of extract
Improved constant factors for delete
ABB
Open problems Constant factors for the findmin, insert, and decrease operations should be improved
Can the bound for delete be improved to log n + O(1)? (this can be obtained when decrease is not supported)
Related work
#Amr Elmasry, Claus Jensen, and Jyrki Katajainen. Relaxed weak queues: an alternative to runrelaxed heaps. CPH STL Report 20052
Amr Elmasry, Claus Jensen, and Jyrki Katajainen. On the power of structural violations in priority queues. CPH STL Report 20053
Both available at www.cphstl.dk
P$Z18I8
R
d
/T!rfX^f'!11(
`/0DArialw0B 0DSymbolw0B 0@.
@n?" dd@ @@``4Root EntrydO) Pictures;Current User/SummaryInformation( pn
!"#$%&'(*+,./0123456789:_clausclausaus JensenOh+'0x `h
Twotier relaxed heapsclauserclauser236Microsoft PowerPoints@0š@̂֩@p :Gpg 04q2d2q!⁌72N@9rxrN@9qK^3hT$rx8+#sTGK(P)썜0T9rxDf)VF6oIEmadl5q
#sꓟR27uΉ\>';Crn5Gtr҉ݲpQk}N~(y%Q@kNN[8&a1٩ y'oPѷT'op^?g7<}*rS2T5.Gias[JGqjK_1REtzT.uA_3fI(PJ*!gry
5pIԃDh}C~W'R_'EW!dޖvA˂E(U{ȥli7?&%2@i &_Ek}>?o 0Qt3*y=^;5ru@\k8r[5>}c FyOytd9jv+u %s"o($(!)Smb}>R\~a8msւ㍜Lyg# hNk1o@~P駯S9=MvvT9P7ް`2Ɵ8.<#r┑,Y6)eijƼ;*{vyS6,?N/!LPS쉠?*E7(?DG7]Z&kkLhVb䕜ސiƲˮT til+7[8Fެa=͎3m,+T~U0=l"mSuƤ25[i*'CsvsH :RfZ6!ḡ:3Y6>t#8NGZ\Jq3;=`6(\.fU>nqA_\]Bi9
o5rx?gpD0k?\ߧ]^(t氝B#l/$*A
o
*ΘUO,g@STD6{+_gg6\
+iruBF8e@T%w߳E_7g4"$GNB~.
ի9[P\hkh9tGζ;O}#{rjFpr=#+zmdGqJ?U=Ɓs+k:P
X}##+!=2ݚ U5'Gry8=2's{di8^=2rN~8?s۽8y~8?{r
*%IENDB`,?!!>b
QZ !"
#%&'
(,./2b$_J:E
$$$b$:.i!bRb$?.y+kioZ $b$OO/@Ady} b$YL2.1a b$S˫[8ŗtc'%0AA0@3ʚ;ʚ;g4BdBd B 0(ppp@<4ddddLpC 0\w80___PPT10
pp?,O
=)Twotier relaxed heaps lPresented by Claus Jensen
Joint work with Amr Elmasry and Jyrki Katajainen
Slides available at
www.cphstl.dkmPm*
Heaps
Our focus has been on the worstcase comparison complexity of the heap operations:
Findmin
Insert
Decrease(key)
Delete
The following heaps support decrease at O(1) cost in the worst case:
Runrelaxed heaps (Driscoll et al. 1988)
Fat heaps (Kaplan and Tarjan 1999)TS&EMS&EM&
Worstcase complexity bounds >The number of element comparisons performed in the worst case
>?? Our twotier relaxed heaps =A twotier relaxed heap has the following complexity bounds.
=>> Twotier relaxed heaps A twotier relaxed heap is composed of two runrelaxed heaps relying on a redundant zeroless representation
Next: Number representations vs. data structures&l +A binomial heap using binary representation,,(+ M = 111two Digits = {0, 1}
A binomial heap storing 7 integers which are kept in 3 binomial trees and stored in heap order within the trees
The rank of a binomial tree is equal to the number of children of the rootrZ
MC 6 A binomial heap using redundant binary representation"7(6(6 XM = 202redundant two
Digits = {0, 1, 2}
A binomial heap storing 10 integers @Y
&Y 7A binomial heap using redundant zeroless representation88(7 [M = 214redundant four Digits = {1, 2, 3, 4}
A binomial heap storing 14 integers8\Z%\ Zeroless number system $Addition
M + 1
Corresponds to inserting a node into the binomial heap
Subtraction
M 1
Corresponds to extracting a node from the binomial heapT Z?ZZ?Z ?? Insert and extract dUsing functionality which incrementally handles carries and borrows in the zeroless number system, both addition and subtraction can be accomplished at constant cost
When using a carry/borrow stack to provide this functionality in the context of binomial heaps, both insert and extract can be performed at constant worstcase cost
Next: Runrelaxed heaps^ePDle Runrelaxed heaps A runrelaxed heap is composed of relaxed binomial trees which are almost heapordered binomial trees
Some nodes can be marked active indicating that there may be a heaporder violation
The maximum number of active nodes is lg n (Driscoll et al. 1988)
A singleton is an active node which has no active siblings
A run is a sequence of consecutive active siblingsnP")
5 2.& Runrelaxed heaps A series of run/singleton transformations is used to reduce the number of active nodes
Illustrated with one of the singleton transformations0WZZ6Z A runrelaxed heap
A runrelaxed heap storing 10 integers. The relaxed binomial trees are drawn in schematic form and active nodes are drawn in greyZ Twotier relaxed heap components!!(! A twotier relaxed heap has the following components:
An upper store which contains pointers to roots and active nodes held in the lower store
A lower store which contains the elements of the heap
The two components are runrelaxed heaps using the redundant zeroless number system6T6>T A twotier relaxed heap 3
A twotier relaxed heap storing 12 integers, &Extra functionality at the upper store''(' Lazy deletions: Sometimes nodes in the upper store are marked instead of being deleted
When the number of marked nodes reaches half of the total number of nodes, the marked nodes are removed by an incremental global rebuildingHXFn Heap operations Findmin:
The upperstore findmin operation is called, and this operation returns either one of the roots or one of the active nodes
6 Heap operations Insert:
The lowerstore insert operation is called which adds a new node to the lower store
A pointer to that node is inserted into the upper store
If due to a join of two trees a node is no longer a root, the pointer in the upper store associated with that node is marked*
Heap operations Decrease:
After the element replacement the node is made active
If the number of active nodes has become too large, a constant number of transformations (singleton or run) is performed
A pointer to the node is inserted into the upper store
* Heap operations \Delete:
Lower store: The node is removed. A node is extracted, and this node and the roots of the former subtrees are joined together into a new tree
If deletion involves an internal node, the new root of the subtree is made active
Upper store: A pointer to the new root is inserted. If there exists a pointer to the removed node, it is deleted.
. PTP T] New contribution AThe introduction of extract
Improved constant factors for delete
ABB
Open problems Constant factors for the findmin, insert, and decrease operations should be improved
Can the bound for delete be improved to log n + O(1)? (this can be obtained when decrease is not supported)
Related work
#Amr Elmasry, Claus Jensen, and Jyrki Katajainen. Relaxed weak queues: an alternative to runrelaxed heaps. CPH STL Report 20052
Amr Elmasry, Claus Jensen, and Jyrki Katajainen. On the power of structural violations in priority queues. CPH STL Report 20053
Both available at www.cphstl.dk
P$Z18I8
R
d
/T!#
:2 (
r
S `}
x
c$ YY
XAtt_fig3G
H
0h ? 33___PPT10i.
+D=' =
@B +#
:2
(
r
SXc `}
x
c$,d
XAtt_fig3p`c
H
0h ? 33___PPT10i.q`+D=' =
@B +#
:2 @(
@r
@ Sk `}
x
@ c$l
@
XAtt_fig3p`c
H
@0h ? 33___PPT10i.@U+D=' =
@B +#
:2 `(
`r
` S~ `}
x
` c$H
`
XAtt_fig3p`c
H
`0h ? 33___PPT10i.*`hl+D=' =
@B +#
:2 D(
Dr
D S `}
x
D c$\
D
XAtt_fig3p`c
H
D0h ? 33___PPT10i.\w+D=' =
@B +r,[ V+e7!