leftist_heap (1376B)
1 # Leftist heap 2 3 https://en.wikipedia.org/wiki/Leftist_tree 4 5 Ideas: 6 7 - keep track of the [s_value] of the [tree] [nodes], which is the smallest distance to a [null_leaf] (= an empty tree place) 8 - ensure that the right child has the lower s-value 9 - in particular: the missing child, if any, should be the right one 10 11 [Complexities]: 12 - [find_min] in [O(1)] 13 - [delete_min] in [logarithmic] time 14 - [decrease_key] in [logarithmic] time 15 - [insert] in [logarithmic] time 16 - [meld] in [logarithmic] time 17 - [make_heap] in [linear] time 18 19 So worse than [Brodal_queue] 20 21 ## [Meld] 22 23 Let's merge two min leftist heaps with the the first one having the lower key 24 25 Merge it with the right child 26 27 Swap the left and right child depending on the s-values 28 29 Repair the s-values of the root after the merge 30 31 ## Other operations 32 33 - [insert] via [meld] 34 - [delete_min]: remove the root then [meld] the two children 35 - can delete an arbitrary element by replacing it with the merge of its two children and going up on the tree to fix the [s_values] 36 - [make_heap]: 37 - naively in [n_log_n] time 38 - more intelligently: merge elements two by two 39 - https://en.wikipedia.org/wiki/Monotone_priority_queue 40 41 ## Variants 42 43 - can be weight-biased instead of height-biased 44 - better constant factors, but no performance guarantees in general 45 46 Up: [priority_queue], [heap], [tree_binary] 47 48 Aliases: leftist heap