commit 7f88bb78cbca59a7fdcc5dcd070744bf9b18675b
parent 5b62d601170e08c2cdc3a9d4384c7cd5f6f7dc8e
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 14 Jan 2025 10:55:46 +0100
Merge branch 'master' of a3nm.net:git/wiki_research
Diffstat:
3 files changed, 67 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
diff --git a/unambiguity b/unambiguity
@@ -35,3 +35,5 @@ pas de conversion polynomiale de 2-UFA vers [unambiguous_finite_automaton] par [
See also: [ddnnf], [unambiguous], [determinism_language]
Up: [formal_language_theory]
+
+Aliases: automaton unambiguous
