Overview of Soft Sequence Heaps in Algorithms
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.
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 Gerth St lting Brodal Aarhus University SIAM Symposium on Simplicity in Algorithms (SOSA), January 11, 2021
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) Time bounds are all amortized
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
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 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
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
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)
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/?
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 ?
