Overview of Soft Sequence Heaps in Algorithms

 
S
o
f
t
 
S
e
q
u
e
n
c
e
 
H
e
a
p
s
 
Gerth Stølting Brodal
Aarhus University
 
SIAM Symposium on Simplicity in Algorithms (SOSA), January 11, 2021
 
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
 
Time bounds are all amortized
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
     pivot = Q.
ExtractMin
()
  small, large = partition(A, pivot)
  
if
 k ≤ |small| 
then
     
return
 select(small, k)
  
return
 select(large, k - |small|)
Chazelle JACM00
 
recurse 3rd smallest ?
 
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)
 
x    y
 
Suffix-min pointers
 
and 
witness sets
 
Partial order
Summary - Soft Sequence Heaps
Slide Note

Chazelle introduced the Soft Heap as a priority to solve the minimum spannin tree problem

Embed
Share

Soft sequence heaps are a specialized data structure designed to handle corruptions in heap operations efficiently. This technology, introduced at Aarhus University, simplifies heap manipulation, particularly in car-pooling and other applications, with a focus on minimizing corruptions during extract-min and insert operations. Soft heaps find applications in a variety of scenarios and have evolved over the years for better performance and simplicity in algorithm implementations.

  • Soft Sequence Heaps
  • Algorithms
  • Data Structures
  • Aarhus University

Uploaded on Sep 10, 2024 | 0 Views


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


  1. Soft Sequence Heaps Soft Sequence Heaps Gerth St lting Brodal Aarhus University SIAM Symposium on Simplicity in Algorithms (SOSA), January 11, 2021

  2. 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)

  3. 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) Time bounds are all amortized

  4. Application of Soft Heaps O(n) Selection 8th smallest ? 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 pivot = Q.EXTRACTMIN() small, large = partition(A, pivot) ifk |small| then return select(small, k) return select(large, k - |small|) A 21 47 18 50 4 7 19 16 23 13 36 partition(A, pivot) 4 7 18 16 13 21 47 50 19 23 36 use soft heap to find pivot small large recurse 3rd smallest ? ? 3,2 ? pivot rank (pivot is the increased value) 3 T(n) T(2n/3) + O(n) Chazelle JACM00

  5. 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

  6. 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 INSERT and EXTRACTMIN amortized O(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

  7. Soft 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 2r/? Soft Sequence Heap ? 3 3 10 14 15 20 24 12 6 3 4 7 18 19 21 23 merge 13 16 x y 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 4 3 4 7 10 14 15 18 19 20 21 23 24 pruned values (corruptions, car-pooling) 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) How can this work ? Only O( ?/?) elements are not pruned Solution Not all pruned elements need to be considered corrupted

  8. Each non-pruned element has a corruption set C(e) and witness-set W(e) x C(e) x e x W(e) e x 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 13 W(7) C(21) C(e ) { e } C(e) W(e ) C(e ) witness-set W(e ) { e } W(e)

  9. Analysis corruptions ?n Partial order r Pruned elements Corrupted elements Bounded width C(e) doubles when pruning |C(e)| 2(r log1 width doubles when merging + increases by 2r/? when pruning width ?n )/2 2r/?

  10. Summary - Soft Sequence Heaps At most ?n corruptions in heap INSERT and EXTRACTMIN amortized time O(log 1 Witness-sets used in analysis and for reporting corruptions can be removed from construction if reporting not needed only n/? elements are not in corruption sets (previous constructions (n)) ?) Further results in paper Discuss how to remove buffering insertions from previous constructions Open problems I/O & cache oblivious soft heaps with O(B) operations taking O(1) I/Os ? Other applications of soft heaps ?

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#