Soft Heap and Soft Sequence Heaps: Properties and Applications
S
o
f
t
S
e
q
u
e
n
c
e
H
e
a
p
s
(
A
c
c
e
p
t
e
d
t
o
S
I
A
M
S
y
m
p
o
s
i
u
m
o
n
S
i
m
p
l
i
c
i
t
y
i
n
A
l
g
o
r
i
t
h
m
s
,
S
O
S
A
2
1
)
Gerth Stølting Brodal
Aarhus University
Department of Computer Science, Aarhus University, November 3, 2020
Heap
1
I
NSERT
(
x
)
E
XTRACT
M
IN
()
(other operations not discussed in this talk
MakeHeap
,
Meld
,
FindMin
,
Delete
)
Soft Heap
Soft heap results
Application of Soft Heaps – O(
n
) Selection
function
select(A, k)
if
k = 1
then
return
min(A)
Q = softheap(1/3)
for
a
∈
A
do
Q.
Insert
(a)
for
i = 1
to
|A|/3
do
x = Q.
ExtractMin
()
small, large = partition(A, x)
if
k ≤ |small|
then
return
select(small, k)
return
select(large, k - |small|)
Chazelle JACM00
Application of Soft Heaps – O(
k
) Heap Selection
function
select(root, k)
S = {root}Q = softheap(1/4)
Q
.
Insert
(root)
for
i = 1
to
k - 1
do
(e, C) =
Q
.
ExtractMin
()
if
e not corrupted
then
C = C
∪
{e}for
e
∈
C
do
Q
.
Insert
(e.left)
Q
.
Insert
(e.right)
S = S
∪
{e.left, e.right}return
select(S, k)
3
4
11
12
14
42
6
15
16
19
24
42
uncorrupted boundary
Q
Kaplan, Kozma, Zamir,
Zwick SOSA19
Sequence Heaps
2 15
2 13 15 25
1 2 7 10 12 13 15 25
I
NSERT
(x)
Create rank 0 list containing x
while
two list have equal rank
do
merge the two lists
E
XTRAXT
M
IN
()
Find list with smallest head element e
Remove and return e
Soft Sequence Heap
I
NSERT
(x)
Create rank 0 list containing x
while
two list have equal rank r
do
merge the two lists
if
r even
and
r > log 1/
ε
then
prune list
E
XTRAXT
M
IN
()
Find list with smallest head element e
if
|C(x)| = 0
then
Remove and return e
else
Remove and return an element from C(e)
Suffix-min pointers
and
witness sets
Analysis
Partial order of bounded “width”
Variations of Soft Heaps
– heap ordered trees
Open Problems
I/O & cache oblivious soft heaps with
O(
B
) soft heap operations take O(1) I/Os ?
Other applications of soft heaps ?
Are Soft Heaps simpler ?
Explore the properties and applications of Soft Heap and Soft Sequence Heaps, discussing how corruption handling and selection functions are optimized in these data structures. The concept of car-pooling and the simplification of heap operations are highlighted, along with references to relevant research works and improvements in efficiency over traditional heap structures.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Soft Sequence Heaps Soft Sequence Heaps ( (Accepted to SIAM Symposium on Simplicity in Algorithms, SOSA21) Gerth St lting Brodal Aarhus University Department of Computer Science, Aarhus University, November 3, 2020
Soft Heap Soft heap properties EXTRACTMIN can increase values (corruptions) Returns new corruptions ?N corrupted elements in soft heap, 0 ? , N = # insertions Heap EXTRACTMIN value value Car-pooling equal values = lowest intersected line 5 5 4 4 3 3 2 2 1 1 time time 5 4 1 2 1 3 2 3 4 5 5 4 1 2 1 2 3 3 4 2 5 4 New corruptions (created by EXTRACTMIN) INSERT(x) EXTRACTMIN() (other operations not discussed in this talk MAKEHEAP, MELD, FINDMIN, DELETE)
Soft heap results Soft heaps INSERT / EXTRACTMIN Reference Applications Introduced car-pooling Binomial trees Chazelle ESA98*/JACM00 *2018 ESA Test-of-Time award Selection MST O(m (m, n)) O(log1 ?) / O(1) MST optimal Unknown complexity Pettie, Ramachandran JACM02 A simpler soft heaps Balanced binary trees O(log1 Kaplan, Zwick SODA09 ?) / O(1) Soft heaps simplified Balanced binary trees O(1) / O(log1 Kaplan, Tarjan, Zwick SICOMP13 ?) Report corruptions Tag corrupted reported items Corruptions only EXTRACTMIN Heap selection (and related) Simplifying Frederickson JCSS93 O(1) / O(log1 Kaplan, Kozma, Zamir, Zwick SOSA19 ?) O(log1 Soft sequence heaps Brodal SOSA21 ?) / O(1)
Application of Soft Heaps O(n) Selection function select(A, k) if k = 1 then return min(A) Q = softheap(1/3) for a A do Q.INSERT(a) for i = 1 to |A|/3 do x = Q.EXTRACTMIN() small, large = partition(A, x) ifk |small| then return select(small, k) return select(large, k - |small|) ? 3,2 ? Pivot x has rank in (x is the increased value) 3 T(n) T(2n/3) + O(n) Chazelle JACM00
Application of Soft Heaps O(k) Heap Selection function select(root, k) S = {root} Q = softheap(1/4) Q.INSERT(root) for i = 1 to k - 1 do (e, C) = Q.EXTRACTMIN() if e not corrupted then C = C {e} for e C do Q.INSERT(e.left) Q.INSERT(e.right) S = S {e.left, e.right} return select(S, k) 3 42 4 11 Q 6 42 12 14 19 24 15 16 uncorrupted boundary Kaplan, Kozma, Zamir, Zwick SOSA19
Sequence heap properties Sorted lists, each list a rank Two lists rank r merge, rank r+1 Rank r list 2rvalues N INSERT rank log N Sequence Heaps rank 0 INSERT 2 15 INSERT(x) Create rank 0 list containing x while two list have equal rank do merge the two lists 1 2 15 13 25 2 1 7 10 12 2 13 15 25 EXTRACTMIN EXTRAXTMIN() Find list with smallest head element e Remove and return e 3 1 2 7 10 12 13 15 25 4 3 4 5 7 9 11 14 16 17 18 19 20
Sequence heap properties Sorted lists, each list a rank Prune every 2ndelement of a new list of even rank > log1 x pruned { x } C(x) added to C(y) where y successor of x Rank r list size 1 Soft Sequence Heap ? 3 3 10 14 15 20 24 2r 12 6 ? 3 4 7 18 19 21 23 merge INSERT(x) Create rank 0 list containing x while two list have equal rank r do merge the two lists if r even and r > log 1/ then prune list 13 16 4 3 4 7 10 14 15 18 19 20 21 23 24 pruned values (corruptions) 4 10 12 15 13 19 6 21 16 C(18) EXTRAXTMIN() Find list with smallest head element e if |C(x)| = 0 then Remove and return e else Remove and return an element from C(e)
Each non-pruned element has a corruption set C(e) and witness-set W(e) x C(e) x e x W(e) x e x corrupted x C(e ) for some e and x W(e ) for any e When EXTRACTMIN removes e, W(e) is reported as corrupted Suffix-min pointers and witness sets rank 0 15 Suffix-min 1 12 14 e e e 2 3 20 24 C(e ) W(e ) C(e) W(e) C(e ) W(e ) prune 6 6 3 4 7 18 19 21 23 e e e 16 16 13 W(7) witness-set 13 C(e ) { e } C(e) W(e ) C(e ) W(e ) { e } W(e)
Analysis Partial order of bounded width
Open Problems I/O & cache oblivious soft heaps with O(B) soft heap operations take O(1) I/Os ? Other applications of soft heaps ? Are Soft Heaps simpler ?
