1 // Randomized meldable heap.
2 // https://en.wikipedia.org/wiki/Randomized_meldable_heap
3
4 use slotmap::{new_key_type, Key, SlotMap};
5
6 new_key_type! {
7 struct HeapKey;
8 }
9
10 #[derive(Copy, Clone)]
11 struct NodeHandle(HeapKey);
12
13 #[derive(Copy, Clone)]
14 struct Node<T> {
15 value: T,
16 children: [HeapKey; 2],
17 parent: HeapKey,
18 }
19
20 struct RandMeldHeap<T: Ord> {
21 sm: SlotMap<HeapKey, Node<T>>,
22 rng: std::num::Wrapping<u32>,
23 root: HeapKey,
24 }
25
26 impl<T: Ord + std::fmt::Debug> RandMeldHeap<T> {
new() -> Self27 pub fn new() -> Self {
28 Self {
29 sm: SlotMap::with_key(),
30 rng: std::num::Wrapping(0xdead_beef),
31 root: HeapKey::null(),
32 }
33 }
34
coinflip(&mut self) -> bool35 pub fn coinflip(&mut self) -> bool {
36 // Simple LCG for top speed - random quality barely matters.
37 self.rng += (self.rng << 8) + std::num::Wrapping(1);
38 self.rng >> 31 > std::num::Wrapping(0)
39 }
40
insert(&mut self, value: T) -> NodeHandle41 pub fn insert(&mut self, value: T) -> NodeHandle {
42 let k = self.sm.insert(Node {
43 value,
44 children: [HeapKey::null(), HeapKey::null()],
45 parent: HeapKey::null(),
46 });
47
48 let root = self.root;
49 self.root = self.meld(k, root);
50
51 NodeHandle(k)
52 }
53
pop(&mut self) -> Option<T>54 pub fn pop(&mut self) -> Option<T> {
55 self.sm.remove(self.root).map(|root| {
56 self.root = self.meld(root.children[0], root.children[1]);
57 if let Some(new_root) = self.sm.get_mut(self.root) {
58 new_root.parent = HeapKey::null();
59 }
60
61 root.value
62 })
63 }
64
remove_key(&mut self, node: NodeHandle) -> T65 pub fn remove_key(&mut self, node: NodeHandle) -> T {
66 let node = node.0;
67 self.unlink_node(node);
68 self.sm.remove(node).unwrap().value
69 }
70
update_key(&mut self, node: NodeHandle, value: T)71 pub fn update_key(&mut self, node: NodeHandle, value: T) {
72 let node = node.0;
73
74 // Unlink and re-insert.
75 self.unlink_node(node);
76 self.sm[node] = Node {
77 value,
78 children: [HeapKey::null(), HeapKey::null()],
79 parent: HeapKey::null(),
80 };
81 let root = self.root;
82 self.root = self.meld(node, root);
83 }
84
unlink_node(&mut self, node: HeapKey)85 fn unlink_node(&mut self, node: HeapKey) {
86 // Remove node from heap by merging children and placing them where
87 // node used to be.
88 let children = self.sm[node].children;
89 let parent_key = self.sm[node].parent;
90
91 let melded_children = self.meld(children[0], children[1]);
92 if let Some(mc) = self.sm.get_mut(melded_children) {
93 mc.parent = parent_key;
94 }
95
96 if let Some(parent) = self.sm.get_mut(parent_key) {
97 if parent.children[0] == node {
98 parent.children[0] = melded_children;
99 } else {
100 parent.children[1] = melded_children;
101 }
102 } else {
103 self.root = melded_children;
104 }
105 }
106
meld(&mut self, mut a: HeapKey, mut b: HeapKey) -> HeapKey107 fn meld(&mut self, mut a: HeapKey, mut b: HeapKey) -> HeapKey {
108 if a.is_null() {
109 return b;
110 }
111 if b.is_null() {
112 return a;
113 }
114
115 if self.sm[a].value > self.sm[b].value {
116 std::mem::swap(&mut a, &mut b);
117 }
118
119 let ret = a;
120
121 // From this point parent and trickle are assumed to be valid keys.
122 let mut parent = a;
123 let mut trickle = b;
124
125 loop {
126 // If a child spot is free, put our trickle there.
127 let children = self.sm[parent].children;
128 if children[0].is_null() {
129 self.sm[parent].children[0] = trickle;
130 self.sm[trickle].parent = parent;
131 break;
132 } else if children[1].is_null() {
133 self.sm[parent].children[1] = trickle;
134 self.sm[trickle].parent = parent;
135 break;
136 }
137
138 // No spot free, choose a random child.
139 let c = self.coinflip() as usize;
140 let child = children[c];
141 if self.sm[child].value > self.sm[trickle].value {
142 self.sm[parent].children[c] = trickle;
143 self.sm[trickle].parent = parent;
144 parent = trickle;
145 trickle = child;
146 } else {
147 parent = child;
148 }
149 }
150
151 ret
152 }
153
len(&self) -> usize154 pub fn len(&self) -> usize {
155 self.sm.len()
156 }
157 }
158
main()159 fn main() {
160 let mut rhm = RandMeldHeap::new();
161 let the_answer = rhm.insert(-2);
162 let big = rhm.insert(999);
163
164 for k in (0..10).rev() {
165 rhm.insert(k * k);
166 }
167
168 rhm.update_key(the_answer, 42);
169 rhm.remove_key(big);
170
171 while rhm.len() > 0 {
172 println!("{}", rhm.pop().unwrap());
173 }
174 }
175