commit a06e862f4d7c6a1405ee6a37b85e73832a8d9e57
parent 51c2c466d7b5b62427b270741eefdb7a6e606a32
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 13 Jan 2025 15:19:15 +0100
commit with codex
Diffstat:
2 files changed, 65 insertions(+), 0 deletions(-)
diff --git a/brodal_queue b/brodal_queue
@@ -0,0 +1,17 @@
+# Brodal queue
+
+https://en.wikipedia.org/wiki/Brodal_queue
+
+[Complexities]:
+- [find_min] in [O(1)]
+- [delete_min] in [logarithmic] time
+- [decrease_key] in [O(1)] time
+- [insert] in [O(1)] time
+- [meld] in [O(1)] time
+- [make_heap] in [O(1)] time
+
+Can be made [purely_functional]: [brodal1996optimal]
+
+Up: [priority_queue]
+
+Aliases: brodal queues
diff --git a/leftist_heap b/leftist_heap
@@ -0,0 +1,48 @@
+# Leftist heap
+
+https://en.wikipedia.org/wiki/Leftist_tree
+
+Ideas:
+
+- keep track of the [s_value] of the [tree] [nodes], which is the smallest distance to a [null_leaf] (= an empty tree place)
+- ensure that the right child has the lower s-value
+ - in particular: the missing child, if any, should be the right one
+
+[Complexities]:
+- [find_min] in [O(1)]
+- [delete_min] in [logarithmic] time
+- [decrease_key] in [logarithmic] time
+- [insert] in [logarithmic] time
+- [meld] in [logarithmic] time
+- [make_heap] in [linear] time
+
+So worse than [Brodal_queue]
+
+## [Meld]
+
+Let's merge two min leftist heaps with the the first one having the lower key
+
+Merge it with the right child
+
+Swap the left and right child depending on the s-values
+
+Repair the s-values of the root after the merge
+
+## Other operations
+
+- [insert] via [meld]
+- [delete_min]: remove the root then [meld] the two children
+- 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]
+- [make_heap]:
+ - naively in [n_log_n] time
+ - more intelligently: merge elements two by two
+ - https://en.wikipedia.org/wiki/Monotone_priority_queue
+
+## Variants
+
+- can be weight-biased instead of height-biased
+ - better constant factors, but no performance guarantees in general
+
+Up: [priority_queue], [heap], [tree_binary]
+
+Aliases: leftist heap
