Selection in Heaps and Row-Sorted Matrices Using Soft Heaps
Generalized selection involves finding the ?-th smallest item from a totally ordered domain with a known partial order. Various interesting selection problems are discussed, including selecting the ?-th smallest item in a heap using both trivial and non-trivial algorithms. The comparison between heaps and soft heaps, particularly in terms of operations and corruption of items, is also highlighted.
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
Selection in heaps and row-sorted matrices using soft heaps Haim Kaplan L szl Kozma Or Zamir Uri Zwick ( ) May 15, 2018
Generalized selection Given ? items from a totally ordered domain, with a partial order on them already known, find the ?-th smallest item, or the set of ? smallest items. All algorithms in this talk are comparison-based. smaller Partial order larger
Generalized selection Given ? items from a totally ordered domain, with a partial order on them already known, find the ?-th smallest item. The generalized sorting problem is well understood. Information-theoretic lower bound is essentially tight. Information-theoretic lower bound for generalized selection may be extremely loose. (E.g., finding the minimum) General answer for generalized selection is not known. Some interesting special cases were studied.
Some interesting selection problems Collection of sorted lists Doubly sorted matrix Binary min-heap set of pairwise sums ? + ? = ? + ? | ? ?,? ? (?,? are not sorted) Studied by [Frederickson-Johnson (1982)] [Frederickson (1993)] We give simpler and somewhat improved algorithms.
Selecting the ?-th smallest item in a heap 1 Already extracted 6 2 Currently in the heap 7 3 7 9 4 9 8 5 Trivial algorithm: ?(?log?) Insert root into an auxiliary priority queue ?. Repeat ? times: Extract the minimum item from ?. Insert its two children into ?. Not seen yet Returns the ? smallest items in sorted order.
Selecting the ?-th smallest item in a heap 7 9 15 11 10 17 21 25 16 14 12 19 23 22 30 Non-trivial algorithm: ?(?) [Frederickson (1993)] ?log ? ?loglog? ?logloglog? ?3log ? ?2log ? ? Matching the information-theoretic lower bound. We get an ?(?)-time algorithm by essentially running the trivial algorithm using a soft heap.
Heaps vs. Soft Heaps [Chazelle 00] [Kaplan-Tarjan-Zwick 13] Fibonacci heaps (Hollow heaps) Soft Heaps Make-heap Insert Extract-min Meld ?(1) ?(1) ?(log?) ?(1) ?(1) ?(1) ?(log1/?) ?(1) All bounds are amortized. Soft heaps may increase keys of items. Items with increased keys are corrupt. At most ?? items in the heaps are corrupt, where ? is the total number of insertions.
Previous applications of Soft Heaps A deterministic?(??(?,?))-time algorithm for finding minimum spanning trees [Chazelle 00] An optimaldeterministic algorithm for finding minimum spanning trees (with a yet unknown running time) [Pettie-Ramachandran 02] New selection and approximate sorting algorithms [Chazelle 00]
Deletions from a binary heap 7 9 15 11 10 17 21 25 16 14 12 19 23 22 30
Deletions from a binary heap 9 15 11 10 17 21 25 16 14 12 19 23 22 30
Deletions from a binary heap 15 11 10 17 21 25 16 14 12 19 23 22 30
Deletions from a binary heap 9 15 11 10 17 21 25 16 14 12 19 23 22 30
Deletions from a binary heap 9 15 11 17 21 25 16 14 12 19 23 22 30
Deletions from a binary heap 9 10 15 11 17 21 25 16 14 12 19 23 22 30
Deletions from a binary heap 9 10 15 11 17 21 25 16 14 19 23 22 30
Deletions from a binary heap 9 10 15 11 12 17 21 25 16 14 19 23 22 30
Deletions from a binary heap 9 10 15 11 12 17 21 25 16 14 19 23 22 30
Deletions from a binary heap 9 10 15 11 12 17 21 25 16 14 19 23 22 30
Binary heaps with lists [Kaplan-Tarjan-Zwick 13] Corrupt key of all items in the list Original keys Tree is heap ordered with respect to corrupt keys 18 3 12 2 4 16 17 18 22 27 27 8 22 15 1 30 45 45 30 40 35 40 35 Each node has a list of items. (Most) items in lists of length>1 are corrupt.
Binary heaps with lists [Kaplan-Tarjan-Zwick 13] Corrupt key of all items in the list Tree is heap ordered with respect to corrupt keys 18 3 12 2 4 16 17 18 22 27 27 8 22 15 1 30 45 45 30 40 35 40 35 Deleting an item of smallest corrupt key is easy. Until the list at the root becomes empty
Double even refill [Kaplan-Tarjan-Zwick 13] When a node of even rank ? ? is empty, fill it twice, concatenating the two lists of items. ? Move list of smaller child to root 56 18 44 10 45 56 1 12 2 4 16 17 18
Double even refill [Kaplan-Tarjan-Zwick 13] When a node of even rank ? ? is empty, fill it twice, concatenating the two lists of items. ? 18 1 12 2 4 16 17 18 Recursively fill the child 56 44 10 45 56
Double even refill [Kaplan-Tarjan-Zwick 13] When a node of even rank ? ? is empty, fill it twice, concatenating the two lists of items. 18 1 12 2 4 16 17 18 If ? ?is even, do it again! 56 20 44 10 45 56 4 14 20 5 ? = log3 ? Moving lists takes a constant time.
Controlling corruption The size of a node of rank ? is at most: Corrupt items rank ? ? ? 2 1 ??= 2 if ? > ? otherwise Claim: Number of nodes of rank ? is at most ?/2? rank < ? uncorrupt items Number of corrupt items: ?? 2?= ? ? 2? ? = log3 ? = ? ?? ? ? ?
Soft Heaps assumptions Insert and Meld do not corrupt items. All corruptions are caused by Extract-min, after extraction. Extract-min returns a list of newly corrupted items. ?,? Extract-min(?) Item with smallest (corrupt) key, extracted from the heap. List of newly corrupt items, corrupted after extracting ?. (Remain in the heap.) ?.??????? Is ? corrupt?
Selection from a heap using a soft heap Run the na ve algorithm using a soft heap. When an item is extracted, insert its children, and the children of all items corrupted by the extraction, into the soft heap. ? Soft-Heap(?) Insert(?,?) for ? 1 to ? 1: ?,? Extract-min(?) if not ?.???????: ? ? ? for ? ?: Insert(?,?.????) Insert(?,?.??? ?) Claim 1: After ? 1 iterations, the ? smallest items were inserted into ?. Claim 2: Total number of items inserted into ? is ?(?). Finish by finding the ?-th smallest among the inserted items, using a standard selection algorithm.
Selection from a heap using a soft heap Proof of Claim 1 Claim 1: After ? 1 iterations, the ? smallest items were inserted into ?. After each iteration, ? constrains a barrier of uncorrupt items, and possibly some corrupt items above them. All other items above the barrier were already extracted from ?. Corrupt items Barrier The item extracted at each iteration is smaller or equal tothe smallest item on the barrier. (We rely on the assumption that corruption occurs only after extractions.) After ? iterations, the rank of the smallest item on the barrier is at least ? + 1. After ? 1 iterations, the rank of the smallest item on the barrier is at least ?. After ? 1 iterations, the ? smallest items must be on or above the barrier, i.e., they were inserted into ?, as claimed.
Selection from a binary heap Proof of Claim 2 Claim 2: Total number of items inserted into ? is ?(?). ? Number of insertions ? Number of corrupt items 1 + 2? 1 2? ? ? < 2? + 2? ? < ? < 2 1 +1 + 2? ? < ? + ? ? ? 1 2? It is thus enough to take ? <1 2, e.g., ? =1 4. Each soft heap operation takes ?(1) time. Total running time (and number of comparisons) is ?(?). Simple!
Row-sorted matrices Select the ?-th smallest item from a collection of ? sorted lists. ? ? ? + ? , ? ?log? ? [Frederickson-Johnson (1982)] We immediately get ?(? + ?) using soft heaps. Number of items in the ?-row that are among the ? smallest We also get a simple ? ?log? ? algorithm. ? New output-sensitive result: ? ? + log(??+ 1) ?=1
Row-sorted matrices - ? ?log? ? ? Split each row into blocks of size 2?. Select the smallest 2? block leaders. (Using the ? ? + ? algorithm.) ? The ? smallest items must reside in at least 2? blocks. Thus, the selected 2? leaders must be among the ? smallest. At least ? blocks, i.e., the non-last blocks in each row, are fully contained in the set of ? smallest, and can be eliminated. In ?(?) time, ? was reduced to about ?/2. After log? ? iterations, ? is down to ?, and we use previous algorithm.
?log?? Row-sorted matrices - ? ? + ?=1 Let ?? be the length of the ?-th list. ? ? Let ? be the number of long rows. Long rows: ?? ?/2?. The short rows contain at most ?/2 items and are put on hold . The long rows contain at least ?/2 items of the solution. Split the long rows into blocks of size ?/(4? ). The ?/2 smallest items in long rows reside in at least 2? blocks. Select the 2? smallest leaders in the long rows. At least ? non-last blocks, containing at least ?/4 items, eliminated.
?log?? Row-sorted matrices - ? ? + ?=1 Let ?? be the length of the ?-th list. ? ? Cost of iteration is ? ? , proportional to number of participating rows. Each iteration reduces ? to at most 3?/4. Threshold (= ?/2?) decreases exponentially to a constant. Row ? participates in at most the last? log?? iterations. ?log?? . Total running time is ? ? + ?=1
Row-sorted matrices - ? ? + ?=1 ?log(??+ 1) Select the ? smallest items from a collection of ? sorted lists. Let ?? be the number of items selected from ?-th row. ? ? Let ? = ?=1 log(??+1) . Split each row into blocks of sizes 1,2,4, Note that ? is exactly the number of blocks that cover the ? smallest items. If we know ?, or a tight upper bound on it, we could select the smallest leaders and use the ?? algorithm. If ? not know, try = ?,2?,4?,
Concluding remarks Results for general partial orders? More applications of Soft Heaps? Thank you for your attention!
